基于混合基站策略的传感器网络移动数据收集算法

刘 逵，刘三阳

（1.河南师范大学 数学与信息科学学院，河南 新乡453002；2.西安电子科技大学 数学与统计学院，西安710071）

0 引 言

由于传感器节点的工作环境通常比较恶劣，因此替换节点的电池或对电池进行充电都十分困难，所以如何有效利用节点的有限能量［1－3］，从而最大化地延长网络寿命就变得至关重要。在监控区域中部署移动基站［4－7］来收集数据信息是延长网络寿命的一个重要手段。这是因为移动基站通过在监测区域内部巡回移动，可避免近基站节点的过早死亡而引发的路由空洞问题，同时在监测区域中引入移动基站还可以有效减小网络中数据的传输距离，进而减少网络的通信能耗。目前在移动基站方面的研究已有许多成果，如文献［8］提出的Data Mules策略就是基于移动基站思想设计的。Data Mules策略是将基站固定在人或动物等移动载体上，然后采用随机行走的方式在监控区域内移动并就近收集节点采集到的数据信息，但由于移动载体是无序运动的，从而造成网络的通信延迟过大。文献［9］提出了一种沿固定轨迹周期运行的基站移动策略。这种沿固定轨迹周期运行机制可以帮助网络监控者收集到监控盲区内的数据信息，但却无法保证信息的适时性。

针对移动基站在无线传感器网络应用中存在的弊端，本文提出了一种混合基站策略的网络数据收集算法。该方法有效解决了无线传感器网络中节点能耗不均衡及通信延迟过大的问题，进而达到了延长网络寿命、保证采集数据适时性的目标。同时本文所提算法还采用了一种中途数据拦截策略，这种策略可以有效减少网络内中转数据的传输距离，从而提高数据在传输过程中的安全性。

1 网络模型

网络部署在一个正方形监控区域内，区域内各节点均被分配一个ID 号，节点利用无线通信装置与其一跳通信范围内的邻居节点进行局部信息传输，然后以多跳中继的方式将数据传输给基站。网络中配备了两个基站（一个移动基站和一个固定基站），固定基站被网络操控者固定在监控区域的边界，充当网络的数据汇聚门户；移动基站被固定在一个自动移动装置上，充当网络的移动数据收集者。同时移动装置上配备有定位装置，可供移动基站适时了解自己的位置信息，然后根据监控区域的边界自动修正运动状态。在基站的软硬件配置方面，移动基站和固定基站一样，拥有相同的存储、计算和通信能力。

本文中假定移动基站采用随机行走的移动策略，并用函数Mr来描述移动基站的移动状态。移动基站每次转移之前，函数Mr首先采用随机数生成法在区间［－π，π］内生成一个角γ，并将这个角定义为移动基站下一时刻的移动方向。移动基站的运动速度始终保持恒定，同时为了确定移动基站将来的位置，函数Mr将在区间［dmin，dmax］内随机选取一个数作为移动基站在方向γ上的移动距离。如果移动基站的新位置落在了监测区域以外，则函数Mr将促使移动基站沿原路后退，直至退到监测区域的边界。移动基站每到一个位置，就开始利用局部查询信息构建网络的以移动基站为根的有限衍生树，如图1所示，该有限衍生树的层数由局部查询信息的挖掘深度唯一决定。

图1 以移动基站为根的有限衍生树Fig.1 Limited propagation tree with the mobile sink as root

节点的能耗模型采用文献［10］中的模型，同时网络内各节点均要建立并维护一张邻居信息表并存储如下信息：节点本身及其邻居节点的ID号；节点本身及其邻居节点的剩余能量信息；节点本身及其邻居节点的地理位置信息；节点到达固定基站的最优路由信息，包括该路径从固定基站出发依次途经各节点的ID 号字符串seqn1和该路径的最优路径度D；节点到达移动基站的最优路由信息，包括该路径从移动基站出发依次途经各节点的ID 号字符串seqn2、该路径的最优路径度Dc和其最后更新时刻tu。

本文采用文献［11］中的最优路径评定标准，该标准侧重考虑了网络中各节点的负载均衡性，防止过度使用某些关键节点而导致其过早坏死，进而引起网络割裂。标准如下：

式中：λ1、λ2、λ3均为非负偏向参数，通过对其调控来实现对各变量的偏向程度调整；σ 为路径上各节点剩余能量的标准差；E1为路径上的能量总消耗；E2为路径上节点的平均剩余能量；E3为路径上节点中的最小剩余能量。

2 混合基站策略的网络数据收集算法

本文设计一种混合基站策略的网络数据收集方法，该策略在网络中布置了两种不同类型的基站。其中固定基站充当网络数据的汇聚门户，移动基站作为网络的移动数据收集者。移动基站每到达一个新位置，即采用查询信息来构建局部数据采集最小路径树，该树的大小由查询信息的网络挖掘深度唯一决定。实践表明［12］，局部查询信息的挖掘深度设定为网络最优路径平均跳数的三分之一时，取得的效果最为显著。局部数据采集最小路径树上的节点，如有信息需要发送，则立刻沿着该树将信息发送给移动基站，同时树上节点均开始倒计时，当到达事先设定的时间阈值时，该树失效。网络中不在局部数据采集最小路径树上的节点如有数据需要传输，则将沿着该节点路由列表中存储的到固定基站的最优路径逐级传输给固定基站。如果途经节点在局部数据采集最小路径树上，则途经节点会对中转数据进行拦截，即将接收到的数据按其路由列表中存储的到移动基站的路由进行转发，进而缩短网络数据的传输距离，提高网络中数据的安全性和适时性。

2.1 路由初始化

固定基站周期性地向网络中发布查询信息进行路由初始化。查询信息携带有记录途经各节点ID 号的字符串seqn、途经各节点的平均剩余能量和途经路由的最优度D1。路由初始化时刻，固定基站不停向网络里广播查询信息。当节点收到查询信息后，节点将会利用从查询信息中释放出的数据及其自身邻居表中存储的数据计算该查询信息到达此节点所经路径的最优路径度D1，并将D1与自身邻居表中存储的Ds（Ds的初始值为∞）进行比较，进而决定是否更新邻居列表中存储的到固定基站的路由信息，路由初始化的伪代码如下：

A＝［］；%记录查询信标途经节点剩余能量的矩阵

seqn＝［］；%记录查询信标途经节点ID 号的字符串

E1；%查询信标途经路由的总能耗

Eij；%节点i和节点j之间的通信能耗

e1；%节点i的剩余能量

Algorithm 1

／＊node i receive a setup beacon message come from the node j＊／

2 updates the information contain by this setup beacon message

3 A＝［A，ei］；seqn＝［seqn，IDi］；E1＝E1＋Eij；E3＝min（A1，A2，…，Astze（A））；

4 E2＝sum（A1，A2，…，Astze（A））／size（A）；

5 σ＝sqrt（（A1－E2）＾2＋（A2－E2）＾2＋，…，＋（Astze（A）－E2）＾2）

6 D1＝sqrt（λ1＊σ＾2＋（λ2＊E1／λ3＊E2＋λ4＊E3）＾2）；

7 if（D1＜D5）

8 node i will update its route optimal level by assigning D5＝D1；

9 node i will update the old seqn1by assigning seqn1＝seqn；

10 node i will broadcast this setup beacon message to its neighbors；

11 else if（D1＝D5）

12 node i compare size（seqn1）with size（seqn）

13 if（size（seqn1）＞size（seqn））

14 node i will update the old seqn1 by assigning seqn1＝seqn；

15 node i will broadcast this setup beacon message to its neighbors；

16 else

17 node i drops this beacon message packet；

18 end

19 else

20 node i drops this beacon message packer；

21 end

22 end

如果D1＜Ds，那么接收节点将开始更新其存储的到固定基站的路由信息：首先更新最优路径度，将D1赋值给Ds；其次更新记录的最优路径，将字符串seqn赋值给seqn1。结束后，接收节点开始更新查询信息中存储的数据：首先将其ID 号存储到字符串seqn尾端第一个空格中，然后将其剩余能量信息也加入到该查询信标中，最后按能耗公式计算并更新查询信标中存储的由字符串seqn记录的路由总能耗。接收节点更新完查询信息后，即向其邻居节点广播该查询信息。

如果D1＝Ds，那么该接收节点首先从查询信息中提取出字符串seqn，然后比较其邻居表中存储的字符串seqn1与字符串seqn的长度。如果字符串seqn的长度大于字符串seqn1的长度，那么接收节点丢弃该查询信息；否则，接收节点将首先更新其存储在邻居表中的最优路径信息，将字符串seqn赋值给seqn1。然后更新查询信息，并向其邻居节点广播该查询信息。

如果D1＞Ds，接收节点丢弃这个查询信息。初始化结束之后，网络中各节点均形成并各自维护一张存储有到固定基站最优路径信息的邻居表。

2.2 构建局部数据采集最小路径树

移动基站每到达一个新位置就开始广播查询信标来构造新的最小路径树。查询信标中携带有如下信息：移动基站的有效停留时间tthres、查询信标的剩余转发次数ttl、记录途经各节点ID 号的字符串seqn0、途经各节点的平均剩余能量和所经路径的最优度D2。网络中各节点均保存有其到移动基站的最优路径度Dc，Dc的初始值为∞，同时设置一个时间戳tu来记录Dc的上次更新时刻。当节点在时刻tb接收到查询信标，则节点将利用其邻居表中存储的信息和从查询信标中释放出的信息来计算该查询信标所经路由的路径度D2，然后决定是否更新其到移动基站的路由信息。构建最小路径树算法的伪代码如下：

tb：% 查询信标被接收时的时刻

ttl：% 时间戳

tthres：% 局部衍生树有效寿命

Algorithm2

／＊node i receive a beacon message come from the node j＊／

1 if a beacon message is received by node i

2 updates the information contain by this setup beacon message

3 A＝［A，ei］；seqn0＝［seqn0，IDi］；E3＝min（A1，A2，…，Asize（A））；

4 E1＝E1＋Eij；E2＝sum（A1，A2，…，Asize（A））／size（A）；

5 σ＝sqrt（（A1－E2）＾2＋（A2－E2）＾2＋，…，＋（Asize－E2）＾2；

6 D2＝sqrt（λ1＊σ＾2＋（λ2＊E1／λ3＊E2＋λ4＊E3）＾2）；

7 if（D2＜Dc）

8 node i will update its route optimal level by assigning Dc＝D2；

9 node i will update the old seqn2by assigning seqn2＝seqn0；

10 node i will assign tu＝ib and assign ttl＝ttl－1；

11 if（ttl＞0）

12 node i broadcasis this beacon message to its neighbors；

13 else

14 node i drops this beacon message packet；

15 end

16 else if（D2≥Dcand tb＞tb＋tthres）

17 node i will update its route optimal level by assigning Dc＝D2；

18 node i will update the old seqn2by assigning seqn2＝seqn0；

19 node i will assign tu＝ib and assign ttl＝ttl－1；

20 if（ttl＞0）

21 node i broadcasis this beacon message to its neighbors；

22 else

23 node i drops this beacon message packet；

24 end

25 else

26 node i drops this beacon message packer；

27 end

28 end

如果D2＜Dc，则接收节点将首先更新其到移动基站的最优路径信息：将D2赋值给Dc、将tb赋值给时间戳tu、将字符串seqn0赋值给seqn2；然后按如下规则更新查询信标中存储的信息：将其ID号存储在字符串seqn0尾端第一个空格中；将剩余能量信息相应加入到该查询信标中；计算并更新查询信标中存储的由字符串seqn0记录的路由总能耗；按公式解ttl＝ttl－1修正查询信标的剩余转发次数。如果修正后的ttl值大于零，则接收节点向其邻居节点广播该查询信标；否则接收节点丢弃此查询信标。

如果D2≥Dc且tb＞tu＋tthres，则接收节点首先开始更新其到移动基站的最优路径信息：将D2赋值给Dc，将tb赋值给时间戳tu，将字符串seqn0赋值给seqn2；然后接收节点更新查询信标，并借助剩余转发次数ttl来判断是否转发该查询信标。

如果D2≥Dc且tb≤tu＋tthres，则接收节点丢弃此查询信标。查询过程结束时形成一个由移动基站为根的局部数据采集最小路径树，局部数据采集最小路径树的大小由网络操控者事先设定好的查询信标转发数ttl确定。

2.3 网络数据收集过程

网络中各节点均保存着其到达不同基站的最优路径信息，当节点有数据需要传输给基站时，节点首先要判断当前是否存在通往移动基站的有效路由。例如网络中节点A 有数据需要传输给基站时，节点A 首先需要核查其邻居表中存储的信息来判断是否存在有通往移动基站的有效路由。如果A 邻居表中存储的到移动基站的最优路径度Dc≤∞且tb＜tu＋tthres，则说明此刻节点A 在以移动基站为根的局部数据采集最小路径树上，因此节点A 将沿着其邻居表中存储的到移动基站的最优路径把数据逐级传输给移动基站。如果节点A 邻居表中存储的到移动基站的最优路径度Dc＝∞或Dc≤∞，但tb＞tu＋tthres，则说明此刻节点A 没有通往移动基站的有效路径。因此节点A 需要沿着其存储的到固定基站的最优路径将数据逐级传输给固定基站。数据传输途中，如果途经节点处在以移动基站为根的网络局部数据采集最小路径树上，则该途经节点将会对传输过来的数据进行拦截，并将拦截到的数据转发给移动基站。借助这种策略可将途经局部数据采集最小路径树上节点的数据进行有效拦截，进而减少网络的通信延迟和近基站节点的数据转发量。数据收集算法的伪代码如下：

t；%

tu；%

Algorithm 3

1 star＝false

2 while star＝false

3 the node whick has data packets to relay to the sinks extract the local

4 information like Dctu，ttherstored by itself；

5 if（Dc＜∞＆t＜tu＋tther）

6 this node will relay data packets to the mobile sink along the route

7 recording by seqn2 whick is stored by itself；

8 star＝true

9 else

10 this node will relay data packers to its father neighbor node

11 along the route recording by seqn1which is stored by itself

12 if the ID of node that received data packets is same as the static sink

13 star＝true；

14 end

15 end

16 end

3 仿真实验

将本文提出的混合基站数据收集算法（MDCA）与文献［9］提出的混合基站数据收集算法（MSSM）、文献［11］提出的移动代理联合优化路由算法（MACORA）以及文献［12］提出的基于遗传算法的移动基站算法（GA）进行了仿真对比。在仿真实验中，选择节点数据包的产生速率为变量。这是因为节点数据包的产生速率越高，其对应的网络负载也就越大。网络负载的高低直接影响数据包的通信延迟和传输成功率两个指标。网络负载越大，对应数据包的平均通信延迟就越大，同时对应数据包的传输成功率也就越低。在实验中，对不同算法取得的性能指标值进行了依次比较，所有对比数据都是经过50次仿真实验后求平均值获得的。仿真实验借助NS－2 软件来实现，实验中的主要参数设置如下：实验区域是一个900m×900m 的正方形区域，该区域内随机分布了250个节点；网络中所有节点的通信半径设定为R＝60m，并设定移动基站的速度在实验过程中始终保持5 m／s；网络中所有节点的初始能量为7J；假定每个数据包为400bytes、查询信息包为20bytes；实验中移动基站发布的局部查询信息的网络挖掘深度为4。

图2为不同网络负载下在同一网络中4种算法的平均通信延迟对比。平均通信延迟为网络中数据包从源节点传输到基站的平均耗时。由该图可以看出，随着网络负载的加大，网络的平均通信延迟也逐渐提升，但本文所提的MDCA 算法与其他算法相比增速最为缓慢。主要原因如下：首先，MDCA 算法在监控区域内引入了移动基站。由于移动基站可以在监控区域中自由移动，其附近的节点可将数据包沿着局部数据采集最小路径树传输给移动基站，从而缩短了数据包在网络中的传输距离、降低了网络的通信延迟。其次，从偏远区域传输给固定基站的数据包如果途经由移动基站构建的局部数据采集最小路径树上的节点，则该节点将会对接收数据进行拦截，然后沿着局部数据采集最小路径树将数据转发给移动基站，因此有效缩小了网络中数据包的传输距离，进而减小了网络中数据包的平均通信延迟。

图2 平均通信延迟Fig.2 Average delay of communication

图3 为相同网络负载下不同算法对应的数据包平均传输成功率之间的比较。由图3可知：网络中数据包的产生速率对网络中数据包的平均传输成功率有非常明显的影响。原因主要是随着数据包产生速率的增高，网络中数据包之间的报文冲突也将急剧增加，进而影响数据包的平均传输成功率。采用MDCA 算法可以小幅提升网络中数据包的平均传输成功率，与MACORA 算法相比，数据包的平均传输成功率提升6%～19%；与GA 算法相比，数据包的平均传输成功率提升4%～13%；与MSSM 算法相比，数据包的平均传输成功率提升2%～7%。主要是由于MDCA 算法在监控区域中引入了移动基站，进而可以保证收集到网络监控盲区及偏远断裂区域内的数据信息。同时，由于移动基站可以降低网络中数据包的传输距离，因此该策略可以有效减少数据包长途传输过程中的出错率，达到提升数据包传输成功率的目标。

图3 数据包的传递成功率Fig.3 Success rate of packet transmission

图4 为4种算法对应的网络寿命情况。由该图可得，本文提出的MDCA 算法能明显提升网络的寿命，主要是因为本文所提算法有如下优点：首先，在监控区域中引入了移动基站，通过移动基站靠近源节点和在数据传输途中实施拦截来减少数据的传输距离，进而达到减少网络中转数据量和网络能耗的目标；其次，MDCA 算法采用了一种能综合兼顾跳数、路由总能耗和节点剩余能量的最优路径评价准则，该评价准则可以促使节点在选择最优路径时，避开剩余能量小的节点，这样可以保证网络中节点的能量均衡性衰退，并避免某些关键节点被频繁使用而过早死亡，进而导致网络出现路由空洞或网络割裂的情况。虽然在相同情况下，GA 算法取得的网络寿命最高，但是GA算法是以高通信延迟为代价来换取网络高寿命的。这是因为GA 算法在监控区域中只配置了移动基站，因此网络中的节点在采集数据信息后必须等待移动基站到达其附近来开始传输数据，所以产生了如上的以牺牲通信延迟来获取网络寿命的状况。

图4 网络寿命Fig.4 Network lifetime

图5 为4种算法对应的数据包的平均能耗情况。由于MDCA 算法在监控区域中引入了移动基站，减小了网络中数据包的平均传输距离，因此相应减小了网络中数据包的平均能耗。同时，减小数据包的传输距离还可以相应提高数据包的安全性，进而减少数据包的传递失误率，达到降低数据包的平均能耗目标。由图5可知：MDCA 算法对应的网络中数据包的平均能耗与MACORA 算法相比降低了49%～57%；与MSSM 算法相比降低了33%～40%；与GA 算法相比降低了7%～17%。总之，采用MDCA 算法后，网络对应的平均通信延迟等性能指标均不同程度地有所提升。虽然移动基站在监控区域中移动也会耗费一定的能量，但给网络带来的利益要比移动基站的花费大得多，所以本文所提的混合基站数据收集算法是可行的。

图5 数据包的平均能耗Fig.5 Average energy consumption per packet

在上述实验区域内随机抛洒100个传感器节点生成监控网络，同时令节点初始能量等参数的设置与上述实验保持相同。将本文所提算法与文献［13］提出的ASLEEP 算法及文献［14］提出的ADAPT 算法进行仿真对比。图6描述了不同算法在网络断裂时各节点剩余能量的分布情况。由图可知：本文所提策略可均衡网络中各节点的能量消耗，避免近基站节点被过多使用而造成其过早死亡，并引起路由空洞的问题。这是因为移动基站减少了近基站节点传输数据的工作量，降低了关键节点的通信能量消耗；其次采用的最优路径评估标准能综合兼顾路由跳数、路由总能耗和节点剩余能量等因素，促使源节点在构建最优路径时避开剩余能量小的节点。这两方面因素均能弥补网络能耗不均衡的缺陷。

图6 网络中各节点的剩余能量Fig.6 Residual energy of each node in network

4 结束语

提出了一种应用于事件驱动型传感器网络的混合基站策略的无线传感器网络移动数据收集算法。这种混合基站数据收集算法在监控区域内配置了两个基站：在网络数据收集过程中充当网络关口的作用的固定基站，在网络数据收集过程中充当一个数据骡子作用的移动基站。实验表明，混合基站数据收集算法能显著提高网络的性能。因为采用两种不同类型的基站可以取得互补所短的效果。同时移动基站在网络中自由移动可以近距离接触源节点，进而减少数据包在网络中的传递距离，达到节省网络能耗、提高数据安全性的目标，而固定基站的存在则可以使网络的通信延迟保持在一个可接受的范围，即保证采集数据的适时性。

［1］石文孝，张阁，王继红，等.基于网格的异构无线网络负载均衡算法［J］.吉林大学学报：工学版，2013，43（3）：788－793.Shi Wen－xiao，Zhang Ge，Wang Ji－hong，et al.Grid based load balancing algorithm over heterogeneous wireless networks［J］.Journal of Jilin University Engineering and Technology Edition，2013，43（3）：788－793.

［2］Abdulla A E A A，Nishiyama H，Kato N.Extending the lifetime of wireless sensor networks：a hybrid routing algorithm［J］.Computer Communications，2012，35（9）：1056－1063.

［3］Hanzalek Z，Jurcik P.Energy efficient scheduling for cluster－tree wireless sensor networks with timebounded data flows：application to IEEE 802.154／ZigBee［J］.IEEE Transactions on Industrial Informatics，2010，6（3）：438－450.

［4］周小佳，吴侠，闫斌.基于移动基站的动态无线传感器网络［J］.西南交通大学学报，2011，46（5）：793－802.Zhou Xiao－jia，Wu Xia，Yan Bin.Dynamic wireless sensor network based on mobile base station［J］.Journal of Southwest Jiao Tong University，2011，46（5）：793－802.

［5］Pazzi R W N，Boukerche A.Mobile data collector strategy for delay－sensitive applications over wireless sensor networks［J］.Computer Communications，2008，31（5）：1028－1039.

［6］Kinalis A，Nikoletseas S.Scalable data collection protocols for wireless sensor networks with multiple mobile sinks［J］.40th Annual Simulation Symposium 2007，Washington，DC，USA，2007：60－72.

［7］Bi Y Z，Sun L M，Li N.BoSS：a moving strategy for mobile sinks in wireless sensor networks［J］.International Journal Sensor Networks，2009，5（3）：173－184.

［8］Jea D，Somasundara A，Srivastava M.Multiple controlled mobile elements（data mules）for data collection in sensor networks［J］.1st IEEE International Conference on Distributed Computing in Sensor Systems 2005，Marina del Rey，CA，USA，2005：244－257.

［9］Chatzigiannakis I，Kinalis A，Nikoletseas S.Efficient data propagation strategies in wireless sensor networks using a single mobile sink［J］.Computer Communications，2008，31（5）：896－914.

［10］Wang J，Ma T H，Cho J S，et al.An energy efficient and load balancing routing algorithm for wireless sensor networks［J］.Computer Science and Information System，2011，8（4）：991－1007.

［11］刘逵，刘三阳，冯海林.双信道无线传感器网络移动代理路由算法［J］.西安交通大学学报，2012，46（2）：113－118.Liu Kui，Liu San－yang，Feng Hai－lin.A mobile agent combination optimization routing algorithm in dual channel wireless sensor networks［J］.Journal of Xi＇an Jiaotong University，2012，46（2）：113－118.

［12］Huang Z，Liu S Y，Qi X G.A genetic algorithm based strategy for mobile sink in wireless sensor networks［J］.Advanced Science Letters，2011，4（11／12）：3528－3536.

［13］Anastasi G，Conti M，Francesco M D..Extending the lifetime of wireless sensor networks through adaptive sleep［J］.IEEE Transactions on Industrustrial Informatics，2009，56（3）：351－365.

［14］Francesco M D，Anastaci G，Conti M，et al.Reliability and energy－efficiency in IEEE 802.15.4／ZigBee sensor networks：an adaptive and cross－layer approach［J］.IEEE Journal on Selected Areas in Communications，2011，29（8）：1508－1524.