基于改进虚拟力算法的通信基站再部署策略

赵海富,陈 炯,谷源涛

(1.清华大学 微波与通信国家重点实验室,北京100084;2.总参陆航研究所,北京101121)

1 引 言

在地震、飓风、洪水等自然灾害,以及大规模战争中,固定的通信设施很可能遭到破坏,导致通信网络无法正常运行。通过移动终端(手机)进行自组网通信是理论上可行的解决方案,但是受限于设备本身功率等问题,这种方式很难达到较高的通信容量和较大的覆盖范围;卫星电话性能良好但设备昂贵,不方便广泛配置,所以亟需具有一定移动性、可动态组网的通信基站为灾区或战场区域提供通信中继服务。

可移动性使得基站能够根据客观条件重新组网,尽快地恢复通信网络或者根据战场情况实时调整基站分布,保证对战区有效覆盖和关键区域的优先保障。基站的可移动性为网络设计提出了新的要求,其中基站位置调控机制和调整过程中保证业务的持续稳定是其中的两个重要问题。现有基站规划方法一般仅考虑静态的基站部署,以基站密度和系统容量为考核指标,力求在保证通信容量的基础上,通过线性规划等方法,尽量减少基站数量以提高经济效益,基本不涉及动态规划。本文研究了移动基站的动态规划问题,提出了一种基于业务量的虚拟力算法来实现基站的动态规划,在保证覆盖率的同时大幅降低通信中断次数,是基站动态规划方面的有益尝试。

虚拟势场法由Khatib[1]在移动机器人障碍躲避问题中提出,由Howard[2]和Poduri[3]等人先后引入到无线传感器网络覆盖问题。Zou[4-5]根据虚拟势场的概念正式提出了虚拟力算法。而后相关的研究工作逐渐展开,主要的研究工作包括边界条件[6]、覆盖盲区的处理[7-9]、力的计算公式[10]、移动损耗[11-12]和局部最优解问题[13-15]等。相关的研究工作对我们设计基于业务量的移动基站规划方案有一定的启发。

2 虚拟力算法的基本原理

虚拟力算法的基本原理是假设节点间存在引力和斥力作用,在引力的作用下节点相互靠近,保证连通;在斥力的作用下,节点相互远离,避免重复覆盖;最终节点会在引力和斥力的联合作用下达到平衡位置。

假定 dij是基站Si和Sj之间的欧式距离,αij为两基站间的方位角,dth为基站间最佳距离,虚拟力计算公式定义为

考虑到区域中障碍物的斥力作用FiR,以及覆盖盲区或覆盖中心的引力作用FiA,节点i受到的总的力的作用为

其中,FiR可以定义为

FiA可以定义为

3 通信基站再部署策略

传统的虚拟力算法并不能直接应用于基站动态规划问题中,本文应用虚拟力原理设计了一种基于业务量的移动基站再配置方案,相比传统虚拟力算法,主要从以下三方面进行了改进。

3.1 计算虚拟力的参量

传统的方法中,计算虚拟力的参量是节点之间的距离。在现实通信系统中,由于天气、电磁辐射、地面植被、多径、障碍物等因素,节点间的绝对距离不能完全代表其间的通信质量,依照绝对距离计算虚拟力势必导致较大偏差。本文提出利用接收信号强度(Received Signal Strength Indication,RSSI)作为虚拟力的参量,使得虚拟力的含义更加贴近实际情况,优化结果也更有实用价值。

为了利用现有虚拟力计算公式,我们根据基站获得的信号强度和基站的发射功率,得到传播过程中信号的衰减值l,再由自由空间的衰减模型(公式(5))反解出基站间的等效距离,根据该等效距离,计算基站之间的虚拟力。

其中,d为发射端和接收端距离(单位为km),f为无线电传播频率(单位为MHz),n为路径衰减因子,一般取2～5。由于所有基站之间均选用同一公式进行等效距离的计算,所以等效距离可以较好地区分出基站间的信号质量差别,从而产生不同的虚拟力指导基站移动,依照此虚拟力控制基站移动可以更为有效地保证基站间通信质量的均衡,从而保证了基站对整个区域的有效覆盖和有效连通。

3.2 基站移动的限制方案

基站的移动使得基站之间的连接情况实时变动,网络拓扑动态变化,很容易造成当前业务的中断和大批底层用户的不断越区切换,严重影响通信质量,所以必须采取一定方法来限制基站的移动。

虚拟力算法中对节点中止问题主要采用两种方法:限制虚拟力合力反向次数[13]、假设节点移动过程中存在摩擦力[15]。由于移动基站的特殊性,为填补邻近基站死亡产生的盲区,网络中多数基站都应该处于可移动状态,所以第一种方法不太适合移动通信基站。后一种方法中摩擦力的取值对效果有较大影响,需要根据节点受到的虚拟力大小、节点的虚拟质量和移动速度等因素进行仔细调整,参数设置比较困难,所以在移动基站规划中也较难利用。

我们提出了新的基站移动的限制方案,假设基站在移动过程中处于两种状态:移动态和固定态。处于移动态时,基站根据虚拟力计算下一步移动的方向和距离,并将目的位置与之前的x次位置进行比较,如果综合偏差较大,则正常移动,否则认为该基站不需要移动,基站进入固定态,本次迭代过程结束;处于固定态的基站不需要进行虚拟力的计算,只维持自身位置不变,经过y次迭代后,重新回到移动态。

在平衡位置附近振荡运动的基站,综合偏差应该很小;正在运动的基站综合偏差应该较大,所以通过x次移动轨迹的综合偏差进行考察,我们可以较方便地分辨出正在移动的基站和接近或达到平衡位置的基站,将平衡位置附近的基站设置为固定态后,使得此类基站不会再进行无谓的移动;进入固定态一定时间后,基站又会重新回到移动态考察自身所受虚拟力作用,从而对附近的覆盖盲区进行响应。实验结果显示,统计之前3～5次移动位置即可较好地分辨出平衡基站和运动基站;而y值的选取不能过大,过大的y值会使网络对覆盖盲区的响应时间较长,过小的 y值又会使基站移动频繁,造成服务质量恶化,所以实际工作中需要在覆盖盲区延时和网络服务质量间进行折衷。

由于各个基站独立记录自身位置和处于固定态的次数,所以网络中各个基站的状态是相互独立的,基站数量充足时可以保证网络中时刻都存在着一定数量的可移动基站来保证对盲区的覆盖,同时也可以使得一定数量的基站保持固定状态不变,使得服务质量得到有效改善。

3.3 基于业务量的业务保持机制

由于基站的相互移动,可能导致当前存在通信业务的两个基站因为相互远离发生业务中断,为尽量避免因基站移动引起的通信业务中断,我们设计了基于业务量的业务保持机制:首先对基站之间的业务进行统计,由得到的业务量产生额外的虚拟力,促使存在通信业务的两基站相互靠近。由业务量产生的虚拟力计算公式为

式中,c为业务量产生的虚拟力的放缩系数,用来调整业务量产生的虚拟力的强度;tij为基站i和j之间归一化的业务量,由当前支路上的业务量除以该支路的最大承载业务量得到,用以调整不同业务量支路之间虚拟力的差别;Rc为基站的通信半径;dij为基站i和j之间信号强度等效的距离。

上式的意义在于当两基站间信号强度较弱时,两基站间会产生相互的引力作用,促使两基站相互靠近,从而使得两者间相对信号强度得到加强,降低发生通信中断的概率;基站间距离越远,本身业务中断的概率越大,产生的虚拟力就越大,基站相互靠近的趋势越大;而当基站间信号强度较强,即等效距离较近时,为了不对基站的扩散产生过大阻力,业务量产生虚拟力为0。基于业务量的虚拟力的大小也和基站间的流量成正比,即利用归一化的流量决定基站间虚拟力的大小,优先保障重要(大量)业务链路的连通性。

4 仿真分析

4.1 参数设置

基站需要覆盖区域为10 km×10 km;区域内随机分布100个通信节点和40个可移动通信基站,基站覆盖半径为Rb=1 km,通信半径为Rc=2 km,基站为Rb范围内的所有节点提供服务,可以与Rc范围之内的所有基站进行通信,为了保证完全覆盖基站间最佳距离应该设为

4.2 仿真分析

仿真的目的是通过仿真验证基站规划方法对网络覆盖率和连通率的影响,对改进方案的优越性进行考察。由于应用基站移动的限制方案带来的好处较为直观,此处不对其进行深入介绍,重点考察另外两种方案的性能。

4.2.1 覆盖性和连通性

设虚拟力最大迭代次数为30,进行1 000次独立实验,统计得到在虚拟力算法迭代过程中平均覆盖率和连通率变化如图1所示。

图1 覆盖率和连通率随迭代次数变化曲线Fig.1 Station coverage and connectivity improvement by the number of iterations

可见,随着迭代次数的增加,覆盖率和连通率均不断增加,其中迭代次数为1～10次时增加明显,此后略有提升。由于实际工作中最大迭代次数越小,基站调整过程越快,综合考虑,最大迭代次数设为5～10次即可。

对比利用RSSI和不利用RSSI的虚拟力方法性能,发现利用RSSI计算虚拟力得到的覆盖率和连通率要较直接利用基站间距离好,这是因为基站间信号强度更能真实地反映出基站间的连接情况和基站对周围区域的覆盖情况,利用信号强度指导基站移动使得基站的分布更合理,网络服务质量更好。

4.2.2 业务中断次数

业务中断次数是衡量网络服务质量的重要指标,为了保证动态覆盖基站必须具有移动性,这就导致业务中断是不可避免的。我们试图通过3.3节所述方案在不过分影响覆盖率的前提下来降低中断次数。我们将利用该方案的虚拟力方法(称为改进方法)与未利用该方案的方法(称为原方法)进行对照实验,得到了不同基站数量下覆盖率和中断次数变化,如图2所示。

图2 覆盖率和中断次数随基站数量变化曲线Fig.2 Coverage and breaks changeswith the number of stations

其中覆盖率是指完成虚拟力迭代后最终覆盖率,中断次数是指在迭代过程中产生的业务中断次数统计。图2中上部的两条较为接近的曲线,是原方法和改进方法所对应覆盖率,可见两者相差不大,随着网络中基站个数的增多覆盖率会越来越好。

图2中下部虚线为原方法规划过程中的中断次数,实线为改进方法规划过程中的中断次数。可以看出,中断次数随着基站数量的增加是逐步增加的,这是因为基站数量的增加使得网络覆盖功能增强,会为更多的节点提供通信中继服务,使得业务量的基数得到增加,同时在中继服务中,路由的平均跳数也会增加,使得业务中断的概率有一定增加,最终导致了中断次数增加。对比原方法和改进方法可以看到,改进方法大幅降低了业务中断次数,并且随着基站数量增加改进方法中断次数的增长率也较原方法略小。

4.2.3 覆盖率和连通率的恢复

在基站工作过程中,由于自身设备故障或被恶意破坏,会有部分基站不断损失,由此产生覆盖盲区,并可能导致网络的分离。为了验证改进方案在基站损失后覆盖性恢复以及连通性保持方面的性能,我们进行了基站损失实验,假设在基站迭代过程中,每30次迭代就会有一个基站死亡,得到的基站覆盖和连通率变化如图3所示。

图3 覆盖率和连通率随基站死亡变化曲线Fig.3 Coverage and connectivity changes with the stations death

图3中覆盖率是指完成基站部署后所有基站不再移动所得到的随着基站死亡的覆盖率变化,改进虚拟力算法的覆盖率是指基站部署后按照改进的基站规划方案进行不断调整所得到的覆盖率,连通率和改进虚拟力算法的连通率也与上述定义类似。

从图3结果可以看出,随着基站的损失,网络的覆盖率和连通性都会不断下降,但是在移动基站规划方案的作用下,网络的连通性会在一定程度上得到保持,覆盖率也可以得到一定程度的恢复。其中前10个基站死亡后覆盖率恢复和连通率保持较为明显,从图3(a)中可以看出随着基站死亡改进方法的连通率基本保持在100%,改进方法覆盖率会在基站死亡的瞬间有一定降低,但会随着迭代过程有所恢复。整体来看覆盖性和连通性上改进方法要较基站固定不动有大幅改善,但同时基站的不断损失对网络性能的影响都是不可忽视的,基站规划方案只能减缓覆盖率和连通率的下降速度,不能完全抵消基站损失对网络的影响,如图3(b)所示。

5 结 论

本文从移动基站动态规划问题出发,利用虚拟力算法在计算虚拟力的参量、基站移动的限制方案和基于业务量的业务保持机制等方面进行了新的设计,使得改进的虚拟力算法既能使基站保证对覆盖区域的覆盖,同时也大幅降低了通信业务中断概率,并且随着基站的死亡也能一定程度上保持网络覆盖性和连通性,是移动基站动态规划问题上的有益尝试。

文中的仿真实验力求贴近实际网络情况,得到的仿真结果可以作为搭建实物网络的参考。该方法在覆盖和连通率上的优异表现,充分证明了该方案在基站再部署问题中的优异性能,为基站再部署问题提供了一个新的解决思路。后续的研究工作可以在此基础上进行实物网络的仿真验证,或者结合其他方法如遗传算法、神经网络法等对上述方案进行改进,进一步提升其性能。

本方案虽然是针对移动基站设计的,但在类似研究中诸如智能机器人、传感器网络等场景中也是适用的,具有较好的扩展性,也可以为相关研究提供一定参考。

[1]Khatib O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,20(3):197-243.

[2]Howard A,Matari M J,Sukhatme G S.Mobile sensor network deployment using potential field:a distributed scalable solution to the area coverage problem[C]//Proceedings of the 2002 International Conference on Distributed Autonomous Robotic Systems.Fukuoka,Japan:IEEE,2002:299-308.

[3]Poduri S,Sukhatme G S.Constrained coverage for mobile sensor networks[C]//Proceedings of the 2004 IEEE International Conference on Robotics and Automation.Barcelona,Spain:IEEE,2004:165-171.

[4]Zou Y,Chakrabarty K.Sensor deployment and target localizationbased on virtual forces[C]//Proceedings of the T wenty-Second Annual Joint Conference of the IEEE Computer and Communications.San Francisco,USA:IEEE,2003:1293-1303.

[5]Zou Y,Chakrabarty K.Sensor deployment and target localization in distributed sensor networks[J].ACM Transactions on Embedded Computing Systems,2004,3(1):61-91.

[6]刘丽萍.无线传感器网络节能覆盖[D].浙江:浙江大学,2007.LIU Li-ping.Energy-efficient coverage in wireless sensor network[D].Zhejiang:Zhejiang University,2007.(in Chinese)

[7]Wang X,Wang Chen,Ma J J.An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment[J].Sensors,2007(7):354-370.

[8]Tan L,Yu C C,Yang M H.Self-deployment algorithm of mobile sensor network based on uniform density cluster[C]//Proceedings of Wireless Communications Networking and Mobile Computing.Chengdu,China:IEEE,2010:1-4.

[9]Yang M H,Cao Y D,Tan L,et al.An enhanced self-deployment algorithm in mobile sensor network[C]//Proceedings of the 2008 International Seminar on Future Information Technology and Management Engineering.Leicestershire,England:IEEE,2008:572-576.

[10]任孝平,蔡自兴,任清雄.四种虚拟力模型在传感器网络覆盖中的性能分析[J].信息与控制,2010,39(4):441-445.REN Xiao-ping,CAI Zi-xing,REN Qin-xiong.Performance analysison four virtual force models usedfor coverage algorithm of wireless sensor networks[J].Information and Control,2010,39(4):441-445.(in Chinese)

[11]Kribi F,Minet P,Laouiti A.Redeploying Mobile wireless sensor networkswith virtual forces[C]//Proceedings of 2nd IFIP Wireless Days.Venice,Italy:IEEE,2009:1-6.

[12]Xie L P,Zeng J C,Cui Z H.Using artificial physics to solve global optimizationproblems[C]//Proceedings of the 8th IEEE International Conference on Cognitive Informatics.Hong Kong:IEEE,2009:502-508.

[13]Liu Hai,Chu X W,Leung Y W,et al.Simple movement control algorithm for bi-connectivity in robotic sensor networks[J].IEEE Journal on Selected Areas in Communication,2010,28(7):994-1005.

[14]邹磊,蔡自兴,任孝平.基于虚拟力的自组织覆盖算法[J].计算机工程,2010,36(14):92-95.ZOU Lei,CAI Zi-xing,REN Xiao-ping.Self-organization Coverage Algorithm Based on Virtual Force[J].Computer Engineering,2010,36(14):92-95.(in Chinese)

[15]宋光明,庄伟,魏志刚.用于未知环境的移动传感器网络自部署算法[J].华南理工大学学报,2006,34(9):26-30.SONG Guang-ming,ZHUANG Wei,WEI Zhi-gang.Self-deployment algorithm for mobile sensor networks in unknown environment[J].Journal of South China University of Technology,2006,34(9):26-30.(in Chinese)