基于RSSI的分层定向扩散路由协议

郑 勇，徐玉斌，李学安(太原科技大学计算机科学与技术学院，太原 030024)

无线传感器网络[1](Wireless Sensor Networks，WSN)融合了通信技术、嵌入式技术和传感器技术，由散布于环境中的大量传感器节点组成。以数据为中心的计算(data centric computing)[2-3]是WSN的重要特征之一。在无线传感器网络中，从网络层面来看，中间节点不但要负责储存转发数据分组，而且还需要按照一定的规则对数据进行分析和处理；从应用层面来看，人们往往只关注获得的特定数据，而不会访问某个指定的传感器节点。

以数据为中心的路由(data centric routing)协议[4]，将路由计算和数据处理二者有机的结合起来。在现有的无线路由协议中，定向扩散(Directed Diffusion，DD)路由协议[5]是一种典型的以数据为中心的路由协议，它将应用层的需求、路由生产和数据的聚合三者结合起来。

在定向扩散路由协议中，汇聚节点根据不同的应用需求定义不同的兴趣(interest)消息，并通过泛洪(flooding)的方式将兴趣消息发送至全网或者局部网络的传感器节点。兴趣消息用来表示查询内容，反映终端用户希望获得全网不同类型的数据服务，例如，某监测区域中环境的温度、湿度、或该区域中的实时动态信息应用等。在进行兴趣消息泛洪同时，每个节点根据缓存中的兴趣列表，沿着兴趣消息传播的反方向建立梯度(gradient)，当兴趣消息到达匹配的源节点后，源节点将数据沿着建立好的传输梯度进行正向传输，直到汇聚节点。

在实际应用中，传感器节点的能量有限且一般没办法补充。为了延长节点的工作时间，要求高效的利用节点的能量。然而传统DD协议中周期性的泛洪兴趣、转发探测数据等操作导致能量开销过大，影响协议的效率和网络的生存期[6-7]。针对这些问题，许多学者提出了改进的办法，其中基于分簇的定向扩散协议[8]，降低了节点的平均能耗，明显的减少了网络中的兴趣消息冗余，但是对于簇首节点[9]的过度使用会使簇首节点因能耗过快而失效，从而影响网络的寿命。文献[10]提出了一种分层扩散(Ladder Diffusion，LD)算法，该算法在兴趣扩散过程中将网络中的节点进行分层，最后结合蚁群优化算法(Ant Colony Optimization，ACO)来确定一条最短传输路径。

1 分层扩散算法分析

传统定向扩散中兴趣消息泛洪传播最终能保证兴趣消息遍历全网，在一定程度上能够提高网络的健壮性。但是，在网络中以泛洪的方式来进行数据的传输，是一个极其耗费能量的过程，尤其对于大多电池不可更换的节点来说，泛洪传播给这些节点带来的能量损耗是巨大的。

文献[10]中的LD算法能使汇聚节点发出的兴趣消息由内层向外层逐层传播，直至找到数据源节点。在所有节点都静止不动的情况下，能够保证兴趣消息的快速扩散，并且大大减少扩散过程中兴趣消息的冗余，避免生成循环路线。 LD算法基本过程如图1所示。

图1分层扩散算法

Fig.1Ladderdiffusionalgorithm

在扩散阶段开始前，设置所有节点在初始状态下的层数值Level=0.LD算法描述如下：

(1)汇聚节点消息扩散过程，如图1中的(a)所示。在网络的开始时刻，汇聚节点要向网络中以广播的形式扩散兴趣消息，在汇聚节点一定范围内的节点收到来自于汇聚节点的兴趣消息后，将消息中所携带的层数值加1，并更新该节点中的Level值，然后将消息广播出去。

(2)中间节点消息扩散过程，如图1中的(b)、(c)所示。那些当前层数值为Level(Level≠0)的节点，将从汇聚节点收到的兴趣消息以一定的扩散半径广播出去。在这个过程中，若接收节点的层数值为0，则将消息中的Level值加1，并更新节点本身和消息中的Level值，然后将消息继续广播；若接收节点的层数值小于或等于消息中Level值，则表明消息是向低层传输或在同层间传输，这时直接将消息丢弃，不建立它们之间的链接。

通过上述过程，兴趣消息可遍历全网，直至找到匹配的数据源节点，如图1中的(d)所示，同时也实现了网络中节点的分层。

在文献10中，通过LD算法将网络分层后，依据蚁群优化算法(ACO)：①在源节点处初始化算法参数：蚂蚁路径选择率q0、环境信息素τ0和信息素挥发率∂，它们的取值均在0与1之间，开始状态蚂蚁随机行走并释放信息素；②新的蚂蚁从源节点处出发，依据各条路径上的信息素τ(i,j)选择信息素大的路径行走，然后更新局部信息素τ(i,j)；③蚂蚁都达到汇聚节点以后，更新全局信息素τ(i,j).重复进行②③步来建立一条含有信息素最多的路径，这条路径即为源节点与汇聚节点间的最短路径。在规模较小的网络中，采用ACO能很快的在几条路径中确定一条最短路径来进行数据的传输；但在大规模网络中，即使通过分层，网络中的路径依然很多，采用ACO必须经过多次迭代才能寻找到一条最短路径，实时性较差并且其算法复杂度也相对较高。

本文将RSSI与分层机制相结合，提出一种基于RSSI的分层定向扩散路由协议(Layered and Directed Diffusion Routing Protocol Based on RSSI，RSSI-LD)。该协议在兴趣分层扩散的过程中同时记录节点间的RSSI值[11]，采用RSSI值指示最短路径，可有效降低算法复杂度。同时对传统定向扩散协议进行改进，省去了数据探测和兴趣重发两个过程，大大减少了时延，降低了能耗。

2 基于RSSI的分层定向扩散路由协议RSSI-LD

传统定向扩散路由协议分为兴趣扩散、梯度建立、路径加强三个阶段。针对第2节描述的LD算法的不足，我们在DD协议的兴趣报文中添加层次信息和信号强度累加信息，其中层次信息用来记录节点的层数，信号强度累加信息用来记录节点所挑选的最大信号强度累加值。兴趣扩散阶段完成以后，就可以根据最大信号强度累加值直接确定最短路径，大大减少了网络时延、降低了能量损耗，非常适合于大规模传感器网络。RSSI-LD的操作主要分为如下两个过程。

2.1 兴趣扩散过程

在DD协议的兴趣扩散过程中，我们在兴趣数据包报文中添加一个层次信息和信号强度累加信息，在兴趣的传播中达到将网络中节点分层和记录路径代价的目的。

在这个过程中，首先进行网络初始化：网络中所有节点的层数值为0，兴趣消息为interest(level，Max_RSSI，Msg)，其中level为节点所在的层数值，初始值为0；Max_RSSI为节点所挑选出来的最大信号强度累加值(也即是汇聚节点到此节点的最短路径)，初始值为0；Msg为兴趣内容，可依据不同的命名方式得到。兴趣的扩散过程如图2所示。

图2 RSSI-LD的兴趣扩散过程

图2中，sink为汇聚节点，A、B、C和D、E、F及G、H为中间节点，source为与兴趣消息匹配的数据源节点。每个节点上的数值表示相邻节点间的信号强度值(RSSI).

汇聚节点向网络中广播兴趣interest，在其通信范围内的所有节点将收到该兴趣。

当网络中的任意一个节点i收到兴趣interest后，如果节点i所在的层数值为0，根据(1)、(2)式来更新此节点的层数值和最大信号强度累加值。

level+1->level

(1)

Max_RSSI+RSSI->Max_RSSI

(2)

如图2所示的A、B、C节点，它们都收到来自于sink节点的兴趣消息，依据(1)式更新兴趣消息中的层数值，得到A、B、C节点位于第1层；依据(2)式更新兴趣消息中的最大信号强度值，得到A、B、C节点的最大信号强度值分别为146、152、145.

如果i节点所在的层数值大于兴趣消息中的level，说明已有兴趣传送到该节点，此时直接用(2)式来更新新到兴趣消息中的Max_RSSI值，并与i节点中已有的Max_RSSI值进行比较，若新的Max_RSSI值大于已有的Max_RSSI值，则用新的Max_RSSI来替换已有的Max_RSSI，并更新路由信息；若新的Max_RSSI值小于已有的Max_RSSI值，则直接丢弃新到的兴趣消息，不建立它们间的链接。如图2所示的F、H节点，根据上述过程，对于节点F，我们保留Max_RSSI值为145+155=200的这条路径；同理，对于节点H，通过比较我们保留Max_RSSI值为451的这条路径(实线表示)。

如果i节点所在的层数值等于或小于兴趣消息中的level，说明兴趣消息在同层之间或高层向低层之间传输，直接丢弃此兴趣消息，不建立它们之间的链接。

网络中的任意一个节点均重复上述过程，就可以将网络中的节点进行分层，并记录下每个节点相对于汇聚节点的最大信号强度值(Max_RSSI).

2.2 数据传输过程

兴趣扩散的过程也就是梯度建立的过程。当节点收到来自不同邻居的兴趣消息时，通过比较兴趣消息中的Max_RSSI值，保留其中最大的信号强度累加值，从而建立一个指向该节点到上一层某个邻居节点的梯度。在发现匹配兴趣消息的源节点后，在源节点和汇聚节点之间就建立了一条有最大信号强度(Max_RSSI)的路径。源节点在采集到数据之后，直接沿着这条路径将数据传送到汇聚节点。如图2所示，源节点收到来自于节点G、H的兴趣消息，通过计算比较，保留Max_RSSI值为594的那条路径，然后数据将沿着source->H->E->B->sink这条路径直接进行数据传输。

传统的定向扩散路由中，由于兴趣的泛洪传播，会在网络的某些节点间形成环路，造成能量的浪费。RSSI-LD协议使用分层扩散算法，避免了网络中环路的出现，能够节省网络中的一部分能量并能降低网络中的兴趣消息冗余。在兴趣消息中加入Max_RSSI后，不再像传统定向扩散路由协议那样，在兴趣扩散阶段完成后，再沿着梯度方向发送探测数据到sink节点，由sink节点来加强其中的一条或多条路径来进行数据的传输，这样处理不利于数据传输的实时性。在兴趣扩散阶段完成后，依据Max_RSSI已经确定了一条最短路径，数据源节点在采集到数据后直接沿着确定的最短路径进行数据的传输，使网络的实时性得到提高。

3 仿真结果及分析

为了验证RSSI-LD协议的网络性能，本文基于NS-2[12]对DD协议和RSSI-LD协议在网络中的兴趣包数、节点平均能耗和时延性能上进行比较分析。

为了比较不同节点密度情况下协议的性能。设计6个不同规模的网络，节点数依次为50、100、150、200、250、300，所有节点随机分布在200 m′200 m的矩形区域中。相应的仿真参数如表1所示，其它参数依据原定向扩散协议设置。

表1 仿真参数 Tab.1 Network simulation parameters

通过对仿真跟踪文件进行分析，用gnuplot生成结果，得到不同网络规模下传统DD协议和RSSI-LD协议在网络中的兴趣包数、节点平均能耗和网络时延三个性能方面的比较关系分别如图3、图4、图5所示。

图3 不同场景下网络中的兴趣数量

图3比较了DD和RSSI-LD协议随着网络中节点数的增加，某一时刻网络中兴趣消息数的变化情况。从图中可以看出，随着节点数的增加，二者在网络中的兴趣数均增加，但是RSSI-LD协议中的网络兴趣消息数要小于DD协议，尤其是在节点数目较多的网络中，这种差别更加明显。这是因为RSSI-LD协议在兴趣的扩散过程中使用分层扩散算法，减少了同层节点间及高层与低层节点间的信息传输，能够有效的避免消息的重传，从而能够减少网络中的兴趣消息数，减少网络中兴趣消息的冗余。

图4 不同场景下节点的平均能耗

图4比较了随着网络中节点数的增加，DD和RSSI-LD协议节点的平均能耗的变换情况。从图中可以看出，RSSI-LD协议的节点平均能耗要明显低于DD协议的节点平均能耗。当网络中节点数目的个数为50时，新协议的能耗占传统DD协议能耗的89.2%，当网络中节点数目的个数为300时，新协议的能耗占传统DD协议能耗的62.35%.这是因为网络中的节点数目越多，通过分层进行兴趣扩散，在兴趣扩散过程中，使兴趣在层与层之间进行传输，减少了重发信息所消耗的能量，同时RSSI-LD协议没有数据探测过程，也节省了一部分能量。

图5表明不同场景下，传统DD协议和RSSI-LD协议从sink节点发送interest到sink节点收到来自于source节点的稳定消息的相应响应时间。从图可以看出，RSSI-LD协议的响应时间要明显小于DD协议的响应时间。这是因为，在兴趣消息的扩散过程中，结合RSSI并记录节点MAX_RSSI，在兴趣消息传送到source后，直接依据Max_RSSI来确定一条最短路径进行数据的传输。省去了传统DD协议中数据探测过程和确定路径过程，网络的时延大大降低，提高了网络的实时性。

图5 不同场景下网络的延迟

4 结束语

本文基于分层和RSSI机制，提出基于RSSI的分层定向扩散路由协议(RSSI-LD).在兴趣扩散阶段结合分层扩散算法，并在兴趣报文中加入Max_RSSI信息。兴趣扩散过程中实现了网络节点分层，同时确定了每一个节点上的MAX_RSSI值。在兴趣消息扩散到匹配的源节点后，源节点就根据MAX_RSSI值来确定进行数据传输的路径，MAX-RSSI值最大的路径即为源节点和汇聚节点间距离最短的路径。基于NS-2的仿真实验结果表明，与传统DD协议相比，RSSI-LD协议在网络平均能耗、网络中兴趣传播数量以及网络延迟等方面均得到显著改善，对于大规模、密集型网络尤其明显。

参考文献：

[1] 孙利民，李建中，陈渝.无线传感器网络[M].北京：清华大学出版社，2005.

[2] AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.A survey on sensor networks[J].Communications magazine，IEEE，2002，40(8)：102-114.

[3] REN F Y，HUANG H N，LIN C.Wireless sensor networks[J].Journal of software，2003，14(7)：1282-1291.

[4] KRISHNAMACHARI B，ESTRIN D，WICKER S.Modelling data-centric routing in wireless sensor networks[C]∥IEEE infocom.USA：New York，2002.

[5] INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al.Directed diffusion for wireless sensor networking[J].Networking，IEEE/ACM Transactions on，2003，11(1)：2-16.

[6] AKKAYA K，YOUNIS M.A survey on routing protocols for wireless sensor networks[J].Ad hoc networks，2005，3(3)：325-349.

[7] SHAH R C，RABAEY J M.Energy aware routing for low energy ad hoc sensor networks[C]∥2002 IEEE Wireless Communications and Networking Conference.USA，2002.

[8] LIU X，LI F，KUANG H，et al.The study of directed diffusion routing protocol based on clustering for wireless sensor network[J].IEEE，2006(2)：5120-5124.

[9] 吉云，徐玉斌.基于地理位置划分的无线传感器网络分簇算法[J].太原科技大学学报，2010,31(1)：6-9.

[10] HO J H，SHIH H C，LIAO B Y，et al.A ladder diffusion algorithm using ant colony optimization for wireless sensor networks[J].Information Sciences，2012，192：204-212.

[11] 冯爱丽，乔钢柱，曾建潮.基于信标节点间距离的改进 RSSI 定位算法[J].太原科技大学学报，2012，33(1)：6-9.

[12] 柯志亨，程荣祥，邓德隽.NS2 仿真实验——多媒体和无线网络通信[M].北京：电子工业出版社，2009.