WSN网络中分段组播路由算法的研究

高江军

(池州职业技术学院 信息技术系，安徽 池州 247100)

无线传感器网络，简称WSN。它是一种由多个无线传感设备组成的分布式传感网络，这些传感设备可以感知和传输外部世界信息。WSN中的传感器通过无线方式通信，因此网络设置灵活，设备位置可以随时更改，还可以跟互联网进行有线或无线方式的连接。通过无线通信方式形成的一个多跳自组织网络。由于节点的灵活多变，同样也带来了能量受限[1]、存储有限[2]的问题，在长时间大范围信息转发的环境中，组播技术的应用可以减少冗余发送、降低能耗，从而提升网络的传输效率。

WSN中组播的研究有很多，主要是无状态组播[3]和分级分层组播。无状态组播算法的研究有GMR算法[4]和DBOM算法[5]等，GMR算法主要是将所有组播接收节点的位置信息都存储在组播分组头部，中间节点接收到组播分组后根据邻居路由算法来进行分组转发。DBOM算法主要是为每个组播接收节点创建一块接收区域，每个区域有一个中心位置，当分组投递时，sink节点先将分组投递到所属中心位置，再由中心位置投递到目的节点，这种划分区域的方式一定程度上防止了拓扑结构变化带来的影响。对于无状态组播算法，它的优点很明显，就是当节点失效时，可以根据路由算法重新选择路由，可以减弱网络拓扑结构变化带来的影响，但是它的缺点也很明显，该算法要求所有组播接收节点都要存储在根节点中，对于大型WSN时，过多的组播接收节点信息就无法被分组头容纳，出现网络的扩展性问题。

分级分层组播路由算法主要是适用大规模WSN网络，解决网络扩展性问题，目前研究的算法主要有HGMR[6]和MRBIN[7]，HGMR算法将网络分成多个一定大小的子树，每个子树通过地理算法[8]选举一个簇头来管理各个子树节点，sink节点将分组投递给各簇头，再由簇头将分组投递到各个组播接收节点,虽然通过分簇的方式解决了分组头的大小问题，但是簇头要接收所有分组，并进行大量的路由转发，造成簇头能量的快速耗尽。MRBIN算法在组播树上的每个分支节点上存储其下各分支节点的首末节点位置信息，每个分支节点只负责和其下分支节点的分组传递，这种分支传递的方式减少了汇聚节点路由能耗过快的影响，但是每个分支依然要转发所有的分组，如果其下分支节点太多，依然会造成节点能量消耗殆尽。

综合以上组播路由算法存在的问题，本文提出了一种分类分级组播路由算法(Classification hierarchical multicast routing algorithm，CHMR)。该算法首先是将组播树按照规定的节点数量分成多个组播子树，组播子树的根节点存储该子树的分支节点和末梢节点的位置信息和父子关系，通过这种方式可以减小分组头长度同时尽量降低单点失效[9]的可能性。

1 网络模型构建

(1)假定WSN网中的节点具有相同的结构和能量，并且能量是受限的。

(2)假定节点在特定的定位机制[10]下可获知其他节点的地理位置信息。

(3)假定分组可以通过地理路由到达目的节点。

(4)假定组播子树中节点可以分成存储节点、分支节点、转发节点、末梢节点四类。存储节点为组播子树的根节点，存放子树的路由信息，分支节点为分组多路转发经过的非叶节点，转发节点为分支节点间单播分组转发的节点，末梢节点即子树的叶节点。

(5)本文使用无线传输一阶射频能量模型[11]，节点传输一个分组的能耗表示为Et，接收分组的能耗表示为Er，其他能耗忽略，分组长度用l表示，射频传送距离r,射频收发能耗常量Ee,射频放大器能耗常量e，则有：

Et=1Ee+1er2

(1)

Er=1Ee

(2)

节点收发一次分组的总能耗为：

Ea=Et+Er=2lEe+1er2

(3)

2 CHMR算法描述

2.1 选取存储节点的具体方法

上述研究中，存储节点是用来存放子树分支节点、末梢节点的位置信息和父子关系信息。分组投递的目的节点包括分支节点和末梢节点，而且子树内使用无状态转发，分组头部内需要存储所有末梢节点和分支节点的位置信息，因此要控制各子树的规模。具体方法如下：首先，需要一个计数器Ki来计算机子树内节点数量和一个最大目的节点数kmax，当Kmax≤Ki,节点i才可以成为存储节点。

组播目的节点向sink节点申请加入组播组时，先置Ki=0，并将Ki和目的节点位置信息加入组请求中，请求数用n表示，节点i获得下方n≥2请求时，i节点成为分支节点，并计算自己的Ki值，即

(4)

(1)当Kmax

(2)当Kmax=Ki时，i节点成为存储节点，置Ki=0,m值不变，继续向sink发送。

(3)当Kmax>Ki时，i节点从其下Ki≤Kmax分支节点中选择值最大作为存储节点，定义为x节点，如果有多个值相等的都可以选择为存储节点，并执行一下操作：

(5)

(4)如图1，该组播树只显示了sink节点、分支节点和末梢节点，假定Kmax=4，根据算法计算出了各节点的Ki值，由于节点1和3值为5>4,只能选择节点9和节点3作为存储节点，而节点2的值刚好为4，所以节点2即为存储节点。

图1存储节点的选取过程图2组播分组的转发过程

2.2 组播分组的分段转发过程

如图2，A、B、C、D为转发节点，2、3、9为存储节点，1、6为分支节点，具体转发过程如下(只画出右侧的转发节点):

sink节点将其存储的子树节点(1(3,4),2)加入到组播分组的头部中向下通过地理路由，经A、B节点无状态转发到节点1、2，节点2收到分组时，由于节点2是存储节点，将分组头替换成(5,6(10,11))，提取出下级目的节点5、6，通过C、D使用地理路由转发到5、6,6节点收到分组继续转发到末梢节点10、11。同理，节点1收到分组转发到3、4节点，由于3是存储节点，分组头替换成(7，8,9)，分组到达节点9，分组头又替换成(12,13)，最终完成所有节点的转发，该转发过程很清楚地显示出分组头通过多次的替换，大大减少了分组头的大小，在大规模网络中可以很好提高扩展性。

3 仿真比较

3.1 参数设置

仿真环境：在50×50m2的正方形区域内均匀分布无线传感器节点。

3.1.1 常量设置 射频传送距离r=5m；数据传输速率v=400bits/s；组播分组有效数据长度la=400bits；节点初始能量Et=100000μJ；射频收发能耗常量Ee=50nJ/bits；射频放大器常量e=100pJ/b/m2

3.1.2 网络密度设置 节点射频传送范围r内所包含的邻居节点的个数的平均值,设为ρ，设置传感器所分布的区域面积为s，分布节点的数量为n，则有：

(6)

3.1.3 节点转发分组能耗设置 假定分组头长度为lh，根据公式3得出，节点转发一次分组的能耗为Ea=2lEe+ ler2=l(2Ee+ er2)=102.5×(400+ lh),可以看出相同参数下转发分组的能耗取决于分组头长度。

3.1.4 仿真节点数量设置 下文的仿真比较主要从扩展性和吞吐量两方面进行比较，设定Kmax=10,网络密度ρ=10,每个仿真重复500次，随机分布节点，平均值显示结果，并通过与无状态组播HGMR、分支组播MRBIN方案对比。

3.2 扩展性比较

扩展性即能耗随接收节点数量变化情况，综上所述，能耗取决于分组头的长度，因此可以通过观察分组头长度随接收节点数量变化情况，见图3。

图3扩张性的比较图4吞吐量的变化

从图3可以明显看出，当有效数据长度相同时，HGMR的分组长度随着目的节点的增多，组播分组的长度不断地增大，由于分组头长度是有限的，当网络规模增加到一定程度而分组头无法容纳时，扩展性就非常差。MRBIN和CHMR算法下的分组长度一直保持在一定的大小，扩展性很好。

3.3 吞吐量的比较

网络吞吐量即生存时间内传输有效数据的总量，生存时间内，传输的数据量越大，则吞吐量越大，网络的综合性能就越好，见图4。

从图4可以看出，MRBIN算法的吞吐量一直维持在一定的水平，但是HGMR和CHMR的吞吐量开始处在一个较高的水平，但是随着网络规模的扩大，吞吐量在不断下降，HGMR的下降趋势比较快，改进的算法CHMR由于控制了有效数据的量，下降趋势则相对要缓慢一些。

综合上述两项比较，可以得出，CHMR的算法在扩展性和吞吐量的综合性能上，相比较无状态组播和分支组播上有了一定性能的提升。

4 结束语

本文主要针对大规模无线传感网而展开的组播研究，通过分析多种组播路由算法，找出无状态组播和分支组播当中存在的分组头长度和节点路由转发负载过大的问题，结合地理路由和WSN的网络特性，提出一种基于存储空间控制和路由分段的CHMR算法，通过对该算法的各节点的分类描述以及存储节点选取方法进行设计，最终将该算法在仿真环境下进行实验，并将实验结果以图表的形式和其他组播路由算法在扩展性和吞吐量上进行比较，得出CHMR算法在大规模WSN网络数据传输性能提升上有一定的效果。