无线网络中若干NP-难问题的参数算法

摘要

随着无线网络设计的日趋复杂化，无线网络应用中不断出现具有非常高复杂性的NP-难问题。作为求解NP-难问题的一种新思路，参数计算方法受到了人们的广泛关注，并被成功应用到诸多领域难解问题的求解中。
　　本文以无线网络中的最小能量组播路由、连通支配集、最大生命周期目标覆盖和完全p-支配集等NP-难问题为研究对象，在深入挖掘问题的参数特性基础上，运用参数计算理论和技术对它们进行参数化建模、多变量参数复杂性分析和参数算法设计与实现。主要研究工作包括:
　　对最小能量组播路由进行了参数化分析、参数算法设计与实现。单源组播是实现从某个源节点到指定目标节点进行通信的高效机制。而小规模组播（目标节点个数较少）在无线网络中具有重要应用。无线节点由电池供电，而限制网络延时是网络QoS的一个关键因素，因此设计能量有效且延时受限的组播至关重要。首先研究最小能量单源h-组播，即找到一颗能量代价最小的组播树，要求在组播树中从源节点到任一个目标节点均存在一条长度不超过h的路径。将最小能量单源办-组播转化为一个图优化问题，然后基于动态规划技术，提出一个时间为O(3k·(n+m)·h+2k·（n+m）2·h）的精确算法DBMM，其中k为目标节点个数，n和m分别为实例中顶点和边的数目。实验表明，与现有启发式或近似算法相比，算法DBMM可以节省的能量消耗在19％到42％之间，且在小规模组播场景下展现了较好的时间性能。在单源组播研究的基础上，进一步研究了多源组播和强连通组播。多源组播存在多个源节点，要求实现任一源节点到目标节点的通信，而强连通组播要求一组节点中任意一个节点均能实现到组中其它节点的通信。利用参数化规约，证明最小能量强连通h-组播以“目标节点个数k”和“转发节点个数k2”作为双参数是W[1]-难的，而最小能量多源h-组播以k2为参数是W[2]-难的。最后利用多项式时间参数化转换，证明最小能量单源h-组播问题以（k,k2）作为双参数不存在多项式核。
　　针对平面图上连通支配集设计了降低问题规模的核心化算法。连通支配集被用于构建无线网络中的虚拟骨干网，从而为网络中的广播和路由等操作提供一个有效的通信基础。首先通过对给定实例中顶点进行着色，挖掘出图中顶点之间的新的组合特性，进而提出一系列高效的多项式时间局部简化规则。接着对区域分解技术进行扩展，将规约图进行区域数目不超过3k-6的极大区域分解（k为问题解的大小），并将图中区域按区域端点间的最短距离分成两类:端点间的距离为1的区域、端点间的距离大于1的区域。通过充分利用问题解的连通特性，证明了后一种类型的区域的个数不超过2k-5。结合着色规约规则与平面图的性质，证明了这两种区域中顶点个数的上界分别是23和41。最后利用问题解的连通特点及着色规则，证明位于区域以外的顶点个数也是有界的，从而得出一个大小为130k的线性核，这是当前的最好结果。
　　研究了最大生命周期目标覆盖问题的参数复杂性及参数算法设计。最大生命周期目标覆盖的主要任务是将传感节点分组，并给每个组分配时间片，使得在满足覆盖需求的同时最大化网络生命周期。为了深入理解问题难解性根源，对两类目标覆盖问题进行系统的参数复杂性分析:最大-最小目标覆盖和最大-个体目标覆盖。最大-最小目标覆盖要求每个组至少覆盖k2个目标节点，而最大-个体目标覆盖要求每个目标节点至少被k3个组覆盖。首先证明了最大-最小目标覆盖和最大-个体目标覆盖在以下特殊情况下仍是NP-难的:每个目标节点至多被两个传感节点覆盖，或者每个传感节点至多可以覆盖两个目标节点。因此，限制传感节点的“度”或目标节点的“度”不会降低问题的难度。相反，限制目标节点的个数可以降低这两个问题的复杂性。也就是，最大-最小目标覆盖和最大-个体目标覆盖以“目标节点个数”作为参数是固定参数可解的。接着研究了结构参数“至少覆盖两个目标节点的传感节点个数k”。基于整数线性规划技术，证明了最大-最小目标覆盖和最大-个体目标覆盖关于参数k均是固定参数可解的。最后，利用图着色技术，针对最大-最小目标覆盖提出了时间为O*((6.1k1k2)k1k2）的精确算法，其中k1表示划分组的数目。
　　研究了完全p-支配集的参数复杂性及参数算法设计。完全p-支配集被用于构建无线节点的自我保护网络，从而使无线节点能够抵抗外部的攻击。首先证明完全p-支配集在顶点最大度为3的UDG(unitdisk graph)上仍是Np-难的。为了深入理解完全p-支配集在UDG模型上的难解性根源，接着研究了完全p-支配集在UDG上的参数复杂性。利用k-团问题进行参数化规约，证明完全p-支配集在UDG上是W[1]-难的，并发现了UDG上相交圆间的距离对问题难度有根本性的影响。基于问题难解性根源的分析，最后利用树分解技术和动态规划技术，针对平面图（一种特殊DG模型）上的完全p-支配集设计了一个时间为O((2p+2)19.1·√kk3n+n3)的精确算法，其中n为给定实例中的顶点个数，k为问题解的大小。从而证明了完全p-支配集在平面图上以p和k为参数是固定参数可解的。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究内容

1．3 研究意义

1．4 全文结构

第二章 参数计算理论概述

2．1 计算复杂性

2．1．1 P vs NP

2．1．2 参数复杂性

2．1．3 多变量参数复杂性

2．2 参数算法设计技术

2．2．1 核心化

2．2．3 树分解和动态规划

2．2．3 着色技术

2．2．4 整数线性规划

2．3 小结

第三章 最小能量组播路由的参数算法设计与实现

3．1 引言

3．2 相关工作

3．3 模型和相关定义

3．4 固定参数可解算法

3．4．1 等价转换

3．4．2 算法

3．5 固定参数不可解结果

3．6 模拟实验与分析

3．6．1 模拟环境

3．6．2 性能分析

3．7 小结

第四章 平面图上连通支配集问题核上界改进

4．1 引言

4．2 相关术语

4．3 规约和着色规则

4．4 问题的核

4．5 小结

第五章 最大生命周期目标覆盖参数复杂性分析

5．1 引言

5．2 相关工作

5．3 模型和相关定义

5．4 度受限图上的复杂性

5．5 参数复杂性

5．5．1 “与可解情况的距离”的参数复杂性

5．5．2 “目标节点个数”的参数复杂性

5．5．3 组合参数的参数复杂性

5．6 小结

第六章 完全p-支配集的参数算法设计

6．1 引言

6．2 相关术语

6．3 UDG上的NP复杂性

6．4 UDG上的固定参数不可解

6．5 平面图上的参数亚指数算法设计

6．5．1 树分解

6．5．2 动态规划

6．6 小结

第七章 结论

7．1 主要贡献和创新点

7．2 展望

参考文献

致谢

攻读博士学位期间主要的研究成果