一种基于能效的多摆渡组播路由算法*

莫媛淇，杨文忠，张振宇

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐830046)

0 引 言

无线传感器网络(WSNs)是部署在检测区域内由大量廉价的微型传感器节点构成分布式自组网络，这些节点能够实现传感、计算和无线通信功能，但也受到能量和带宽的限制［1，2］。因此，基于能量的路由设计在无线传感器网络路由机制的研究中变得日趋重要。目前，针对无线传感器网络的组播问题，研究学者们提出了多种路由策略［3］，根据网络拓扑结构的不同，可将其分为两类:基于树形结构的方法和基于网格结构的方法。基于树形结构的路由协议主要包括VLMM［4］，EMRS［5］和GMR［6］等。这类协议利用不同的能量启发式构造组播树，根据组播树提供的最优路径可以把信息快速准确地发送到目的节点，但基于组播树的网络鲁棒性较差容易产生孤立节点。基于网格结构的路由协议主要包括E2MRP［7］，DCMP［8］等。这类路由协议在网格建立的基础上，选取一组中继节点完成组播分组的传送，使源和目的节点之间存在多条路径，能很好地适应节点的移动性，解决了树形结构引起的单点失效的问题，但在网格内信息的洪泛将产生巨大的能耗。

针对节点能量受限且通信间断等问题，本文提出多摆渡组播路由算法(multiple ferries multicast routing algorithm，MFMA)。该算法在网络区域划分的前提下，利用区域摆渡节点和区间中继节点的交互实现网络的连通，在此基础上，MFMA 提出了区域能量优先级，并基于此能量优先级，选择合适的中间区域，以确定能量最优的组播树，最后各个区域内的摆渡节点根据此组播树的路径信息完成组播数据的传递。

1 网络模型与假设

在图1 所示网络拓扑结构中，将节点均匀分布的网络G 划分为M 个相等的区域，那么，每个小区域Ri中分布着N/M 个节点(总节点个数为N)和一个摆渡节点f。相邻的区域利用中继节点Nr来中继区间信息。为了方便描述，本文将中继节点Nr虚拟化为区域间的通信链路，网络为以区域R 为传输单元的无向连通图G(R，Nr)，如图2 所示。其中R={R1，R2…Rd}表示网络所有区域的集合，其中每个区域中又由若干节点组成，即Ri={1 ＜j ＜N/M|Nj}，Nr={Ri≠Rj|Nr(Ri，Rj)}为网络中继节点集合，即通信链路的集合。任何区域间最多有一条链路，若区域Ri，Rj∈R 且Ri，Rj间存在一条直接相连的链路，记此链路为Nr(Ri，Rj)。

本文将源节点所在的区域称为源区域记为Rs，目标节点所在区域称为目的区域，记为Rd，与区域有边直接相连的区域称为该区域的邻居区域，若Ru是Rv的邻居区域，则Ru∈Neighbor(Rv)且存在Nr(Ru，Rv)。每个区域有自己的属性AtRi=(［Di］，［hi］)，其中，Di为区域的度，表示与该区域相关联的边的个数，用该区域邻居区域的个数表示，hi表示当前区域到达源区域的最小跳数，用当前区域到达源区域的最短路径上经过的中间区域的个数表示。

图中，▯为摆渡节点，○为普通节点，●为中继节点。

图1 网络拓扑结构Fig 1 Network topology structure

图2 无向连通图Fig 2 Undirected connected graph

2 能量组播树的构建

2.1 问题定义

基于上述网络模型，本文主要研究在指定源区域Rs和目的区域集合Rd，Rd={Rd1，Rd2，…，Rdk}(k ＜M)的情况下，寻找一棵以Rs为根并且可以到达所有目的区域Rd的树，使该组播树满足在时延受限的条件下总能耗最小。

2.2 能量模型

本文假设普通节点和中继节点具有相同的初始能量和发射功率，摆渡节点没有能量限制。根据节点能量消耗和通信模型，节点发送和接收k bit 数据的能耗分别为

其中，Eelec为电路上接收或发送每比特数据消耗的能量，εfs为电路放大器系数，d 为摆渡节点与普通节点的通信距离，a 为路径损耗指数，满足关系2 ＜a ＜4。根据文献［10］能量消耗与通信距离存在如下关系

由于摆渡节点与普通节点只发生近距离的数据传输，假定该通信距离一定，根据式(3)可知，摆渡节点与任意节点通信的能耗相同，那么组播树的能量消耗与参与通信的节点的个数呈正比。在本文提出的网络模型中，由于度大的区域可以承担更多的中继任务，起到减少组播树中参与通信的节点的个数的目的，因此，选择度大的区域作为中继区域可以有效的减少能量的消耗。

综上，区域能量优先级level 度量公式，如式(4)所示

其中，区域度Di可以控制组播树的能量消耗

由于最小跳数hi可以控制单个数据的传输时延［11］，因此，level 的值越大，表示选择的中间区域能使组播树能量消耗越少且传输时延越短。

2.3 能量组播树

在设计区域组播树时，采用贪婪算法思想，迭代选择邻居区域中能量优先级level 最高的作为中继区域。组播成员的加入和离开通过控制信息的交互实现，其中孩子请求信息(child request message，CRM)和回复孩子请求信息(reply child request message，RCRM)协助组播成员区域加入组播树，离开请求信息(left request message，LRM)和回复请求信息(reply left request message，RLRM)实现区域离开组播树，在RCRM 中包含目的区域到源区域的路径信息Path。RCRM 在组播树的构建中是动态变化的。另外，每个区域的摆渡节点维护区域的状态信息表StaTable，如表1。当父亲区域请求孩子区域时，父亲区域将状态信息表StaTable封装在CRM 头部一同发送给邻居区域，接收到CRM 的区域便可据此获悉邻居区域的能量优先级。

2.3.1 组播树的构建

算法主要描述了以区域为单位的能量组播树的构建方法，其中，1 ～3 行是初始化阶段，利用Dirkstra 算法，更新各区域到源区域的最小跳数hi，并根据式(5)更新区域的度Di及各区域的邻居列表Neighbor.list;4 ～16 行是组播树构建阶段算法从源区域开始向flag=0 邻居区域发送孩子请求信息CRM。若Ri是目的区域，在Rd［］中删除Ri，并根据式(4)计算接收到的CRM 中的区域level，选择level 最大的区域作为父亲区域，当多个邻居区域的level 相同时，选择本身是目的区域或者其邻居区域中包含目的区域的区域作为父亲区域，将该父亲区域加入组播树，并将路径信息追加到RCRM 中回复该父亲区域，其余的区域放在备用父区域列表中，该父亲区域再以同样的方式寻找自己的父亲区域直到Rd［］为空，说明所有的目的区域已经加入组播树算法结束，此时，源从收到的RCRM 中可获悉各个目的区域到达自己的最佳路径信息。

表1 区域状态表Tab 1 Region state table

算法1 construct multicast tree(Rs，Rd［］)

输入:源区域，目的区域集合

输出:源区域到目的区域的能效组播树

1)level=0，flag=0;∥初始化能量优先级和表示符

2)Dirkstra(Rn);更新各个区域能量优先级

3)renew Stable.level and Stabel.Neighbor.list();

4)Multicast Tree add Rsand Rd［］;

5)For each Riin RN

6)while(Rd［］! =null) do

7)Risend CRM(Stable) to Ri.neighbor.list();

8)For any Rp，Rq∈Rj.neighbor.list()

9)if(Rp.level=max{Rj.neighbor.level})

10)Rj.parent→Rp;Multicast Tree add Rp;∥在邻居区域中选择level 最大的区域作为父区域

11)else if

Rp.level=Rq.level=max{Rj.neighbor.level})

12)then compare(destnum);

∥比较level 相同的区域的邻居区域包含的目的区域的个数

13)If(Rp.neb.list().destnum ＞Rq.neb.list().destnum)

14)Rj.parent→Rp; Multicast Tree add Rp;

∥选择本身是目的区域或者其邻居中包含目的区域多的区域作为父区域

15)else Re-parent.list add Rp;∥其余邻居区域加入备用父亲区域

16)return Multicast Tree

2.3.2 组播树的维护

当有区域要离开组播树时，若该区域不存在孩子区域，则直接向父亲区域发送LRM;否则，向孩子区域发送LRM，孩子区域从备用父亲区域列表中选择level 次高的作为父亲区域建立通信，并向原父亲区域回复RLRM，接收到回复后，该区域再向父亲区域发送LRM，并断开连接处于休眠状态。

当有区域要加入时，从收到的CRM 中选择level 最大的区域作为父亲区域，此过程与建树过程类似，这里不再赘述。

当源区域R2产生到Rd={R6，R7，R8}数据包时按着算法1 的构建过程，便可得到如图3(a)所示的组播树。而基于NRA［12］方法可得到如图3(b)的组播树，基于最短路径树的构建方法［13］可得到如图3(c)的组播树，从能量的角度分析，图3(a)中的组播树使更多的区域处于休眠状态，相应的能量消耗最少。因此，本文提出的组播树的构建是在控制时延的基础上能量高效的。

3 仿真实验

本文利用MyEclipce8.0 编程实现仿真任务，通过改变网络数据流量和区域个数，对NRA，MFMA 的网络平均传输能耗和数据交付率进行了比较分析。仿真参数配置为:网络大小12 km×12 km;数据包的大小512 字节，接收或发送每比特数据的能耗5×10－8J，功率放大器εfs=10(pJ/bit/m2)，摆渡节点和普通节点的通信半径均为150 m;节点的初始能量E0=50 J。

1)数据流量对网络性能的影响

在区域个数M=9 时，图4、图5 分别显示了网络数据流量对平均传输能量和数据交付率的影响。如图4 所示，随着网络中数据流量的增加，MFMA 的平均能量消耗明显低于NRA，这是因为MFMA 是基于区域局部信息进行建树的，在建树过程中利用贪婪的算法思想使组播树中包含的中间区域最少，从而更多的区域处于休眠状态，避免了额外的能量消耗。

如图5 所示，随着网络中数据流量的增加，MFMA 和NRA 两种方法的数据交付率在不断降低，这是因为节点的初始能量有限，当执行了一定量的通信任务后，由于节点能量的不足使部分通信链路失效，从而导致数据交付率的降低;在NRA 中，源到目的只存在一条路径，关键路径上节点失效的问题将严重影响数据的交付率，而MFMA 中，源到目的存在多条路径，有效缓解了上述问题，增加了网络生命周期，因此，MFMA 的数据交付率明显高于NRA。

图4 数据流量对平均传输能量的影响Fig 4 Influence of data flow on average transmission energy

图5 数据流量对数据交付率的影响Fig 5 Influence of data flow on data pay rate

2)区域数量对网络性能的影响

在网络信息产生率为5 000 条/min 的情况下，图6 和图7分别显示了网络中包含的区域数量对平均传输能量和数据交付率的影响，如图6 所示，MFMA 和NRA 两者的平均传输能耗均与区域的个数呈正比，这是由于伴随着网络中区域个数增加，从源区域到各个目的区域经过的中间区域的个数也在增加，因此，产生了更多的通信量，导致了网络平均能耗的增加。而在同等条件下，MFMA 的平均能量消耗低于NRA。

如图7 所示MFMA 和NRA 两者的数据交付率均与区域的个数呈反比，这是由于从源区域到各个目的区域经过的中间区域个数的增加，导致数据传输时延的增加，使某些数据包不能在其生命周期内被传送到目的区域，从而降低网络的数据交付率，而MFMA 保证了源区域到各个目的区域经过的跳数最小，使数据传输时延最短，因此，在相同的数据包的生命周期内，MFMA 能使更多的数据包成功传输到目的区域。

4 结 论

图6 区域的数量对平均传输能量的影响Fig 6 Influence of number of region on average transmission energy

图7 区域的数量对数据交付率的影响Fig 7 Influence of number of region on data delivery rate

为实现在节点通信间断的无线传感器网络环境中的组播路由机制，本文提出一种MFMA。该算法区域划分的基础上，引入轨迹可控的区域摆渡节点负责区域内信息的传输，区域间的共享节点负责信息的中继。为了降低通信能耗，该算法提出了区域能量优先级，并利用贪婪算法的思想根据区域优先级构建以区域为传输单位的能量组播树，保证总能耗最小，而邻居区域的优先级是通过控制信息的交互获得的，这样就避免了周期性广播自身信息的能量消耗，当组播树中有节点失效时，MFMA 可从后备中继列表中选择合适的中继替代该失效节点，以保证通信链路的连通。仿真结果表明了该算法在能量和传递率等方面的有效性。

［1］ 余旻辉，唐 亮.无线传感器网络现状及应用［C］∥信息通信网络技术委员会年会文，2011:1396－1403.

［2］ Chen C，Chen Z.Evaluating contacts for routing in highly partitioned mobile networks［C］∥Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking，ACM，2007:17－24.

［3］ Mongiovi M，Singh A K，Yan X，et al.Efficient multicasting for delay tolerant networks using graph indexing［C］∥2012 Proceedings IEEE INFOCOM，IEEE，2012:1386－1394.

［4］ Anmol S，Brian S，Richard Han.VLM2:A very light weight mobile multicast system for wireless sensor networks［C］∥Proceedings of the IEEE Wireless Communications and Networking Conference，2003:1936－1941.

［5］ Niwat T，Yoshito T，Kaoru S.Tree-based data dissemination in wireless sensor networks［J］.Journal of University of Tokyo Center for Spatial Information Science(CSIS)，2005(2):17－18.

［6］ Sanchez J A，Ruiz P M，Liu Jennifer，et al.bandwidth-efficient geographic multicast routing protocol for wireless sensor networks［J］.IEEE Sensor Journal，2007，7(5):627－636.

［7］ Song W Z，Wang Y，Li X Y，et al.Localized algorithms for energy efficient topology in wireless Ad Hoc networks［J］.Mobile Networks and Applications，2005，10(6):911－923.

［8］ Lee S J，Williams Mario G.Ad Hoc wireless multicast with mobility prediction［C］∥Proc of Mobile Networks and Applications Conf，2001:351－360.

［9］ Zeng Guokai，Wang Chen，Li Xiao.Grid multicast:An energy efficient multicast algorithm for wireless sensor networks［C］∥Proc of Fourth IEEE International Conference on Networked Sensing Systems，Braunschweig，2007:267－274.

［10］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Hawaii International Conference on System Science，Hawaii，USA，2000:10－20.

［11］Zhang Z，Fei Z M.Route design for multiple ferries in delay tolerant networks［C］∥Proceedings of Wireless Communication and Networking Conference，Kowloon，China，2007:3460－3465.

［12］Zhao W，Ammar M，Zegura E.Controlling the mobility of multiple data transport ferries in a delay-tolerant network［C］∥Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies，2005:1407－1418.

［13］王 涛，李伟生.低代价最短路径树的快速算法［J］.软件学报，2004，15(5):660－665.