传感器网络移动中继节点部署算法

张 华,姚嘉鑫,吴朝云

（1.四川旅游学院信息技术系，四川 成都 610100；2.电子科技大学计算机科学与工程学院，四川 成都 611731）

传感器网络移动中继节点部署算法

张 华1,姚嘉鑫1,吴朝云2

（1.四川旅游学院信息技术系，四川 成都 610100；2.电子科技大学计算机科学与工程学院，四川 成都 611731）

针对传感器网络节点能量有限性及节点能量消耗不匀性问题，提出一种移动中继节点部署算法。首先假设网络中没有移动中继节点时，对静态节点提出一种最优路由树算法来构建数据传输路径；在此基础上再采用贪婪算法增加移动节点改善网络的拓扑结构提高路由树连通性；接着提出一种高效的分布式迭代算法，使得路由树的拓扑结构收敛于最优位置；最后进行理论分析与仿真实验，结果表明该方法具有一定理论意义与实用价值。

传感器网络；移动中继节点；寿命；贪婪算法

0 引 言

随着网络技术的进步和物联网的发展，无线传感器节点在各种监测中得到应用，如现代农业、林业、气象、环境、家居等[1-2]。由于传感器节点的存储容量有限，所采集的各种数据需要发送到基站进行存取和分析，而在传感器能量消耗的各个环节中，发送数据消耗能量最大，数据密集型无线传感器网络面临的主要挑战是减少传感器节点的能量消耗，对节能研究具有重大的意义。

一些学者利用节点的移动性，提出了一些降低无线传感器网络能量消耗的算法[3-12]。如移动节点可以通过机器人方式来回移动收集静态节点传递的数据[3-5]，再通过单跳或者多跳方式把相关数据发送给使用终端或者中心服务器[6-7]。另外移动节点也可以被用来作为中继器，转发从源节点到基站的数据，文献[8-9]专门研究了移动中继器的运动策略。以

上文献的移动节点能量供应方式存在一些问题。首先在网络的总体能量消耗中没有考虑移动节点运动时所消耗的能量，通常的做方法是认为移动节点的能量是有补充的[4]，在现实情况中，这并不总是可行的（如物理环境的限制）；再就是认为移动节点的计算能力是万能的，可以反复计算最优运动路径和改变它们的位置、方向、移动速度[4-5，10-11]。这种能力通常在现有低成本的移动传感器平台难以提供支持，例如，使用8位CPU和小电池供电Robomote[12]节点最多只能够运动25min。

针对以上问题，本文使用一次性廉价的移动中继来实现以上功能，并减少传感器网络的总体能量消耗。思路为移动节点沿着从基站到数据收集节点的路径移动到网络拓扑结构需要连通的位置，然后保持静止，这样通信延迟可以得到显著提高，且每个移动节点不像其他算法需要反复重定位。在整个算法中，先比较了不同的初始树的构建方法，提出一种最佳的树的构建策略，再设计移动中继节点的插入算法及路由树的优化算法，最后对现有的移动中继节点和静态传感器能量模型平台为基础进行了大量的仿真。

1 问题定义

1.1 能量消耗模型

移动传感器节点能量消耗主要体现在发送或者接收数据、计算和移动3个方面，其中通信和移动是能量消耗的主要环节。而对节点的各种状态而言，空闲侦听、休眠调度也是消耗能量重要的组成部分[13]，本文将重点放在减少数据传输和节点移动的能量消耗，通过移动中继器作为静态节点数据的转发节点，来减少总体能量的消耗。移动中继传感器节点选择采用差分驱动器技术的轮式传感器节点（如Khepera[14]，Robomote[12]和FIRA[15]），这种类型的节点通常有两个轮子，每个轮子由独立的发动机控制。能量模型采用文献[15]所提出的移动单位距离消耗模型，为中继节点移动时消耗的能量，如式（1）所示。

式中：EM（d）——中继节点M移动距离d所消耗的能量；

k——参数，主要由节点移动的速度决定。

在文献[15]中，作者对节点移动速度与能量消耗关系作了专门研究，当k取值为2时，达到最优值。数据传输能量消耗模型，如式（2）所示。

式中：ET（d）——节点T发送数据到达距离d的地方所消耗的能量；

m——发送数据包的大小；

a，b——参数，由环境因数决定。

1.2 数学模型

假定所有的动作都是在网络收集数据传输开始前完成，并没有障碍影响变速器的工作。同时，假设所有的移动节点知道自己的起始位置，都安装GPS单元为网络定位提供服务，每个移动节点和移动相应的距离都不超过移动中继器预定范围，此外在移动节点更改网络拓扑结构时，不考虑网络短暂的延迟。本文面向的是一个2D平面（R2），但其结果可应用在R3、R4、多维平面。

问题描述如下：整个网络由3部分节点组成，一个或者多个数据汇聚节点，大量的移动中继节点和大量的静态数据采集节点。从数据汇聚节点开始构造一个方向路由树，同时在这个静态的方向性路由树里面插入移动中继节点对路由结构树优化，使得数据在传输中网络的能量消耗最少。整个网络可定义如下：S={s1，s2，s3，…，sn}表示整个网络中的n个节点，O={o1，o2，o3，…，on}表示整个网络中可放置节点的n个位置，oi是节点si的初始位置，且满足条件i∈（1，…，n）；整个网络的能量消耗主要由两部分组成，节点移动消耗的能量加上数据传送的能量，如式（3）所示。

其中c（＜E，U＞）表示整个网络能量的消耗，它由两部分组成：E为构架方向性路中树移动节点S移动时所需要消耗的能量；U表示各位置节点传输数据时消耗能量。根据上面的定义，把相关符号代入式（3），整个网络的能量消耗数学模型如式（4）所示。其中式（4）表示由第i个节点移动至第j个节点过程中系统消耗的总能量。

2 移动中继节点部署算法

最佳移动中继配置问题依赖多种因素，如路由树的拓扑结构及通过每个链路传送的数据量。当传送小数据时，最佳的配置位置是中继节点在它们的原始位置，这样就不会产生中继节点移动消耗的能量；传输的数据量大时，不能再采用此方法，会导致节点能量过早用尽，因此需要添加新的中继节点，改变拓扑结构来达到节能的效果，而中继节点移动到什么位置才最节能是需要解决的主要问题。解决的方法分为3步：首先不考虑中继节点，按照能量传输模型建立路由

树；再根据数据量的大少决定是否插入中继节点及插入在什么位置；最后对拓扑路由树进行处理。

2.1 静态路由树构造

利用最短路径树方法来构建路由树的拓扑结构，首先以通信能量消耗模型为依据定义一个通信权值w，从而可得到在网络中任意两个节点si，sj传递数据时所消耗的能量值，如式（5）所示。

以Sink节点为中心，以式（5）为基础寻找最近的节点加入到路由结构树集合S′中，再以集合S′为基础，添加其他节点，一直到所有节点加入为止，具体过程如图1所示。

2.2 移动中继节点的插入及路由树的优化

利用贪婪算法添加节点来改造静态路由树的拓扑结构，定义Sout={sout，1，sout，2，…，sout，n}为移动中继节点的集合，且不在静态路由树的节点中。如果静态节点si，sj之间需要增加一个中继来转发数据，定义最理想位置为O（x，y）。需要对加入中继节点前后的能量消耗进行对比，如果优于前，则加入中继节点，否则不加入，如式（6）～式（8）所示。

式（6）主要是用来计算不插入中继节点时，节点si向节点sj发送mi，j个数据包所消耗的能量，式（7）为计算插入中继节点后所消耗的能量，式（8）主要用来比较哪种方式更节能。如果式（8）大于“0”则插入中继节点，否则不插入。

经过式（8）计算后，两个节点之间能够找节能的路由方式，但在整个网络中可能出现有多个节点靠近移动中继节点，如何使整个网络节能，这是下一步对路由树的优化问题。首先如式（9）所示对mi进行计算，同时计算所有可能的路径，并分别求X轴、Y轴偏导数，并设他们的结果为“0”，如式（10）～式（11）所示。

其中A，Bx，By取值如式（12）～式（14）所示。

3 仿真实验及测试

在整个网络结构中，随机产生100个网络拓扑结构，每个网络拓扑结构中存在100个节点，覆盖面积为150m×150m的区域，每个区域存在1个Sink节点及10～20个随机的移动中继节点。取各种结果的平均值为测试结果。先测试传送数据量的改变对算法的影响，再测试移动中继节点移动距离改变对算法的影响，最后测试两者都改变对算法的影响。

移动中继的距离是自动计算出来的，在整个测试中不好改变，所以设计的方案为改变其节点的数量，移动节点数量从4个增加到20个，每个节点发送的数据包的大小为1～150MB。在环境配置方面，令a= 0.6×10-7，b=4×10-10，作为环境配置。移动中继节点的设置分为两步，先令k=2，再分别令k=1，2，4[13-15]。由于本文所提出的是一种网络拓扑结构的优化方案，为了便于比较，采用常用的3种路由算法（powerbased、hop-based、greedy geographic）来测试网络的性能。power-based路由算法（简称pb）为Sink节点到数据收集节点最短距离路径传递算法，所消耗的

能量为数据传递时节点之间传送的能量消耗和。hop-based路由算法（简称hb）为Sink节点到数据收集节点最少跳数的路径为路由路径。greedy geographic路由算法（简称gg）为贪婪路由算法，在通信范围内每次选择到达Sink节点最近的节点为传送数据节点。

图2为采用本网络拓扑结构后，能量消耗与以前pb、hb、gg采用的网络拓扑结构能量消耗情况的比较。从图2中可以看出，在传输少量数据时，pb以前采用的模型与本文提出的模型能量消耗一样，hb,gg则要优于本文方法，主要原因在于，这个模型需要移动中继节点，因此需要消耗能量；当数据量大时，采用提出的模型比其他的模型要节能很多，当数据过150MB时，节能量超过40%。

图3为网络拓扑结构模型优化前后能量消耗对比。可以看出数据量少时，能量节约值不大，当数据量超过150MB时，能量可节约70%左右。从图2、图3中可以看出，不管是pb、hb、gg哪一种路由算法，当长时间收集数据且是收集大量数据时，本文所提出来的模型优于同类型的网络拓扑结构。

图4、图5是随中继节点数量的增长k取不同值集中式算法与分布式算法能量消耗情况分析，图4与图5都说明了当k的值越大，则节约的能量越少，k的值越小，则节约的能量越多；同时也发现分布式算法最大节能量只是以前的50%，而集中式算法最多可以节约能量60%，且k取相同值时集中式算法节约能量要比分布式算法多。经过原因分析及结果追踪知道，采用分布式算法本身消耗的能量比较低，所以不管采用什么办法都很难再节能太多，在整个能量消耗方面分布式算法的能量消耗要低于集中式算法。

4 结束语

本文提出利用移动中继器节点来改善网络的拓扑结构，从而全面减少网络的总能量消耗。当整个网络中没有移动中继节点时，先提出一种最优路由树算法，构造一个网络路由树，再采用贪婪算法增加移动节点改善网络的拓扑结构提高了路由树连通性，接着提出高效的分布式迭代算法，使得路由树的拓扑结构收敛于最优位置，最后进行理论分析与仿真实验，结果表明有一定理论意义与实用价值。

[1]Szewczyk R，Mainwaring A，Polastre J，et al.An Analysis of a large scale habitat monitoring application[C]∥ Poc second ACM Conf on Embedded Networked Sensor Systems，2004.

[2]Luo L，Cao Q，Huang C，et al.EnviroMic：towards cooperative storage and retrieval in audio sensor networks[C]∥ Proc 27th Int’l ConfDistributed Omputing Systems，2007.

[3]邬厚民.无线传感网络中能量和距离改良的LEACH分簇算法[J].中国测试，2012，38（5）：62-65，101.

[4]Kansal A，Jea D D，Estrin D，et al.Controllably mobile infrastructure for low energy embedded networks[J]. IEEE Trans Mobile Computing，2006，5（8）：958-973.

[5]Xing G，Wang T，Jia W，et al.Rendezvous design algorithmsfor wirelesssensor networks with amobile base station[J].Proc ACM Mobihoc，2008：231-240.

[6]Shah R，Roy S，Jain S，et al.Data mules：modeling a three-tier architecture for sparse sensor networks[C]∥Proc IEEE First Int’l Workshop Sensor Network Protocols and Applications，2003.

[7]Jain S，Shah R，Brunette W，et al.Exploiting mobility for energy efficient data collection in wireless sensor networks[J].Mobile Networks and Applications，2006，11（1）：327-339.

[8]Wang W，Srinivasan V，Chua K C.Using mobile relays to prolong the lifetime of wireless sensor networks[C]∥Proc ACM Mobicom.Cologne，2005.

[9]Goldenberg D K，Lin J，Morse A S.Towards mobility as a network control primitive[C]∥ Proc ACM Mobihoc，2004：163-174.

[10]Somasundara A A，Ramamoorthy A，Srivastava M B. Mobile element scheduling with dynamic deadlines[J]. IEEE Trans Mobile Computing，2007，6（4）：395-410.

[11]Gu Y，Bozdag D，Ekici E.Mobile element based differentiated message delivery in wireless sensor networks [C]∥Proc Int’l Symp World of Wireless,Mobile and Multimedia Networks，2006.

[12]Dantu K，Rahimi M，Shah H，et al.Robomote：enabling mobility in sensor networks[C]∥Proc Fourth Int’l Conf.Information Processing in Sensor Networks，2005.

[13]Wang L，Xiao Y.A survey of energy-efficient scheduling mechanisms in sensor networks[J].Mobile Networks and Applications，2006（11）：723-740.

[14]Kim J H，Kim D H，Kim Y J，et al.Soccer robotics[M]. Germany：Springer，2004.

[15]Wang G，Irwin M J，Berman P，et al.Optimizing sensor movement planning for energy efficiency[C]∥Proc Int’l Symp Low Power Electronics and Design，2005：215-220.

4 结束语

从理论分析和试验结果可以看出，通过多个滤波器的并行拼接达到了提升滤波器速度的效果，现有方法设计的滤波器在FPGA中可以实现200～300MHz的工作速度。按本文的方法，如果P=4，则可以使最终滤波器的速度达到800～1200MHz，其速度达到了成倍增加的效果，如果再增加P值，会进一步提升FIR滤波器的速率，也为将来更加广泛的应用奠定了坚实的基础。

参考文献

[1]Ludwig R，Bogdanov G.射频电路设计：理论与应用[M].北京：电子工业出版社，2005：192-194.

[2]陈树新.数字信号处理[M].北京：高等教育出版社，2005：45-46.

[3]赵文亮，蒋冰.基于FPGA的高阶高速FIR滤波器设计与实现[J].中国有线电视，2006（3-4）：329-331.

[4]汤宁生，黄建国，王志刚.一种200 MHz处理速度的FIR滤波器设计[J].微计算机信息，2007（3）：183-187.

[5]杨鸿武，丁朋程，王全州.基于FPGA的高速全并行FIR滤波器的设计[J].西北师范大学学报，2012，48（1）：48-51.

[6]何子述，夏威.现代数字信号处理及其应用[M].北京：清华大学出版社，2009：28-91.

[7]刘凌，胡永生.数字信号处理FPGA实现[M].北京：清华大学出版社，2003：251-252.

[8]张维良，张彧，杨再初，等.高速并行FIR滤波器的FPGA实现[J].系统工程与电子技术，2009，31（8）：1819-1822.

Deploy algorithm of mobile relay nodes of sensor network

ZHANG Hua1，YAO Jia-xin1，WU Chao-yun2
（1.Department of Information Technology，Sichuan Tourism University，Chengdu 610100，China；2.School of Computer Science and Engineering，University of Electronic Science and Technology，Chengdu 611731，China）

For the problems of the limitation of node energy and the imbalance of energy consumption in the sensor network，this paper puts forward a deploy algorithm of mobile relay nodes.Firstly，on the condition that there are no mobile relay nodes in the network，the optimal route tree algorithm to construct data transmission route for static nodes has been put forward;on the basis of previous research，with the help of greedy algorithm more mobile nodes are added to the route trees so as to improve the typology structure of network and to work on the connectivity of route trees；then a high efficient distributive iterative algorithm is proposed to put the typology structure of the route trees in the optimal position；finally theoretical analysis and simulated experiment manifest that this algorithm is of theoretical meaning and practical value in one sense.

sensor network；mobile relay nodes；life；gready algorithm

TP212；TP301.6；TN911.7；TP391.9

：A

：1674-5124（2014）04-0078-05

10.11857/j.issn.1674-5124.2014.04.020

2013-12-17；

：2014-02-25

四川省教育厅重点项目（12ZA280）

张 华（1977-），男，四川富顺县人，副教授，硕士，研究方向为计算机应用技术。