无线传感器网络节点移动路径优化方法

刘香爱，冯烟利

（1.山东师范大学 信息科学与工程学院，山东 济南250014；2.山东工商学院 计算机科学与技术学院，山东 烟台264005）

0 引 言

覆盖 问题是无线 传 感 器 网 络（wireless sensor networks，WSN）的基本问题。它反映了WSN对被监测区域或目标提供的感知服务能力。无线传感器网络在部署传感器时通常采用随机部署方式，所以覆盖空洞的出现是避免不了的。这会使网络的生存时间提前结束，网络中会遗留大量未被利用的能量资源。所以，在保持网络原有覆盖水平的基础上，有效地节能对传感器网络来说是非常重要的［1－6］。

在无线传感器网络中，覆盖问题的最终目的是在不降低原有覆盖水平的基础上，有效分配各节点的状态，最小化网络每轮的能量消耗，同时使每个节点平均分担网络能耗［7］。所以在移动传感器修复覆盖空洞时，确定了移动传感器的最后位置之后我们需要决定怎样把传感器移动到目标位置才能达到更好的网络覆盖效果。文献 ［9］中基本竞标协议采用直接移动（direct movement，DM）的方式，但它一般达不到网络的应用需求，浪费更多的时间，过度消耗单个传感器的能量。在文献 ［11］中提出用级联移动（cascaded movement，CM）来优化这个问题。文中详细讲述了选择中间级联节点的方法，但在选择级联移动路径时，只考虑了路径的总能耗，不能更好的均衡每个移动传感器的能耗。怎么确定最优的级联移动路径是一个值得考虑的问题。最优的级联移动路径既要平衡各传感器的能量消耗，又要减少路径的总能耗。

本文针对这个问题，对文献 ［11］中的级联移动进行了改进，在选择最优级联移动路径时，用多目标优化的方法充分考虑了各传感器间的能耗平衡。它通过减少单个传感器的能量消耗，平衡网络中传感器的能量，提高了网络的能量使用效率。

1 移动路径的优化

1.1 基本假设

本文基于以下假设：①传感器一旦被部署，将会独立工作，每个传感器的能量不能补充，即当其能量耗尽的时候，传感器则不能工作，各传感器初始能量均为E＞0；②所有传感器节点的感知半径和通信半径均相等并都为圆盘形；③所有移动传感器的移动速度均相等，用speed表示。

文中提出的改进的级联移动（improved cascaded movement，ICM），首先采用文献 ［11］的方法选择中间级联移动节点，再采用下面的方法选择最优的级联移动路径。

1.2 最优路径的选择

为了平衡网络中各传感器的能耗，各移动传感器的移动距离应大致相等，则这里假设级联移动路径中的所有移动传感器同时移动。

定义1在级联移动路径中，从任意移动传感器（包括目的移动传感器和所有中间级联传感器）开始移动到覆盖空洞修复完成所花费的时间称为路径的移动时间。

假设某条有效的级联移动路径m中，中间级联节点有n个，节点i的移动距离为dm，i。则路径m的移动时间为

其中，Tm≤T。只有当dm，i越小时，路径m的移动时间才会越小，从而缩短网络的恢复时间。

路径m总的移动长度

式中：D——需移动的移动传感器s0与目标位置s之间的距离。

在路径m上，传感器节点i移动消耗的能量

式中：e——移动传感器移动单位距离所消耗的能量。则节点i的剩余能量

移动传感器节点i的能量可用率

路径m的能量可用率

定义2决定性能量［12］：是指某条可用级联移动路径m上的所有节点的最小能量可用率，记作DEm

式中：i——路径m上的第i个节点si。

从目的移动传感器到目标位置有多条可用的级联移动路径，需要从中选出一条最优的移动路径。设P＝｛DEm＞λ，m∈M｝，其中λ为阈值，M为所有可用路径集。若则从P中选择一条路径能量可用率最大的路径

否则，从集合M中选择一条决定性能量DEm最大的路径

根据式（9），式（10），可从所有可用路径集M 中选出决定性能量大于阈值λ且路径能量可用率最大或决定性能量最大的路径，作为最优级联移动路径。阈值λ的大小可由用户根据实际应用情况来确定，一般设置为0.3。

定义3多目标优化问题的数学形式一般可以描述为［13］

解决移动传感器的级联移动路径问题提高网络能量的使用效率就是最大化路径的能量可用率或决定性能量。根据式（7），路径的能量可用率ηm是由中间级联节点的个数n和各节点的能量可用率ηm，i所决定的。而且在节点的能量可用率相对均等的情况下，路径上的中间级联节点数越多，ηm的值就越小。根据式（8），决定性能量DEm也是由各节点的能量可用率ηm，i所决定的。根据式（4）、（5）、（6），各节点的能量可用率ηm，i最终是由节点i的移动距离dm，i决定的。归根结底，解决问题的根本就需要最小化中间级联节点的个数n，并最小化各节点的移动距离。由式（2）、（3）可以看出，这是多目标优化问题。

如图1所示，采用多目标优化方法，假设从目的移动传感器s0到目标位置s存在3条可用的级联移动路径，目的移动传感器可以沿着任意一条路径移动到目的位置。

图1 级联移动路径

各节 点 的 能 量 可 用 率 ηm，i如 下：η1，A＝0.8；η1，B＝0.35；η2，C＝η2，D＝η3，G＝0.5；η3，E＝0.6；η3，F＝0.7；ηs0＝0.9。

则各级联移动路径的能量可用率ηm和决定性能量DEm分别如下：

路径1：η1＝0.9×0.8×0.35＝0.252，决定性能量DE1＝0.35；

路径2：η2＝0.9×0.5×0.5＝0.225，决定性能量为DE2＝0.5；

路径3：η3＝0.9×0.6×0.7×0.5＝0.189，决定性能量为DE3＝0.5。

按照式（9）和（10）的路径选择规则，由于路径2和路径3的决定性能量DEm大于λ，因此最优级联移动路径将在路径2和路径3中产生。其中，η2大于η3，所以路径2成为传感器移动修复覆盖空洞的最优路径。从上面计算中可以看出，路径1的ηm最大，然而由于DE1不大于λ，则路径1被排除；路径3上各节点的ηm，i虽然均大于或等于路径2上的ηm，i，但是由于中间级联节点数量较多，最后的η3小于η2。

由此，该级联移动策略不仅保护了路径上的低能量节点，而且考虑了节点平均剩余能量和较少的中间级联节点个数作为路径选择的可行性。这样，在目的移动传感器进行移动修复WSN覆盖空洞时，当前能量均衡的、健壮的、中间级联节点个数少的路径就会胜出，成为移动传感器的移动路径，从而使传感器间的能量消耗相对均衡，有效地延长网络的生存时间。

2 仿真实验

目标区域是一个30 m×30 m的矩形，在区域内随机混合部署一定数量的移动节点和静态节点。假设传感器节点总数为50个，移动传感器的百分比从10%变化到50%。实验在目标区域内随机产生不同大小的闭合的覆盖空洞。通过仿真比较了CM与ICM在能量使用效率方面的性能。

在无线传感器网络中，网络能耗主要是由传感器的移动和通信造成的。图2比较了CM与ICM平均移动距离情况。CM只从总能耗方面选择级联移动路径，至于涉及的移动传感器的平均能耗不能得到优化。移动传感器的平均能耗主要是由它们的平均移动距离决定的。另外，由于ICM需要明确计算级联移动路径的能量，所以它的消息复杂度较之直接移动明显增加了，如图3所示。

但是，移动传感器移动1m消耗30J能量，而发送1字节消息只消耗0.1J能量。也就是说，移动传感器移动1m消耗的能量是发送1字节消息所耗能量的300倍。所以，在无线传感器网络中，消息复杂度对网络能耗的影响极小，可以不予考虑。图4给出了两种移动方式下无线传感器网络能量使用效率随移动传感器所占比例的变化情况。无线传感器网络中能量使用效率与网络生存时间密切相关。从而，级联移动大大延长了网络生存时间。

3 结束语

针对移动传感器修复无线传感器网络中的覆盖空洞问题，本文对级联移动作了进一步的改进。在选择级联移动路径时，通过节点的剩余能量精确计算了路径的能量可用率，引入了路径的决定性能量的概念，并结合了多目标优化的思想，充分考虑了各移动传感器间的能耗平衡。它通过减少单个移动传感器的能量消耗，平衡网络中传感器的能量，提高了网络的能量使用效率。最后，通过仿真实验验证了改进方法的有效性和优越性，网络的能量使用效率得到明显提高，延长了WSN的生存时间。

［1］Ghosh A，Sajal K D.Coverage and connectivity issues in wireless sensor networks：A survey ［J］.Pervasive and Mobile Computing，2008，4（3）：303－334.

［2］REN Yan，ZHANG Sidong，ZHANG Hongke.Theories and algorithms of coverage control for wireless sensor networks ［J］.Journal of Software，2006，17（3）：422－433（in Chinese）.［任彦，张思东，张宏科.无线传感器网络中覆盖控制理论与算法 ［J］.软件学报，2006，17（3）：422－433.］

［3］Jennifer Yick，Biswanath Mukherjee，Dipak Ghosal.Wireless sensor network survey ［J］.Computer Networks，2008，52（12）：2292－2330.

［4］LIU Benyuan，Towsley D，Dousse O，et al.Mobility improves coverage of sensor networks ［C］.New York，USA：Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005：300－308.

［5］Sudip Misra，Subhas Chandra Misra，Isaac Woungang.Guide to wireless sensor networks ［M］.London：Springer，2009：47－79.

［6］HU Yaofeng，ZHANG Jianming，WANG Xinsheng，et al.Research on energy－aware multi－path routing protocol in wireless sensor network ［J］.Computer Engineering and Design，2009，30（21）：4811－4814（in Chinese）. ［胡耀锋，张建明，王新胜，等.能量感知的无线传感器网络多路径路由研究 ［J］.计算机工程与设计，2009，30（21）：4811－4814.］

［7］MAO Yingchi，LIU Ming，CHEN Lijun，et al.A distributed energy－efficient location－independent coverage protocol in wire－less sensor networks ［J］.Journal of Computer Research and Development，2006，43（2）：187－195（in Chinese）. ［毛莺池，刘明，陈力军，等.DELIC：一种高效节能的与节点位置无关的传感器网络覆盖协议 ［J］.计算机研究与发展，2006，43（2）：187－195.］

［8］WANG Bang，Hock B L，MA Di.A survey of movement strategies for improving network coverage in wireless networks［J］. Computer Communications， 2009， 32（13－14）：1427－1436.

［9］WANG Guiling，CAO Guohong，Berman P，et al.Bidding protocols for deploying mobile sensors［J］.IEEE Transactions on Mobile Computing，2007，6（5）：563－576.

［10］SU Han，WANG Yun.A self－healing algorithm without location information in sensor networks ［J］.Chinese Journal of Computers，2009，32（10）：1957－1970（in Chinese）.［苏瀚，汪芸.传感器网络中无需地理信息的空洞填补算法 ［J］.计算机学报，2009，32（10）：1957－1970.］

［11］WANG Guiling，CAO Guohong，TOM L P，et al.Sensor relocation in mobile sensor networks ［C］.Miami，FL，USA：INFOCOM，2005：2302－2312.

［12］FAN Zhigang.Research on coverage and node deployment in wireless sensor networks ［D］.Chengdu：University of Electronic Science and Technology of China，2008（in Chinese）.［凡志刚.无线传感器网络覆盖与节点部署问题研究 ［D］.成都：电子科技大学，2008.］

［13］Sumanl B，Kumar P.A survey of simulated annealing as a tool for single and multiobjective optimization ［J］.Journal of the Operational Research Society，2006，57（10）：1143－1160.