区域分级的粮库无线传感器网络路由算法

摘 要 粮库WSN路由算法是WSN检测粮库粮食数量技术的难点之一。由于粮库中传感器节点分布的复杂性，所以其路由算法比较特殊。根据粮库WSN的分布，提出一种RCCMA路由算法，先将大量分布不均的传感器节点进行簇区域划分和级别设定，然后利用最小夹角原则实现二级簇区域内节点间路由和一级簇区域与二级区域内目标节点间的路由。由于一级簇区域传感器节点能耗较大，因此采用轮转调度机制，将能耗平衡化，降低了单个传感器节点的能耗。对比几种典型的路由算法，实验显示，该算法具有明显的优势。
关键词 路由算法 簇区域 无线传感器网络

引 言
    利用无线传感器网络检测粮库的粮食数量是一项新技术。由于粮堆的复杂性，可在粮库底部散布大量分布不均的压力传感器节点。将粮库内大量分布不均的传感器节点进行组网，构建一种路由算法，这是粮库WSN(Wire-less Sensor Network)的关键技术之一。
    高效的路由算法需满足以下几点：能量高效(协议简单和节省能量和均衡消耗)、可扩展性(网络范围和节点密度)、鲁棒性(节点变化和拓扑变化)、快速收敛性。本文通过研究目前主要的几种典型WSN路由算法，提出一种针对粮库WSN的路由算法。实验证明，该算法满足能量高效性、可扩展性、鲁棒性和快速收敛性要求。单个对比文中提到的几种典型路由算法，该算法整体性能比它们都优越。

1 典型的WSN路由算法
    传统无线通信网络研究的重点放在无线通信的服务质量(QoS)上，而无线传感器节点是随机分布、电池供电的，因此无线传感器网络路由算法的研究重点放在如何提高能量效率上。目前典型的无线传感器网络路由算法主要有以下几种。
1．1 泛洪算法
    泛洪(Flooding)算法是一种传统的无线通信路由算法。该算法规定，每个节点接收来自其他节点的信息，并以广播的形式发送给其他邻居节点。如此继续下去，最后将信息数据发送给目的节点。但这个算法容易引起信息的“内爆”(implosion)和“重叠”(overlap)，造成资源的浪费。因此在泛洪算法的基础上，提出了闲聊(Gossiping)算法。
1．2 Gossiping算法
    Gossiping算法是在泛洪算法的基础上进行改进而提出的。它传播信息的途径是，随机地选择一个邻居节点，获得信息的邻居节点再以同样的方式随机地选择下一个节点，进行信息的传递。这种方式避免了以广播形式进行信息传播的能量消耗，但其代价是延长了信息的传递时间。虽然Gossiping算法在一定程度上解决了信息的内爆问题，但是仍然存在信息的重叠现象。
1．3 SPIN算法
    SPIN(Sensor Protocol for Information via Negotia-tion)算法是一种以数据为中心的自适应路由算法。其目的是通过节点之间的协商，解决Flooding算法和Gossi-ping算法的内爆和重叠问题。SPIN算法有3种类型的消息，即ADC、REQ和DATA。ADC用于数据的广播，当某一个节点有数据可以共享时，可以用其进行数据信息广播。REQ用于请求发送数据，当某一个节点希望接收DATA数据包时，发送REQ数据包。DATA为传感器采集的数据包。在发送一个DATA数据包之前，一个传感器节点首先对外广播ADV数据包。如果某一个节点希望接收要传来的数据信息，则向发送ADV数据包的节点回复REQ数据包，因此，便建立起发送节点和接收节点的联系，发送节点便向接收节点发送DATA数据包。SPIN协议的工作流程如图1所示。

1．4 定向扩散算法
    定向扩散(Direeted Diffusion)算法是一种基于查询的路由机制。整个过程可以分为兴趣扩散、梯度建立以及路径加强3个阶段。在兴趣扩散阶段，汇聚节点向传感器节点发送其想要获取的信息种类或内容。兴趣消息中含有任务类型、目标区域、数据发送速率、时间戳等参数。每个传感器节点在收到该信息后，将其保存在Cache 中。当整个信息要求传遍整个传感器网络后，便在传感器节点和汇聚节点之间建立起一个梯度场，梯度场的建立是根据成本最小化和能量自适应原则。一旦传感器节点收集到汇聚节点感兴趣的数据，就会根据建立的梯度场寻求最快路径进行数据传递。梯度场建立的过程如图2所示。

1．5 LEACH算法
    LEACH(LOW-Energy Adaptive Clustering Hier-archy)算法是一种以最小化传感器网络能量损耗为目标的分层式算法。该算法的主要思想是通过随机选择类头节点，平均分担无线传感器网络的中继通信业务，以达到平均消耗传感器网络中节点能量的目的，进而延长网络的生命周期。LEACH算法可以将网络生命周期延长15％。LEACH算法分为两个阶段：类准备阶段和数据传输阶段。类准备阶段和就绪阶段所持续的时间总和称为一个轮回。在类准备阶段，LEACH算法随机选择一个传感器节点作为类头节点，随机性确保类头与基站之间数据传输的高能耗成本均匀地分摊到所有传感器节点上。

2 RCCMA算法
    定义1 簇区域，有一些相同的传感器节点所占的区域，处在该区域内的节点功能相同。在本文中，一级簇区域内所有传感器节点都具有轮转调度机制、数据收发等功能，二级簇区域内传感器节点不具有轮转调度机制。
    定义2 绝对夹角，不考虑方向，只考虑大小。
2．1 簇区域划分和级别设定
    如图3所示，将粮库底面区域化，在各个区域内计算传感器节点密度，ρ=N／S。选取 3个密度最高的区域作为一级簇区域，其他区域为二级簇区域。在边界线外部确定整个网络的终极节点。设终极节点为O，选取的3个一级簇区域为A、B、C，终极节点到3个一级簇区域中心距离分别为dA、dB、dC，则终极节点位置满足min{dA+dB+dC}。

2．2 二级簇区域内节点问路由
    在二级簇区域内，选取一个到最近一级簇区域距离最短的节点作为该二级簇区域内的目标节点。利用最小夹角原则进行源节点到目标节点路由。具体步骤如下：
    设节点1为该二级簇区域内选取的目标节点。节点8可向节点4通信，也可以向节点9通信。如果节点8、9都正常，则将节点8分别与节点4、节点9和节点1连接。以节点8与目标节点1的连线为终边，以节点8与其相邻的节点4、9连线为另一边，判断它们的绝对角大小。选取构成最小角的邻节点作为源节点的下一跳路由节点，图4中节点9构成的绝对夹角最小，故选择节点9作为源节点8的下一跳路由节点。其他节点及其路由类似。

2．3 一级簇区域内节点问路由
    一级簇区域负责与邻近二级簇区域节点通信，同时负责与整个网络终极节点通信，所以能耗最大。但是，一级簇区域内节点密度较高，采用轮转调度机制，每个节点在某时承担目标节点，将能耗平衡化，降低单个节点的能耗。
    当某时该区域内某节点是目标节点时，该区域内的其他节点和其相邻的二级簇区域内的目标节点都是该一级簇区域内目标节点的子节点。此时便是所有子节点与目标节点问的路由问题。同理，参照最小夹角原则进行路由规划。
    一级簇区域内目标节点汇聚了大量的数据，但节点数量较少(本例中任何时刻只有3个)。终极节点采用查询机制与3个一级簇区域目标节点进行通信。

3 实验结果
3．1 实验环境
    实验采用30个能量相同的传感器节点分别分布在10个等面积区域内，A、B、C三个区域节点密度最高，都布置了5个节点，其他区域节点布置如图6所示。然后用一个终极节点和一级簇区域内节点通信，此终极节点能量和通信距离都比其他节点大。传感器节点采用nRF905射频芯片，ATmegal68单片机，供 3．3 V直流电(旧电池)。

3．2 实验方法
    ①先按本路由算法实现整个WSN的通信，记录最大通信延迟时间。然后，进行多次通信，消耗节点能量，直到网络瘫痪，记录网络工作时间。最后，减少或增加传感器节点，按本路由算法再次建立WSN路由，进行相同的测试。在多次测试中，记录网络出错率。
    ②采用上述几种典型的路由算法，按方法1进行同样的测试。部分参数对比如表1所列。

    实验发现，本文提出的RCCMA路由算法在能量高效性、可扩展性、鲁棒性和快速收敛性方面都比文中提到的几种典型路由算法优越。

4 结 论
    本算法有效地把粮仓底部大量分布不均的传感器节点进行了很好的路由，实现了整个网络的通信路径规划。其创新点是先提出一种分级簇区域算法，将大量分布不均的传感器节点进行了区域划分和级别设定。然后提出一种基于最小夹角的路由算法，实现了二级簇区域内节点问路由和一级簇区域与二级区域内目标节点问的路由。由于一级簇区域负责与邻近二级簇区域节点通信，同时负责与整个网络终极节点通信，所以能耗最大。但是一级簇区域内节点密度较高，本文采用轮转调度睡眠机制，每个节点在某时承担目标节点，将能耗平衡化，降低了单个节点的能耗。