一种基于哈希函数及能量均衡的事件查询算法*

2014-09-13章才能龚德良李盛欣

计算机工程与科学 2014年11期

关键词：能量消耗路由传感器

章才能，龚德良，李盛欣

(湘南学院计算机系，湖南郴州 423000)

一种基于哈希函数及能量均衡的事件查询算法*

章才能，龚德良，李盛欣

(湘南学院计算机系，湖南郴州 423000)

在无线传感器网络中对于无固定位置的事件及查询是个重要的研究课题。结合高效及最大化网络生命周期，提出了一种基于哈希函数及能量均衡的事件查询算法。在该算法中，一个传感器节点只需要关心自己通信范围内的邻居节点，不需要知道整个网络的状况，算法具有冗余数据少、查询能耗小、网络生命周期长、实现简单等特点。借助OMNET++网络模拟器进行仿真实验，与经典路由算法比较，结果表明本算法能快速高效地进行事件查询，同时最小化及均衡能量消耗，延长了网络生命周期。

无线传感器网络；哈希函数；能量均衡；事件查询；OMNET++

1 引言

无线传感器网络是计算机、通信和传感器三项技术相结合的产物，近年来得到了飞速发展，已成为计算机科学领域一个活跃的研究分支[1]。该网络的功能是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者[2]。与传统网络相比，无线传感器网络具有以下特点：(1)节点数量大、分布范围广；(2)以数据为中心进行路由传输；(3)能量受限的网络；(4)随应用需求的不同而变化，网络系统与应用密切相关；(5)相邻节点间采集的数据具有相似性，存在冗余信息。这些特点决定了无线传感器网络中的事件查询算法设计受到更多的限制，必须考虑更多的因素，传统的查询算法已经不能满足无线传感器网络中用户查询的需要。在所有无线传感器网络的应用中，最基本的问题是：发生的事件被临近的节点快速地感测到，并将此数据信息顺利地传送到与之感兴趣的查询节点，查询的需求与事件的发生随时随地都有可能发生[3]。在这种需求下，设计能量节省及快速高效的网络路由通信协议是一个相当基本且重要的问题。

2 相关研究

先前的研究方法大多采用固定的Sink节点利用构造路由路径来收集整个事件的信息，但是现在的问题是有了新的挑战：无固定位置的事件需传送到另一个无固定位置的查询。若每次传送前都使用Flooding来寻路，会使整个网络都充满寻路的数据包，同时导致每个传感器节点消耗过多的能量，所以新的通信协议必须更具有机动性和能量节省的特性。

在无线传感器网络中，有效地寻找出查询与事件之间的路径，传统的方法有Flooding[4]、Cluster[5]和Gradient[6]，或是之后提出的Rumor Routing[7]和Random Walk[8]。但是,以Flooding的方式固然可以有效地找到最短的路径，可是在能量消耗上却是相当的惊人，只要一有事件或是查询发生就需要所有的节点消耗能量在寻找路径上，如果一个地区时常有不同的事件或是查询发生，那么所有的资源几乎都会消耗在寻找路径上，这样会导致整个网络的生命周期变短。在以Random Walk方法寻找事件时，在使用GPS的情况下，每个节点在收到数据信息后，再去计算与事件的距离，从而使得数据信息可以逐步靠近所需要的终点。在这个方法中，需要GPS装置，而GPS装置就会增加整个无线传感器网络的成本。文献[7]在不使用GPS装置的情况下，提出了Rumor路由算法，可是Rumor路由算法虽然可以改善Flooding路由算法的能量消耗问题，但是没有办法找到较短的路径，而且会有回路问题，更甚至于在有回路的状况下，根本就没有办法找到适当的路径连接查询与事件；并在Rumor路由算法中，虽然可以通过控制所发出的代理程序数量的多少来减少找不到的情况发生，但过多的代理程序一样会增加传感器节点能量的消耗。

3 HFEBEQ算法

在无线传感器网络中，对于一个需要随时随地传送数据信息的通信协议应该具备以下特性：尽可能节省能量；尽可能不使用GPS设备；可随时随地地传送；具有容错和稳健功能。根据以上特性，本文提出了一个新的算法HFEBEQ(Hash Function and Energy Balance Event Query)。该算法分为两个阶段：(1)拓扑扩散阶段：在无线传感器网络边界上选择最外围的传感器节点作为根节点，向邻居节点广播信息，其中包括跳数字段和距离字段，初值都设为0，当邻居节点接收信息后，将跳数值加1；接着各邻居节点又以同样方式向各自的邻居节点广播信息，将跳数值逐渐累加1，作为对根节点的跳数；最后到了没有邻居节点结束，就是到了无线传感器网络的另一边界，这样就把无线传感器网络相对于根节点分成了若干个跳数层。同时，各节点在邻居节点信息表中记录了各自邻居节点的相关信息。(2)事件查询阶段：当有事件发生时，感知节点根据设定的哈希函数映射出相应的跳数层，再根据节点状态和路径能量消耗函数把数据信息传输到相应跳数层的某个节点，这个节点再把数据信息传输给同层的节点；当有查询发生时，查询节点同样根据设定的哈希函数映射出相应的跳数层，再根据节点状态和路径能量消耗函数找到相应跳数层的某个节点，此时查询与事件之间连接成功，可以开始传输数据信息。

3.1 网络模型

假设无线传感器网络中存在以下特性[9]：所有传感器节点固定，不存在Sink节点，节点携带有限电池，不携带GPS设备，每个节点具有相同特性且分配唯一ID，具有事件监测和查询功能，节点可以通过接收到的信号强度估算相邻节点间的近似距离。

3.2 能量模型

基于通用的能量消耗模型[10]，在两个相距d米的相邻节点间传输一k比特位数据包，其传输和接收的能量消耗分别为：

(1)

(2)

其中，Eelec表示电池能量，Eamp表示发送放大功率。

3.3 哈希函数

建立哈希函数H(k)，k为事件类型属性值，将事件和查询数据标识中的特定属性值关键字k哈希映射到相应的跳数层，并根据节点状态和路径能量消耗函数选择该跳数层的某个节点为存取点。

算法支持存和取两种相关操作：

(1)Put(k,v)：基于监测数据属性值的关键字为k的监测数据v；

(2)Get(k)：获取属性值关键字为k的监测数据。

特定的k值通过Put()操作或Get()操作都将映射到相同的跳数层，从而使对k-v对的存或取都在同一跳数层上进行。

对于用户感兴趣的事件分为几种类型，每种类型有一个唯一的关键字。通过设置哈希函数H(k)，关键字被映射到相应的跳数层。即有：

(3)

其中，E是事件类型集合，T是跳数层集合。

3.4 HFEBEQ算法描述

本文提出的HFEBEQ算法分为两个阶段：拓扑扩散阶段和事件查询阶段。

(1)拓扑扩散阶段。

在无线传感器网络边界上选择最外围的传感器节点作为根节点，开始以洪泛方式向邻居节点广播信息，其中包括跳数字段和距离字段，初始值都为0。当邻居节点接收信息后，将跳数值加1，同时节点Ni传送信息包给节点Nj，满足以下方程式：

d(i,j)

(4)

(5)

其中，Rangei表示节点Ni的传感范围，d(i,s)表示节点Ni到根节点的距离，d(i,j)表示节点Ni到节点Nj的距离。为了确定发送节点和接收节点间的距离，接收节点通过接收数据包的信号强度可以估算两个节点间的近似距离。

每个节点都有一张邻居节点信息表，其结构如表1所示。

Table 1 Information structure of neighbor node表1 邻居节点信息表结构

当节点收到信息包，就更新邻居节点信息表。节点状态通过节点剩余能量与临界值α(临界值αi取值为节点Ni邻居节点中剩余能量值最大的一半)比较确定。如果剩余能量小于选定的临界值α，就不是相关节点，否则是相关节点；当过了一段时间后，剩余能量大于重新选定的临界值α，节点就可以从非相关状态转换到相关状态。接着计算发送信息包的邻居节点路径能量消耗，如果数据信息包从节点Nj发送到节点Ni，节点Ni计算能量消耗公式为：

(6)

(7)

(8)

Ri表示节点Ni的剩余能量，Et+Er表示节点Ni与节点Nj连通路径发送和接收数据信息包消耗的能量。接着各邻居节点又以同样的方式向各自的邻居节点广播信息，将跳数值逐渐累加1，作为对根节点的跳数。最后到了没有邻居节点结束也就是到了无线传感器网络的另一相对边界，这样就把无线传感器网络相对于根节点分成了若干个跳数层，如图1所示，具体算法如算法1所示。

Figure 1 Wireless sensor network hops distribution map图1 无线传感器网络跳数分布图

算法1HFEBEQ算法初始化

//确定每个节点与指定初始化节点的跳数

1. random select nodeAas initial node; /*选择的任意节点作为起始节点*/

2. For 节点Ni接收到数据信息包 do

3.Ni.hops+1;//把接收到的跳数值加1

4. if 节点Nj在节点Ni和根节点之间 then

5. ifNj·Rj>αithen/*节点Nj剩余能量Rj大于临界值αi*/

6.Nj.Status=1；/*节点Nj状态标记为相关节点*/

7. 计算节点Ni到节点Nj的能量消耗；

8. else

9.Nj.Status=0；/*节点Nj状态标记为非相关节点*/

10. end if

11. 增加节点Nj到节点Ni的邻居节点信息表中；

12. else

13. 节点Ni丢弃这个数据信息包；

14. end if

15. end for

(2)事件查询阶段。

当一个节点监测到相应的某一个事件时，根据设定的哈希函数映射得到相应的跳数层，接着通过

多跳的形式发送数据信息包给相应的跳数层的某个节点，这个节点再把数据信息传输给同层的节点。监测事件节点及中间节点通过节点状态和最小路径能量消耗在邻居节点信息表中搜寻下一跳邻居节点，因此选择同一个节点作为下一跳节点的概率减少了，也就是可能事件相同也不会始终使用一条路由路径传输数据信息。这样在节点上可以存储更多的能量，达到了能量均衡的目的，从而也延长了网络的生命周期。依次搜寻选择下一跳邻居节点，直到数据信息包传输到相应的跳数层的某个节点，具体算法如算法2所示。

算法2HFEBEQ算法事件信息的存储

1.j=h(K);/*节点监测到事件时，根据设定的哈希函数映射得到相应的跳数层*/

2. ForNj.hops=jdo

3. 节点Nj向同跳数层的邻居节点传输数据信息包；

4. For 节点Ni接收到的数据信息包 do

5. if 节点Ni邻居节点信息表不为空 then

6. ifNj.Status=1 and 最小路径能量消耗 then

7. 选择下一跳邻居节点Nj；

8. end if

9. else

10. 重新选定临界值αi；

11. 重新确定节点Ni邻居节点状态；

12. ifNj.Status=1 and 最小路径能量消耗 then

13. 选择下一跳邻居节点Nj；

14. end if

15. end if

16. 发送数据信息包给节点Nj；

17. end for

18. end for

当有查询发生时，查询节点同样根据设定的哈希函数映射出相应的跳数层，再根据节点状态和路径能量消耗函数找到相应跳数层的某个节点。此时，查询与事件之间完成连接，数据信息可以沿着查询的原路径传输给查询节点。具体算法如算法3所示。

算法3HFEBEQ算法查询事件信息

1.j=h(K) /*查询节点根据设定的哈希函数映射得到相应的跳数层*/

2. ForNj.hops=jdo

3. 节点Nj传输数据信息包给查询节点；

4. For 节点Ni接收到的数据信息包 do

5. if 节点Ni邻居节点信息表不为空 then

6. ifNj.Status=1 and 最小路径能量消耗 then

7. 选择下一跳邻居节点Nj；

8. end if

9. else

10. 重新选定临界值αi；

11. 重新确定节点Ni邻居节点状态；

12. ifNj.Status=1 and 最小路径能量消耗 then

13. 选择下一跳邻居节点Nj；

14. end if

15. end if

16. 发送数据信息包给节点Nj；

17. end for

18. end for

假设A节点监测了某个事件发生，通过设定的哈希函数映射出相应的跳数层为7，根据节点状态和路径能量消耗函数传输数据信息到相应跳数层为7的某个节点，这个节点再把数据信息传输给同层的节点；同样假设B节点要查询相应的事件信息，通过设定的哈希函数映射出相应的跳数层为7，根据节点状态和路径能量消耗函数找到相应跳数层为7的某个节点。此时，查询与事件之间完成连接，数据信息可以沿着查询的原路径传输给查询节点，也就意味着B节点知道了事件发生在A节点处。如图2所示。

Figure 2 Schematic diagram of event query图2 事件查询阶段示意图

4 仿真实验及分析

借助OMNET++网络模拟器[11]，对本文中的事件查询算法与Flooding路由算法[4]和Rumor路由算法[7]进行平均能量消耗、时间延迟和网络生命周期三个性能测试比较，只考虑其数据传送过程中的能耗和时间延迟。仿真环境使用的面积大小为1 000 m×1 000 m，节点个数从50到800逐渐增加且均匀分布在区域里，其它实验参数如表2所示。

Table 2 Experimental parameters表2 实验参数

网络平均能量消耗等于N个节点能量消耗累加和的平均值，节点能量消耗等于初始能量值减去剩余能量值。图3的仿真实验结果表明本文中的事件查询算法比Flooding路由算法及Rumor路由算法的平均能量消耗要小很多。因为本文中的事件查询算法在拓扑扩散阶段只仅仅使用了一次洪泛方式广播，而在Flooding路由算法中只要有事件或查询发生都会使用洪泛方式广播；对于Rumor路由算法查询需要n条查询路径，查询路径越多，查询消耗的能量越多；本文中的事件查询算法在选择邻居节点的时候根据节点状态和路径能量消耗函数进行能量均衡选择，因此选择同一个节点作为下一跳节点的概率减少了，在节点上可以存储更多的能量，达到了能量平衡和公平使用节点的目的。

Figure 3 Comparison of average energy consumption图3 平均能量消耗比较图

时间延迟是指查询到相应事件信息的时间间隔。图4的仿真实验结果表明，本文中的事件查询算法比Flooding路由算法及Rumor路由算法的时间延迟要小很多。因为本文中的事件查询算法在查询相关事件信息时，目的非常明确且通过设定的哈希函数能够快速定位；而Flooding算法不考虑用户需求定期将大量数据传给Sink节点，Sink节点负责数据的融合处理，再返回给用户需要的事件信息，同时频繁地使用洪泛方式广播会造成网络拥塞而延长了时间延迟；Rumor路由算法没有办法找到较短的路径，而且会有回路问题，更甚至于在回路的状况下，根本就没有办法找到适当的路径连接查询与事件。

Figure 4 Comparison of time delay图4 时间延迟比较图

网络生命周期是无线传感器网络最重要的性能参数之一。本文的网络生命周期定义为网络中第一个节点能量消亡的时间。图5的仿真实验结果表明，本文中的事件查询算法比Flooding路由算法及Rumor路由算法网络生命周期要长。因为本文中的事件查询算法利用了不同的发现路径传输数据，使用了路径能量消耗函数及节点的状态，在高能量节点中分散了能量负载，在不同的节点间减小了能量差距，从而延长了网络的生命周期，确保了能量均衡和避免了网络过早的消亡；而Flooding路由算法频繁地使用洪泛方式广播，需要所有的节点消耗能量在寻找路径上，导致整个网络的生命周期变短；Rumor路由算法可以通过控制所发出代理程序数量的多少来减少找不到的情况发生，但过多的代理程序一样会增加传感器节点能量的消耗，即查询路径越多，查询消耗的能量越多，最终导致整个网络的生命周期变短。

Figure 5 Comparison of network life cycle图5 网络生命周期比较图

5 结束语

在无线传感器网络中对于无固定位置的事件及查询，在设计路由协议时最重要的性能是快速、高效且节省能量。传感器能量消耗主要在数据传输和接收，因此路由设计对于节能方面应该尽可能延长单个传感器及整个网络的生命周期，其主要目标是优化能量消耗。本文提出的基于哈希函数及能量均衡的事件查询算法，目的非常明确且通过设定的哈希函数能够快速定位，用最小的路径能量消耗在邻居节点信息表中查找所有相关的邻居节点。仿真实验结果表明，本文算法能快速高效地进行事件查询，在传感器节点间达到了最小化和平衡能量消耗，从而延长了网络的生命周期。但是，该算法是在假设节点非移动的理想情况下提出的，当网络中节点开始死亡或者节点大规模移动时事件查询就会遇到一定困难，这是今后要研究的重点问题。

[1] Ren Hui-jin,Dai Xiao-hua,Wang Zhi.System design of node of wireless sensor network[J]. Journal of Electronic Measurement and Instrument, 2006,20(6):31-35.(in Chinese)

[2] Li J Z,Li J B,Shi S F.Concepts,issues and advance of sensor networks and data management of sensor networks[J].Journal of Software,2003,14 (10):1717-1727.(in Chinese)

[3] Guo Long-jiang, Li Jian-zhong, Li Gui-lin. Spatio-temporal query processing method in wireless sensor networks[J]. Journal of Software, 2012,7(4):794-805.(in Chinese)

[4] Karp B, Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proc of the ACM/IEEE International Conference on Mobile Computing and Networking,2010:243-254.

[5] Sun K,Peng P,Ning P,et al.Secure distributed cluster formation in wireless sensor networks[C]∥Proc of the 22nd Annual Computer Security Applications Conference, 2008:131-140.

[6] Intanagonwiwat C,Govindan R,Estrin D.Directed diffusion:A scalable and robust communication paradigm for sensor networks[C]∥Proc of the 6th Annual International Conference on Mobile Computing and Networking,2010:56-67.

[7] Braginsky D, Estrin D. Rumor routing algorithm for sensor networks[C]∥Proc of the 1st ACM Workshop on Sensor Networks and Applications, 2012:22-31.

[8] Rezaei B A, Sarshar N, Roychowdhury V P. Random walks in dynamic small-world space:Robust routing in large-scale sensor networks[C]∥Proc of Vehicular Technology Conference,2009:4640-4644.

[9] Heinzelman W,Kulik J,Balakrishnan H.Adaptive protocols for information dissemination in wireless sensor networks[C]∥Proc of ACM/IEEE International Conference on Mobile Computing and Networking,2009:174-185.

[10] Tao M, Lu D, Yang J. An adaptive energy-aware multi-path routing protocol with load balance for wireless sensor networks[J].Wireless Personal Communications Journal,2012,63(4):823-846.

[11] OMNET++ Community Site [EB/OL].[2011-09-01].http://www.omnetpp.org/.

附中文参考文献:

[1] 任绘锦,戴晓华,王智.无线传感器网络节点的系统设计[J].电子测量与仪器学报,2009,20(6):31-35.

[2] 李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展[J].软件学报，2003,14(10):1717-1727.

[3] 郭龙江,李建中,李贵林.无线传感器网络环境下时空查询处理方法[J]. 软件学报, 2012, 7(4):794-805.

ZHANGCai-neng,born in 1978,MS,lecturer,his research interests include wireless sensor networks,network security, and cloud computing.

龚德良(1962),男，湖南益阳人，教授，研究方向为信息安全与计算机教育。E-mail:gdl2865605@163.com

GONGDe-liang,born in 1962,professor,his research interests include information security, and computer education.

李盛欣(1981),男，湖南郴州人，硕士，讲师，研究方向为无线传感器网络和网格计算。E-mail:7188115@qq.com

LISheng-xin,born in 1981,MS,lecturer,his research interests include wireless sensor networks, and grid computing.

AneventqueryalgorithmbasedonHashfunctionandenergybalancing

ZHANG Cai-neng，GONG De-liang，LI Sheng-xin

(Department of Computer Science，Xiangnan University，Chenzhou 423000，China)

Unfixed location events and queries in wireless sensor networks is an important research topic.To achieve efficiency and maximizing the network life cycle, we propose an event query algorithm based on Hash function and energy balancing.In the algorithm,a sensor node only needs to care about the neighbor nodes within its communication range while not knowing the status of the entire network.The algorithm features less redundant data,less query energy consumption, a longer network life cycle, and ease of implementation.The simulation experiments in OMNET++ network simulator show that,compared with the classic routing algorithm, the proposed algorithm can query events quickly and effectively,while minimizing and balancing the energy consumption and prolonging the network life cycle.

wireless sensor networks;hash function;energy balancing;event query;OMNET++

1007-130X(2014)11-2142-06

2014-06-20;

：2014-08-15

湖南省教育厅科技资助项目(12C0884)；湖南省教育科学“十二五”规划课题资助项目(XJK012CGD034)；郴州市科技计划资助项目(2012cj120)；湖南省普通高校“十二五”网络工程专业综合改革试点资助项目(湘教通[2012]112号);湘南学院计算机应用技术重点学科资助项目

TP393

：A

10.3969/j.issn.1007-130X.2014.11.015