论文部分内容阅读
[摘要] 移动自组网中节点移动是网络快速变化的主要原因。快速变化的网络拓扑给移动自组网，尤其是路由设计带来了巨大挑战。基于最小连通支配集算法是一种有效的分层路由算法，它将路由搜索集中在连通支配集内。详细分析了两种具有代表性的连通支配集算法，分别指出它们的不足之处，并进行了初步验证。
[关键词] 移动自组网 支配集 网关节点
一、引言
移动自组织网络（简称Ad Hoc网络或MANET）旨在建立一个可以即时展开、随意通信并对网络拓扑结构变化迅速做出反应的数据网络[1]。这给路由设计带来很大的难度。
最近提出的基于最小连通支配集(Minimum Connected Dominating Set, MCDS)的路由方法是一个很好的分层路由方法,它将路由过程简化到一个由MCDS生成的较小的子网中。MCDS中的网关节点构成了高一级的虚拟骨干网,而每个网关节点在自己的簇中都起着控制中心的作用，用于路由分组和广播路由信息。明显地，这种方法的有效性很大程度上依赖于发现和维持一个MCDS及与之相应的子网的大小。不幸的是，对大部分图来说，求一个MCDS的问题属NP-C问题[2]，在实际应用中需要设计近似求解算法。目前已有的算法主要分两类,集中式算法和分布式算法。集中式算法要求每个节点具有整个网络的拓扑结构信息，因而不适合移动网络多变的特点，可伸缩性差；分布式算法的主要思想是通过节点之间的局部交互操作在网络中迅速构造一个虚拟骨干网(CDS)。
有关连通支配集的算法，国内外已经有许多人从事这一方向的研究。文献[2 ]提出了一种适用于单向ad hoc 网络的连通支配集算法(以后称作UL－WMCDS算法)，它将主机的功率大小或在线时间的长短作为每个节点的权值，这种基于极大权的CDS的选择确保了大部分合适的节点担任网关节点的角色，使其能更好的协调管理网络中所有其他节点,从而能保持CDS的相对稳固性。
二、UL-WMCDS算法分析[3]
文献[3]指出由上述算法得到的网关节点集D是图G的一个连通支配集。接着以一个图例如图1，来说明上述算法的执行过程，得到连通网关集D={3,4,5,6}。
图1 单向ad hoc网络的连通支配集图2 权值改变的连通支配集
对于相同的网络结构，即节点个数及边的方向信息保持不变，但每个节点的权值信息改变，利用UL-WMCDS算法却得到相同的支配集，即每个节点的权值对连通支配集的构造并没有太大的影响。
如图2，节点4的权值变为12，节点6的权值变为15，仍然得到连通网关集D={3,4,5,6}。只不过这时簇的结构发生改变，权值较小的节点4、6充当了网关节点，以节点4、6为骨干节点的簇分别只有4、6两个节点。
三、PLA-CDS算法分析[4]
该算法是一种基于队列选择的移动自组网中电力及负荷感知的构造最小连通支配集算法。算法中将节点根据电力情况和负荷分为9个级别,并从随机节点开始进行广度优先的搜索或深度优先搜索，并通过对搜索结果执行精简规则使得得到的结果是对应MANET的最小连通支配集。文献[3]中综合考虑了节点电力和负荷情况,能够获得最小连通支配集,但也略有不足,主要表现在：
1.该算法是一种非分布式的支配集构造算法，即需要一控制中心来存储网络中节点的电力及负荷信息，而不是通过节点的交互操作来构造CDS；
2.节点电力和负荷情况对支配节点搜索过程并没有重要影响。如图4，算法从节点1开始搜索，得到的连通支配集D＝{1,2,3,4,6,7},实施精简规则后，得到的最小连通支配集＝{3，4，7},与图3所得的最小连通支配集相同。
图3 MANET的最小连通支配集图4 不同搜索起点的连通支配集
四、结论
MANET是一个崭新的研究领域，它的网络特性――自组性、多跳性、节点的随即移动性、分布式控制等给MANET路由问题研究带来了极大的挑战。详细分析了两种具有代表性的连通支配集算法：UL-WMCDS算法和PLA-CDS算法，分别指出它们的不足之处，并进行了初步验证。
参考文献：
[1]阎新芳:基于极大权的最小连通支配集启发式算法[J].电子学报,2004,32(11):1774-1777
[2]Graey M L, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. San Francisico: W H Free man.1979
[3]吴小艳聂欣:一种适用于单向ad hoc网络的连通支配集算法[J].传感技术学报，2006，19（3）：905-907
[4]朱艺华沈毅俊吴小艳:移动自组网电力及负荷感知的构造最小连通支配集算法[J].电子学报，2006,34(11）:2004-2007
[关键词] 移动自组网 支配集 网关节点
一、引言
移动自组织网络（简称Ad Hoc网络或MANET）旨在建立一个可以即时展开、随意通信并对网络拓扑结构变化迅速做出反应的数据网络[1]。这给路由设计带来很大的难度。
最近提出的基于最小连通支配集(Minimum Connected Dominating Set, MCDS)的路由方法是一个很好的分层路由方法,它将路由过程简化到一个由MCDS生成的较小的子网中。MCDS中的网关节点构成了高一级的虚拟骨干网,而每个网关节点在自己的簇中都起着控制中心的作用，用于路由分组和广播路由信息。明显地，这种方法的有效性很大程度上依赖于发现和维持一个MCDS及与之相应的子网的大小。不幸的是，对大部分图来说，求一个MCDS的问题属NP-C问题[2]，在实际应用中需要设计近似求解算法。目前已有的算法主要分两类,集中式算法和分布式算法。集中式算法要求每个节点具有整个网络的拓扑结构信息，因而不适合移动网络多变的特点，可伸缩性差；分布式算法的主要思想是通过节点之间的局部交互操作在网络中迅速构造一个虚拟骨干网(CDS)。
有关连通支配集的算法，国内外已经有许多人从事这一方向的研究。文献[2 ]提出了一种适用于单向ad hoc 网络的连通支配集算法(以后称作UL－WMCDS算法)，它将主机的功率大小或在线时间的长短作为每个节点的权值，这种基于极大权的CDS的选择确保了大部分合适的节点担任网关节点的角色，使其能更好的协调管理网络中所有其他节点,从而能保持CDS的相对稳固性。
二、UL-WMCDS算法分析[3]
文献[3]指出由上述算法得到的网关节点集D是图G的一个连通支配集。接着以一个图例如图1，来说明上述算法的执行过程，得到连通网关集D={3,4,5,6}。
图1 单向ad hoc网络的连通支配集图2 权值改变的连通支配集
对于相同的网络结构，即节点个数及边的方向信息保持不变，但每个节点的权值信息改变，利用UL-WMCDS算法却得到相同的支配集，即每个节点的权值对连通支配集的构造并没有太大的影响。
如图2，节点4的权值变为12，节点6的权值变为15，仍然得到连通网关集D={3,4,5,6}。只不过这时簇的结构发生改变，权值较小的节点4、6充当了网关节点，以节点4、6为骨干节点的簇分别只有4、6两个节点。
三、PLA-CDS算法分析[4]
该算法是一种基于队列选择的移动自组网中电力及负荷感知的构造最小连通支配集算法。算法中将节点根据电力情况和负荷分为9个级别,并从随机节点开始进行广度优先的搜索或深度优先搜索，并通过对搜索结果执行精简规则使得得到的结果是对应MANET的最小连通支配集。文献[3]中综合考虑了节点电力和负荷情况,能够获得最小连通支配集,但也略有不足,主要表现在：
1.该算法是一种非分布式的支配集构造算法，即需要一控制中心来存储网络中节点的电力及负荷信息，而不是通过节点的交互操作来构造CDS；
2.节点电力和负荷情况对支配节点搜索过程并没有重要影响。如图4，算法从节点1开始搜索，得到的连通支配集D＝{1,2,3,4,6,7},实施精简规则后，得到的最小连通支配集＝{3，4，7},与图3所得的最小连通支配集相同。
图3 MANET的最小连通支配集图4 不同搜索起点的连通支配集
四、结论
MANET是一个崭新的研究领域，它的网络特性――自组性、多跳性、节点的随即移动性、分布式控制等给MANET路由问题研究带来了极大的挑战。详细分析了两种具有代表性的连通支配集算法：UL-WMCDS算法和PLA-CDS算法，分别指出它们的不足之处，并进行了初步验证。
参考文献：
[1]阎新芳:基于极大权的最小连通支配集启发式算法[J].电子学报,2004,32(11):1774-1777
[2]Graey M L, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. San Francisico: W H Free man.1979
[3]吴小艳聂欣:一种适用于单向ad hoc网络的连通支配集算法[J].传感技术学报，2006，19（3）：905-907
[4]朱艺华沈毅俊吴小艳:移动自组网电力及负荷感知的构造最小连通支配集算法[J].电子学报，2006,34(11）:2004-2007