增强Ad hoc网络连通性的单节点移动算法*

张颖 沈中 常义林

(西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安710071)

相对于常规通信网络而言，Ad hoc网络最大的特点就是可以在无基础设施支持的情况下，于任意时刻、任意地点快速地构建一个移动通信网络.一旦网络中某个或某些节点发生故障，网络中其它节点经过自组织仍然能够保证网络的正常工作.由于这样的网络具有一定的独立性，因而在战场通信、紧急救援、偏远地区通信及其它一些特殊商业领域中具有极大的吸引力和应用价值.

Ad hoc网络中，当某个节点因移动或故障而导致网络分割时，信息只限在网络局部传递而不能到达整个网络，这样的节点被称为网络分割点.如果网络中存在分割节点，那么网络的通信能力将受到极大的影响.因此，节点之间可靠的连通是保证网络通信的基础.为了增强网络的连通性，通常构造至少具有2-连通的网络拓扑，以保证在一个节点失效的情况下整个网络的连通.以往构造2-连通网络拓扑的研究主要集中在拓扑控制算法上，即通过动态调节各节点的传输功率来达到减少能量消耗的目的［1］.然而，在节点分布较为稀疏的区域，拓扑控制算法不能有效地降低节点的传输功率.因此，以提高网络连通性、降低能量消耗等为目的的节点移动机制成为了研究热点［2-11］.文献［3］中提出了一种节点聚集算法的理论框架，该算法在同步模式或异步模式下移动节点时不会破坏该节点与其邻节点之间的连通性.文献［4］中根据网络拓扑生成块图，即不包含分割节点的极大连通子图，将网络中包含节点数最少的块图内的节点整体向另一个块图中与该块图距离最近的节点移动.考虑到大量节点参与移动会消耗较多的能量，文献［5-6］中提出的LMC算法要求分割节点的邻节点中非同块图内且相距最近的两个节点相向移动，使这两个节点之间的距离减小到最大通信半径.与块移动算法不同的是，LMC算法中节点不需要收集全网络信息，因而更适合于大规模的网络.

上述算法均依赖于全球定位系统(GPS)定位.然而，GPS信号易受建筑物、地形的影响而存在无信号覆盖的盲区.在战场网络中，当某些系统受到GPS费用、功耗等限制而无法使用GPS时，节点将无法获取相关的位置信息.更为严格的是，一些资源有限的Ad hoc网络通常要求在不增加节点的情况下提高网络连通性，此时，如何移动节点是一项值得研究和解决的课题.BRN算法根据分割节点在8个不同方向上接收同一个邻节点信号值的变化来确定其邻节点的方向并移动分割节点的邻节点中属于不同块图且坐标夹角最小的两个节点［7］，由于分割节点为了确定邻节点方向参与移动而消耗能量，因此加快了网络分割.据此，文中提出了一种基于接收信号强度的节点移动算法，该算法在不破坏网络原有连接关系的条件下只移动一个节点到新位置以改善网络的连通性.由于只是单个节点移动，因此节点的移动对网络覆盖的影响较小.

1 相关概念

如果无线Ad hoc网络G中任意两个节点nτ和nω之间通过无线链路可达，则称G是连通的.若删除连通网络G中任一节点nν及其关联的所有链路后所形成的网络G'依然保持连通，那么网络G至少是2-连通的，即2-连通的网络中，任意两个节点之间至少存在2条不相交的路径.然而删除节点nν及其关联的链路后，G将被分割为多个2-连通分支，nν为网络的分割节点.如果将每个2-连通分支中的节点集合称为一个群，则群之间通过分割节点连接.如图1(a)所示的网络拓扑图中，节点nc0为分割节点并将网络分割成两个群C1和C2，C1={n1，n2，n3，n6}，C2={n4，n5}.网络中还会出现两个分割节点相连而形成分割节点对的情况.如图1(b)所示，节点nc1和nc2构成分割节点对，而群C1={n1，n2，n3}和C2={n4，n5}通过nc1和nc2连接.由于2-连通的网络中不存在分割节点，因此可通过探测网络中是否存在分割节点来判断该网络拓扑是否2-连通.目前，探测网络分割节点的方法主要是基于图论的构造深度优先遍历(DFS)生成树［8］.文中算法采用DFS生成树的方法来探测网络分割节点.

图1 某一Ad hoc网络的分割节点Fig.1 Cut nodes in an Ad hoc network

2 网络模型

考虑m个同质节点分布在二维平面上构成的Ad hoc网络.假设每个节点具有唯一ID号并用nτ(τ=1，2，…，m)表示.节点通过全向天线收、发信号，并通过相关的收、发设备指示信号强度.假设无线信道采用相同的传播模型，即无线信号的功率按照节点之间距离d的σ(σ≥2)次方衰减.对于给定的发送功率Pt及反映收、发设备工作特性的常数μ，接收功率Pr可以表示为

不同传输模型的σ取值不同，如自由空间模型中σ=2，而双线模型中σ=4.根据接收节点能否接收到信号及接收信号的强度作如下定义.

定义1当网络中任意节点nτ以一定功率发射信号时，如果节点nω(ω=1，2，…，m;ω≠τ)能够检测到nτ的信号，则称nτ是nω的呼叫节点.

定义2节点根据接收信号强度与接收门限PRT之间的关系，可以判断其与相应发射节点之间的距离关系.当节点nω接收到发射节点nτ的信号，即Pr(nω，nτ)≥PRT时，nτ和nω之间的距离没有超过节点的最大通信半径Rmax，nτ是nω的1-跳邻节点并且nτ和nω之间可直接通信;当Pr(nω，nτ)＜PRT时，nτ是nω的非1-跳呼叫节点.

定义3在节点nτ的1-跳邻节点中，存在节点nν(ν=1，2，…，m－1)，nτ接收到nν的信号强度为Pr(nτ，nν).根据式(1)可知，节点之间的距离越远，接收信号越弱.因此令nτ接收到的最小1-跳邻节点信号强度为Pr，min(nτ)=minPr(nτ，nν).为了不破坏nτ与其1-跳邻节点之间的链路，节点的移动需保证Pr，min(nτ)不小于PRT.因此，节点nτ可移动的最大距离与其最大自由度ρ(nτ)相关.ρ(nτ)定义为

从式(2)可以看出，ρ(nτ)≥0.ρ(nτ)越大则nτ可移动的距离越大.当Pr，min(nτ)=PRT，ρ(nτ)=0时，nτ可移动的距离为0.

定义4因为节点nτ与非1-跳呼叫节点之间的距离均大于Rmax，因此，为了建立nτ与非1-跳呼叫节点之间的直接通信，可通过移动nτ使nτ与这些节点之间的距离最大为Rmax.根据式(1)可知，当nτ接收到的呼叫信号越强时，nτ需向该呼叫节点移动的距离越小;相反，则需移动的距离越大.令nτ的最大呼叫连接信号强度为Ps，max(nτ)=maxPr(nτ，nω)，则nτ的最小趋向度φ(nτ)定义为从式(3)可知，0＜φ(nτ)＜1;φ(nτ)越小，nτ移动的距离越小，反之nτ移动的距离越大.

3 基于接收信号功率的节点移动算法

增加网络连通性最简单的方法就是减少分割节点数，该方法通过移动节点来增加与分割节点相连接的两个群之间的链路.为了节约能量，移动节点的选择应遵循以最少的能量消耗建立链路的原则.由于分割节点与其1-跳邻节点相距最近，因此选择与分割节点相连的任意群内分割节点的1-跳邻节点，作为移动节点向着另一个群移动.然而在节点从一个群向另一个群的移动过程中，会出现因移动而破坏该节点与本群内其它节点之间链路的情况;同时希望节点移动尽量少的距离即可与另一个群内的节点建立链路.因此，节点移动时应满足以下2个原则:(1)节点建立新链路的移动不应破坏网络原有的连通性;(2)节点移动的能量消耗最小.

考虑到节点无法获取位置信息，文中算法根据节点的接收信号强度在不同的两个群内各选一个节点，然后只移动其中一个节点而将另一个作为目标连接节点保持位置不变.

3.1 移动节点及目标连接节点的确定

为简明起见，以图1(a)为例进行分析.将分割节点nc0在群Ca(a=1，2)内的第i个1-跳邻节点表示为表示的第j个1-跳邻节点(除分割节点外)表示群Cb内的第k个呼叫节点.如表示节点n2表示节点表示n2的第2个1-跳邻节点表示在C2内n2的呼叫节点表示节点为n5的1-跳邻节点表示C1内n5的呼叫节点n3.

相应地，ncm的目标连接节点nct为另一个群内ncm的最大呼叫信号节点，即

根据上述方法，可以确定图1(a)所示网络中n2为移动节点，n4为n2的目标连接节点.这两个节点在图2(a)中分别用实、虚线圈标出.同时，图2(a)还标出了节点n1的最大通信范围以及节点n2与n4之间的呼叫链路.

对于图1(b)所示的分割节点对，可将两个分割节点nc1和nc2合并为一个新的分割节点nc12.同时，原分割节点的1-跳邻节点归并为nc12的1-跳邻节点，如图2(b)所示.然后，按照与单分割节点相同的方法在nc12的1-跳邻节点中确定移动节点n4和目标连接节点n2，图2(b)中分别以实、虚线圈标出.

图2 图1所示网络的可移动节点和目标连接节点Fig.2 Moving node and target node of network in Fig.1

3.2 移动的目标位置

与其它节点相比，分割节点是连通网络中较为特殊的节点，同时连接两个甚至多个群，因而这样的节点消耗能量更快.为了避免分割节点过快地消耗能量，移动节点作为增强网络连通性的重要节点在移动到新位置后，所形成从目标节点经移动节点到达分割节点的链路应具有最小代价.这一代价主要体现在节点之间用于通信的能耗.针对这类问题，文献［9-11］中提出的中继节点移动算法可以最小化源、宿节点之间数据流传输的能耗.考虑到实际的能耗包括信号传输的能耗和因其它因素产生的能耗，因此文中将接收信号强度的倒数作为链路的代价［12］.当移动节点位于平面上任意点x时，设接收到目标节点和分割节点的信号强度分别为Pnc(x)和Pnt(x)，则目标节点经移动节点到达分割节点这条链路的代价为因此，移动节点的目标位置x*是使得从目标节点通过移动节点到达分割节点所构成的链路上传输能耗最小的位置，即

3.3 节点的移动

由于无法获取节点位置信息，只能通过节点移动并测量某些点上的链路代价值，然后根据这些值再逐步移动的方法来确定目标位置.假设分割节点和目标节点在二维平面上的坐标分别为(unc，vnc)和(unt，vnt)，且在移动节点移动的过程中保持不变.当移动节点在i时刻的位置为x i(ui，vi)时，它与分割节点和目标连接节点之间的距离为dnc(x i)和dnt(x i)，接收到这两个节点的信号强度分别为Pnc(x i)和Pnt(x i)，且信号传输方向与u坐标的夹角分别为α和β，如图3所示.

图3 分割节点、目标连接节点和移动节点的位置Fig.3 Positions of cut node，target node and moving node

节点从x i出发沿着θi+1方向直线移动δi+1到达x i+1(ui+1，vi+1)，则

如果无线信道采用自由空间模型，那么根据式(1)、(6)和(8)，ξ(x i+1)可表示为

由图3所示可知节点间的位置关系如下:

根据式(1)有

将式(10)－(15)代入式(9)，然后对式(9)求关于δi+1的导数，得

由式(17)得到的δi+1为在搜索δ(x)最小值的过程中，节点从x i沿着θi+1方向到达x i+1所需移动的距离.由于－1≤cosα，sinα，cosβ，sinβ≤1，于是有

式(18)表明，根据位于x i时节点的Pnc(x i)和Pnt(x i)可计算得到在θi+1方向上节点移动距离δi+1的上限Δi+1.当节点沿着θi+1方向从x i到达x i+1时，在下一个ξ(x)减小的方向θi+2上移动距离δi+2.如此重复，直到节点搜索到ξ(x)的最小值点.然而为避免因移动而破坏网络原有的连通性，节点往往不能完全到达x*，文中给出算法停止的条件:

从而确保节点的移动不超出其1-跳邻节点的通信范围.算法具体步骤如下:

1)初始化参数i=0.移动节点位置记作x i，如果节点此时接收分割节点和目标节点的信号强度分别为Pnc(x i)和Pnt(x i)，则根据式(6)计算得到目标节点经移动节点到达分割节点链路的代价为ξ(x i).节点选取移动方向为θi+1.

2)节点从x i出发，沿θi+1方向直线移动单位距离δ0后到达若ξ(x i)，转步骤4).如果，说明θi+1为链路代价减小的方向，于是令，转步骤3).如果，节点将沿－θi+1方向移动到关于x i的对称点，并令，转步骤3).

3)以x i为起点，节点沿θi+1方向继续移动，根据式(18)计算节点在θi+1方向上的移动上限Δi+1.选取移动步长δi+1=Δi+1/2，节点从点x i沿θi+1方向直线移动δi+1到达x i+1.若ρ(ncm(x i+1))≤0，则算法结束;否则节点判断链路代价.若ξ(x i+1)≤ξ(x i)，则转步骤4);否则节点转向相反方向.根据在位置x i+1时节点的接收信号Pnc(x i+1)和Pnt(x i+1)，由式(18)计算出节点从x i+1沿－θi+1方向移动的上限，得到移动步长然后，节点沿－θi+1方向移动若，则算法结束;否则节点判断链路代价是否减小.若，令转步骤4).否则节点再次反方向并按照同样的方法移动，直到确定该方向上链路代价最小的位置为止.

4)节点从位置x i+1选择与θi+1垂直的方向θi+2，令x i=x i+1，θi+1=θi+2，转步骤2).

该算法首先保证了不破坏原有网络的连通性，并最大程度地移动节点至目标位置以增加移动节点与目标连接节点之间的通信链路.图4给出了节点移动的轨迹.从图4中可知，节点从x0搜索到x*，经过位置序列{x1，x2，…，x i，x i+1，…}.实际情况下，节点无法到达x*而是停留在该序列的某一位置点上.

图4 节点的移动轨迹Fig.4 Movement path of node

图5给出了图1中节点移动后的网络拓扑图.从图5可以看出，节点经过移动，构成了与目标连接节点之间的新链路且网络中任意两个节点之间至少存在两条互不相交的链路，因而该网络是2-连通的.由于网络中已不存在分割节点，将图1中分割节点的标识分别更换为图5(a)中的n7和图5(b)中的n6、n7.

图5 节点移动后的网络拓扑图Fig.5 Network topology after nodemovement

4 仿真实验

为验证所提算法的有效性，采用Microsoft VC 6.0仿真平台对随机部署的无线Ad hoc网络进行仿真.在800m×800m的平坦区域内，节点独立且随机分布.每个节点的最大通信半径为150m.为了取得较为合理的结果，相同节点数的网络在实验中均随机产生300个不同的场景，实验结果取平均值;节点在移动过程中，其它节点保持位置不变.首先考察节点移动后网络连通性能的改善和能量消耗情况，然后比较节点移动对网络覆盖面积的影响.

4.1 网络连通性能的改善

图6 两种算法对网络连通性能改善的比较Fig.6 Comparison of improvement of network connectivity by two algorithms

网络连通性能的改善是指在节点数相同的300个不同的网络场景中，能在不破坏网络原有连通性基础上通过移动节点来建立与目标节点之间的直接链路，从而构成具有2-连通性能的网络拓扑结构的场景数.图6给出了节点数从30～120变化且节点随机分布时文中算法和BRN算法的网络连通性能的改善情况.从图6可知，对于文中算法，原为单分割节点的网络连通性能的改善程度随节点数的增加而增大:当网络中节点数为30时，网络连通性能的改善值为9.33%，即只通过一个节点的移动，约28个场景达到2-连通;当网络节点数达到120时，网络连通性能的改善值为92.50%.这是因为当节点分布密集时，节点之间的距离相对较小，因而通过节点移动建立目标链路的成功率较高.对于原为分割节点对的网络，文中算法也取得了类似的结果:当网络中分布30个节点时，网络连通性能改善的均值为4.33%;当网络中分布120个节点时，网络连通性能改善的均值为61.67%.由于移动节点和目标节点之间的距离增大，因而需要移动更多的距离以建立目标链路.然而，为了确保网络原有链路不发生改变，原为分割节点对的网络连通性能的改善程度低于原为单分割节点的网络.在BRN算法中，由于分割节点也要参与移动以确定邻节点方位，因而影响了网络的原有连接关系，故其对网络连通性能的改善略低于文中算法.

4.2 节点移动的能耗

由于节点的移动需要消耗一定的能量，算法是否有效需要考虑节点移动过程中的能量消耗，具体体现为节点移动的距离.当网络节点数从30增加到100时，相同节点数的300个不同场景的节点移动距离的平均值如图7所示.在原为单分割节点的网络中，当节点数为100时，节点移动的平均距离为32.8943m，而节点数为60时，节点移动的平均距离最大为41.2677m.在原为分割节点对的网络中，当节点数为30时，节点移动的平均距离最小为28.3300m，节点数为70时节点移动的平均距离最大.可以看出，节点移动的距离随着网络中节点数的增加呈现出先增加后减小的趋势.这是因为节点的移动首先需要保证网络原有连通性不变，在节点分布较为稀疏的网络中，节点的可移动范围较小，因而节点的实际移动距离较小.随着网络中节点数的增加，节点之间的距离减小，移动节点的可移动范围变大，因而需要消耗更多的能量进行优化位置搜索.

图7 节点移动平均距离与网络中节点数的关系Fig.7 Averagemoving distance of node versus number of nodes in network

4.3 节点移动对网络覆盖面积的影响

节点移动改变了节点在网络中的分布，从而影响网络的覆盖面积.若节点移动前的网络覆盖面积为A0，它是将每个节点的覆盖面积累加、重叠的部分不重复计算得到的.同理可计算节点移动后的网络覆盖面积A.通过比较A/A0的值，可得到节点移动前后网络覆盖面积的变化.图8给出了文中算法和BRN算法在不同节点分布的网络中节点移动对网络覆盖面积的影响.从图8可知，当网络中有30个节点时，两种算法的A/A0均值分别为0.904和0.886;当网络中的节点数增加到100时，两种算法的A/A0均值均可达到0.997，可以说基本上保持了网络覆盖面积不变.这是因为节点趋向于目标节点的移动将产生与目标节点重叠的网络覆盖区域，从而减小了整个网络的覆盖面积，特别是在节点分布较为稀疏的网络中.另外，文中算法只允许移动一个节点且不改变网络原有的连通性，因此相对于BRN算法来说，覆盖面积的改变更小.然而，不论是文中算法还是BRN算法，节点的移动对网络覆盖面积的影响都随着网络中节点数的增加而减小.

5 结语

在节点位置信息未知的情况下，文中提出了一种基于接收信号功率的节点移动算法，用于对网络拓扑进行优化配置.根据接收信号强度，在分割节点的1-跳邻节点中分别确定移动节点和目标连接节点，并根据接收信号强度逐步移动节点，在不破坏网络原有连通性的同时建立这两个节点之间的直接链路.实验结果表明，该算法可以通过移动单个节点来改善网络拓扑的连通性，同时最小化节点移动对网络覆盖面积的影响.当然，移动一个节点并不能保证所有网络具有2-连通性.因此，今后将进一步探讨如何移动节点以构造具有抗毁性的网络拓扑.

［1］Li Ning，Hou J.FLSS:a fault-tolerant topology control algorithm forwireless networks［C］∥Proceedings of ACM/IEEE Annual International Conference on Mobile Computing and Networking.Cologne:ACM/IEEE，2005:275-286.

［2］公维宾，沈中，常义林.传感器网络中实现传输功率均衡的移动控制算法［J］.西安电子科技大学学报:自然科学版，2008，35(5):816-822.Gong Wei-bin，Shen Zhong，Chang Yi-lin.Movement control algorithms for realizing the balance of transmission power for sensor networks［J］.Journal of Xidian University，2008，35(5):816-822.

［3］Lin Jie.Distributed mobility control for fault-tolerantmobile networks［C］∥Proceedings of Systems Communications.New York:IEEE，2005:61-66.

［4］Basu P，Redi J.Movement control algorithms for realization of fault-tolerant Ad hoc robot networks［J］.IEEE Network，2004，18(4):36-44.

［5］Das S，Liu Hai，Kamath A，etal.Localizedmovement control for fault tolerance of mobile robot networks［C］∥Proceedings of InternationalWorkshop on Energy Optimization in Wireless Sensor Networks.Albacete:IEEE，2007:24-26.

［6］Das S，Liu Hai，Nayak A，et al.A localized algorithm for bi-connectivity of connected mobile robots［J］.Telecommunication System，2009，40(2/3):129-140.

［7］Butterfield J，Dantu K，Gerkey B，et al.Autonomous biconnected networks ofmobile robots［C］∥Proceedings of the 6th International Symposium on Modeling and Optimization in Mobile，Ad Hoc，and Wireless Networks and Workshops.Berlin:IEEE，2008:640-646.

［8］Kim H.Articulation points detection algorithm［EB/OL］.［2008-05-15］.http:∥www.ibluemojo.com/school/articul_algorithm.html.

［9］Goldenberg D，Lin Jie，Morse A，etal.Towardsmobility as a network control primitive［C］∥Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing.Tokyo:ACM，2004:163-174.

［10］Jiang Zhen，Wu Jie，Kline R.Mobility control with local views of neighborhood in mobile networks［C］∥Proceedings of International Workshop on Networking，Architecture，and Storages.Shenyang:IEEE，2006:9-14.

［11］Kashyap A，Shayman M.Relay placement and movement control for realization of fault-tolerant Ad hoc networks［C］∥Proceedings of the 41st Annual Conference on Information Sciences and Systems.Baltimore:IEEE，2007:783-788.

［12］Zhang Ying，Shen Zhong，Chang Yilin，et al.A signal awaremovement control algorithm for GPS-free Ad hoc networks［J］.Journal of Convergence Information Technology，2010，5(9):238-224.