［吴晨］



基于分离树的能量有效数据转发机制*

［吴晨］

摘要

在无线传感网中，由于传感器节点能量极度受限，而传统的广播通信方式会产生很大的数据冗余，因而造成能量利用率较低。文章通过建立以汇聚节点为根节点的分离树来解决以上问题，m颗分离树均匀覆盖整个网络并交替进行工作，不工作时则进入休眠状态以节省能量。在数据转发阶段，分离树中的节点有方向性地将数据转发到汇聚节点，有效避免环路和回传，从而大幅度降低了冗余数据的转发。

关键词：无线传感网 分离树 能量利用率 休眠状态 数据冗余

吴晨

女，硕士研究生，重庆邮电大学。

引言

无线传感器网络(Wireless Sensor Networks,WSNs)是由大量带有感知、检测和处理功能的传感器节点组成，但这些节点被布置在监测区域，可以以自组织的方式形成无线网络[1]。无线传感器网络在环境监测、救援、生物医学和智能家居等领域有广泛的应用[2]。传感器节点是由电池供电，由于其部署场景的特殊性，使得不易补给，因此，合理高效的利用传感器节点有限的能量极为重要[3]。而在传统的通信方式中，每个传感器节点将采集的信息直接以广播的形式发送到汇聚节点，由于传感器节点数量庞大、分布较密集，由此会产生频繁的碰撞和冲突，导致广播风暴问题(Broadcast Storm Problem)[4]。各节点冗余数据较多，通信负载重，无谓消耗了宝贵的能量资源。

1　相关工作

针对以上问题，国内外学者已做大量研究。如文献[5]中的概率广播是研究较多的一种解决办法，主要思想是一个节点在收到广播消息之后以概率P进行转播，但概率值的设定是一个NP问题，应根据网络情况动态的设置概率值的大小。文献[6]中提出了一种基于计数器的方法，节点收到一个广播消息后，发起一个计数器，并设初值为1，阈值为C，设置一个随机等待时延，在等待时间段内，节点每收到一个副本消息计数器的值就加1，如果节点收到重复消息的数量小于C，就进行转发，否则，丢弃此消息。文献[7]中提出构建一个由连通支配集CDS（connected dominating set）构成的主干网，主干网中的节点称为支配点，负责路由表的计算和维护、消息的收集和转发；网络中其它节点称为被支配点，主要负责信息的采集。通过构造主干网使得消息限制在网络的一小部分节点间转发，有效地减少了产生广播风暴的机率，而在任意图中求解最小连通支配集是NP问题。分簇路由具有拓扑管理方便、能量利用高效、数据融合简单等优点，它是另外一种经典的分层结构路由协议，成为当前重点研究的路由技术[8]。在分簇的拓扑管理机制下，网络中的节点可以划分为簇头节点和成员节点两类。在每个簇内，根据一定的机制算法选取某个节点作为簇头，用于管理或控制整个簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理以及簇间转发。分簇算法中簇的构建过程开销大，簇头节点通信任务重，会导致节点能耗不均。

以上这些方法虽然能够一定程度上降低广播风暴发生概率，节约节点能量，但是需要所有节点均参与数据采集与转发，邻居节点间的冗余数据较多，并且一次数据传输过程只能收集一种数据。本文的基于分离树数据转发机制，以汇聚节点为根节点来建立m颗均匀覆盖整个网络的分离树，当仅需采集一种数据时，仅其中一棵树负责数据收集与转发，极大地减少了冗余数据量，其他树中的节点则进行休眠，节约能耗。当需要同时采集两种或多种数据时（如温度、湿度、光照等），多棵树同时工作，分别各自采集不同数据，这样汇聚节点可以实现同时采集到多种数据。

2　基于分离树的能量有效数据转发机制

2.1基本思想

本文所提出的机制主要思想是从汇聚节点开始构建m个无交集的生成树，m棵树中的节点均匀分布在整个网络。由于网络节点分布较密集，邻居节点之间采集的信息有很大的相似性和冗余性，因此在通信过程中，m棵树交替进行通信任务，其余的则处于休眠状态，能保证实现信息采集的目的的同时，节省更多能量。另一方面，由于树形结构的特殊性，各节点保存有父节点、子节点信息，因此在数据转发过程中，可以保证数据有方向的传送到汇聚节点，能有效避免环路和消息回传的产生，同时消息碰撞的概率大大降低，缓解了广播风暴问题。

2.2网络模型

为了简化网络模型，本文做了如下假设：

（1）网络中共有N个节点随机部署在m*m的区域内；

（2）所有节点和汇聚节点一旦部署完毕处于静止暂态；

（3）节点可通过功率控制来调整发射功率；

（4）每个节点有唯一的id号；

（5）汇聚节点位于监测区域外，并且能量不受限。

2.3分离树的构建

这里以m=2为例详细说明分离树的构建过程。构建过程中通过给节点标记不同颜色（深色和浅色）来区分两棵树，除了汇聚节点每个节点充当三种角色中的一个：深色节点、浅色节点，孤立节点。汇聚节点是深色、浅色两个生成树的共同节点，因此它可看做既是深色节点也是浅色节点。其构建过程如下：首先由汇聚节点广播一个hello消息给所有邻居，收到此hello消息的邻居节点随机地给自己标记深色、浅色（如图1（a））。然后深色、浅色节点分别广播red-hello、blue-hello给邻居节点。一个节点一旦收到至少一个来自浅色或深色节点的hello消息，此节点将等待一段时间T来接受足够的hello消息，然后根据这些邻居的颜色再决定其自身颜色，以概率pr成为深色节点、pb成为浅色节点以概率成为叶节点。为了使更多的节点收到来自深色和浅色节点的hello消息，需要在给定邻居情况下平衡两种节点。因此，如果一个节点的浅色邻居节点比深色多，那么此节点以更大概率选择成为深色；如果一个节点的深色邻居节点比浅色多，那么此节点更可能选择标记为浅色。一个节点通过接收到的red-hello、blue-hello消息估计两种颜色的邻居节点数量，并选择它自己的颜色保证其他节点最大可能的接收到两种颜色的节点消息。若一个节点没有收到任何hello消息，表示此节点既不能标记为浅色也不能标记深色，成为孤立节点。当所有节点均选定自己角色之后，建立起了深色、浅色两颗以汇聚节点为根节点的分离树（如图1（b））。

图1　分离树的构建过程

为了保证尽量多的节点参与路由，希望所选的分离树尽可能大并覆盖整个网络，需要采取合适的策略来决定的值，如果收到很少的hello消息，则应该大一点，这样可以得到更大覆盖的树。如果节点收到red-hello比blue-hello多，为了平衡两种颜色此节点将会有更大的机会成为浅色节点。因此，由公式（1）（2）来计算pr、pb:

其中，Nred、Nblue分别表示收到的red-hello、blue-hello消息的数量；p是一个节点成为非叶子节点的概率，为了保证网络全覆盖，这里设置，即所建立的分离树能够完全覆盖整个网络。

2.4数据转发过程

当分离树建立起之后，则可以开始数据传输过程，为了实现m颗分离树分开各自通信，不同颜色节点互相不允许转发彼此的消息。如果一个节点成为了浅色或是深色节点，他就会加入相应的树并转发消息给它的父节点。当采集单一数据时，分离树交替工作，不工作的分离树中的节点进入休眠状态。工作状态的节点将自己采集的数据和子节点发来的数据进行融合，然后发送给父节点，直到消息到达汇聚节点。当需采集n（m≥ n）种数据时，任意n棵分离树执行通信任务，其余进行休眠；当其中某一分离树由于节点能量耗尽而不能继续任务时，则休眠的分离树进行唤醒，继续此中断任务，由此保证通信质量。

3　仿真分析

为了研究本文所提出机制的有效性，用OMNeT++仿真软件对此进行验证，在相同实验条件下，对比传统的广播方式和本文的机制，主要对比网络中网络开销和节点能耗情况。

仿真参数设置如表1：

表1　仿真参数的设置

（1）广播风暴发生概率

图2反映了广播风暴发生概率随着节点数的变化趋势，可见本文的分离树机制性能相比广播方式有明显提高，主要原因是本文建立的两颗分离树交替工作，参与的节点数量有所减少，冗余数据大大减少；另外在数据转发过程中，节点有方向性的将数据发给自己的父节点，碰撞的概率大大降低，广播风暴问题得到明显缓解。

图2　广播风暴发生概率随着节点数的变化趋势

（2）节点能耗情况

图3反映了节点每一轮结束时剩余能量的变化情况，从图中可以看出本文所提机制变化趋势较平缓，即节点耗能速度较慢，主要是因为网络中冗余数据大大减少，节点能量利用率得到提高；同时节点周期性的工作通信量有所降低，有助减少节点耗能；此外，节点在数据转发过程中，每个节点都会对数据进行融合处理，使得数据包较小，减小了传输能耗。

图3　节点剩余能量平均值随运行时间的变化曲线

4　总结

本文提出的基于分离树的能量有效数据转发机制利用以汇聚节点为根节点来建立m个均匀覆盖整个网络的分离树，实现进一步降低能耗，还能同时采集多种数据。由于网络节点分布密集，邻居节点之间的感测数据有很大的相似性，故分离树交替执行通信任务，完成通信目的，不工作时，使其处于休眠状态以节省更多能耗。此外利用树形结构的特殊性，在数据转发阶段，有方向性的将数据以最短路径发送给汇聚节点，使节点能量得到高效利用。仿真实验表明，本文的机制能有效缓解广播风暴问题，实现了节能，节点能量利用率大大提高。

参考文献

1Yu J,Wang N,Wang G,et al.Connected dominating sets in wireless ad hoc and sensor networks–A comprehensive survey[J].Computer Communications,2013,36(2):121-134

2Pantazis N,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks:A survey[J].Communications Surveys & Tutorials,IEEE,2013,15(2):551-591

3Kuila P,Jana P K.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014,33:127-140

4Tseng Y C,Ni S Y,Chen Y S,et al.The broadcast storm problem in a mobile ad hoc network[J].Wireless networks,2002,8(2-3):153-167

5Hanashi A M,Siddique A,Awan I,et al.Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc networks[J].Simulation Modelling Practice and Theory,2009,17(2):364-375

6Yassein M B,Nimer S F,Al-Dubai A Y.A new dynamic counter-based broadcasting scheme for Mobile Ad hoc Networks[J].Simulation Modelling Practice and Theory,2011,19(1):553-563

7凌飞,吴振华.能量均衡的最小连通支配集分布式算法[J].传感技术学报,2013,25(9):1316-1321

8Liu X.A survey on clustering routing protocols in wireless sensor networks[J].Sensors,2012,12(8):11113-11153

收稿日期：（2016-02-03）

基金项目：国家物联网专项(工信部科函[2014]351号)

DOI:10.3969/j.issn.1006-6403.2016.03.015