一種基于哈希函數及能量均衡的事件查詢算法*

章才能，龔德良，李盛欣

(湘南學院計算機系，湖南 郴州 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

章才能(1978),男，湖南常寧人，碩士，講師，研究方向為無線傳感器網絡、網絡安全和云計算。E-mail:51809699@qq.com

通信地址：423000 湖南省郴州市湘南學院計算機系

Address:Department of Computer Science,Xiangnan University,Chenzhou 423000,Hunan,P.R.China