章才能，龔德良，李盛欣

(湘南學(xué)院計(jì)算機(jī)系，湖南 郴州 423000)

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

章才能，龔德良，李盛欣

(湘南學(xué)院計(jì)算機(jī)系，湖南 郴州 423000)

在無線傳感器網(wǎng)絡(luò)中對(duì)于無固定位置的事件及查詢是個(gè)重要的研究課題。結(jié)合高效及最大化網(wǎng)絡(luò)生命周期，提出了一種基于哈希函數(shù)及能量均衡的事件查詢算法。在該算法中，一個(gè)傳感器節(jié)點(diǎn)只需要關(guān)心自己通信范圍內(nèi)的鄰居節(jié)點(diǎn)，不需要知道整個(gè)網(wǎng)絡(luò)的狀況，算法具有冗余數(shù)據(jù)少、查詢能耗小、網(wǎng)絡(luò)生命周期長、實(shí)現(xiàn)簡單等特點(diǎn)。借助OMNET++網(wǎng)絡(luò)模擬器進(jìn)行仿真實(shí)驗(yàn)，與經(jīng)典路由算法比較，結(jié)果表明本算法能快速高效地進(jìn)行事件查詢，同時(shí)最小化及均衡能量消耗，延長了網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；哈希函數(shù)；能量均衡；事件查詢；OMNET++

1 引言

無線傳感器網(wǎng)絡(luò)是計(jì)算機(jī)、通信和傳感器三項(xiàng)技術(shù)相結(jié)合的產(chǎn)物，近年來得到了飛速發(fā)展，已成為計(jì)算機(jī)科學(xué)領(lǐng)域一個(gè)活躍的研究分支[1]。該網(wǎng)絡(luò)的功能是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對(duì)象的信息，并發(fā)布給觀察者[2]。與傳統(tǒng)網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有以下特點(diǎn)：(1)節(jié)點(diǎn)數(shù)量大、分布范圍廣；(2)以數(shù)據(jù)為中心進(jìn)行路由傳輸；(3)能量受限的網(wǎng)絡(luò)；(4)隨應(yīng)用需求的不同而變化，網(wǎng)絡(luò)系統(tǒng)與應(yīng)用密切相關(guān)；(5)相鄰節(jié)點(diǎn)間采集的數(shù)據(jù)具有相似性，存在冗余信息。這些特點(diǎn)決定了無線傳感器網(wǎng)絡(luò)中的事件查詢算法設(shè)計(jì)受到更多的限制，必須考慮更多的因素，傳統(tǒng)的查詢算法已經(jīng)不能滿足無線傳感器網(wǎng)絡(luò)中用戶查詢的需要。在所有無線傳感器網(wǎng)絡(luò)的應(yīng)用中，最基本的問題是：發(fā)生的事件被臨近的節(jié)點(diǎn)快速地感測到，并將此數(shù)據(jù)信息順利地傳送到與之感興趣的查詢節(jié)點(diǎn)，查詢的需求與事件的發(fā)生隨時(shí)隨地都有可能發(fā)生[3]。在這種需求下，設(shè)計(jì)能量節(jié)省及快速高效的網(wǎng)絡(luò)路由通信協(xié)議是一個(gè)相當(dāng)基本且重要的問題。

2 相關(guān)研究

先前的研究方法大多采用固定的Sink節(jié)點(diǎn)利用構(gòu)造路由路徑來收集整個(gè)事件的信息，但是現(xiàn)在的問題是有了新的挑戰(zhàn)：無固定位置的事件需傳送到另一個(gè)無固定位置的查詢。若每次傳送前都使用Flooding來尋路，會(huì)使整個(gè)網(wǎng)絡(luò)都充滿尋路的數(shù)據(jù)包，同時(shí)導(dǎo)致每個(gè)傳感器節(jié)點(diǎn)消耗過多的能量，所以新的通信協(xié)議必須更具有機(jī)動(dòng)性和能量節(jié)省的特性。

在無線傳感器網(wǎng)絡(luò)中，有效地尋找出查詢與事件之間的路徑，傳統(tǒng)的方法有Flooding[4]、Cluster[5]和Gradient[6]，或是之后提出的Rumor Routing[7]和Random Walk[8]。但是,以Flooding的方式固然可以有效地找到最短的路徑，可是在能量消耗上卻是相當(dāng)?shù)捏@人，只要一有事件或是查詢發(fā)生就需要所有的節(jié)點(diǎn)消耗能量在尋找路徑上，如果一個(gè)地區(qū)時(shí)常有不同的事件或是查詢發(fā)生，那么所有的資源幾乎都會(huì)消耗在尋找路徑上，這樣會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)的生命周期變短。在以Random Walk方法尋找事件時(shí)，在使用GPS的情況下，每個(gè)節(jié)點(diǎn)在收到數(shù)據(jù)信息后，再去計(jì)算與事件的距離，從而使得數(shù)據(jù)信息可以逐步靠近所需要的終點(diǎn)。在這個(gè)方法中，需要GPS裝置，而GPS裝置就會(huì)增加整個(gè)無線傳感器網(wǎng)絡(luò)的成本。文獻(xiàn)[7]在不使用GPS裝置的情況下，提出了Rumor路由算法，可是Rumor路由算法雖然可以改善Flooding路由算法的能量消耗問題，但是沒有辦法找到較短的路徑，而且會(huì)有回路問題，更甚至于在有回路的狀況下，根本就沒有辦法找到適當(dāng)?shù)穆窂竭B接查詢與事件；并在Rumor路由算法中，雖然可以通過控制所發(fā)出的代理程序數(shù)量的多少來減少找不到的情況發(fā)生，但過多的代理程序一樣會(huì)增加傳感器節(jié)點(diǎn)能量的消耗。

3 HFEBEQ算法

在無線傳感器網(wǎng)絡(luò)中，對(duì)于一個(gè)需要隨時(shí)隨地傳送數(shù)據(jù)信息的通信協(xié)議應(yīng)該具備以下特性：盡可能節(jié)省能量；盡可能不使用GPS設(shè)備；可隨時(shí)隨地地傳送；具有容錯(cuò)和穩(wěn)健功能。根據(jù)以上特性，本文提出了一個(gè)新的算法HFEBEQ(Hash Function and Energy Balance Event Query)。該算法分為兩個(gè)階段：(1)拓?fù)鋽U(kuò)散階段：在無線傳感器網(wǎng)絡(luò)邊界上選擇最外圍的傳感器節(jié)點(diǎn)作為根節(jié)點(diǎn)，向鄰居節(jié)點(diǎn)廣播信息，其中包括跳數(shù)字段和距離字段，初值都設(shè)為0，當(dāng)鄰居節(jié)點(diǎn)接收信息后，將跳數(shù)值加1；接著各鄰居節(jié)點(diǎn)又以同樣方式向各自的鄰居節(jié)點(diǎn)廣播信息，將跳數(shù)值逐漸累加1，作為對(duì)根節(jié)點(diǎn)的跳數(shù)；最后到了沒有鄰居節(jié)點(diǎn)結(jié)束，就是到了無線傳感器網(wǎng)絡(luò)的另一邊界，這樣就把無線傳感器網(wǎng)絡(luò)相對(duì)于根節(jié)點(diǎn)分成了若干個(gè)跳數(shù)層。同時(shí)，各節(jié)點(diǎn)在鄰居節(jié)點(diǎn)信息表中記錄了各自鄰居節(jié)點(diǎn)的相關(guān)信息。(2)事件查詢階段：當(dāng)有事件發(fā)生時(shí)，感知節(jié)點(diǎn)根據(jù)設(shè)定的哈希函數(shù)映射出相應(yīng)的跳數(shù)層，再根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)把數(shù)據(jù)信息傳輸?shù)较鄳?yīng)跳數(shù)層的某個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)再把數(shù)據(jù)信息傳輸給同層的節(jié)點(diǎn)；當(dāng)有查詢發(fā)生時(shí)，查詢節(jié)點(diǎn)同樣根據(jù)設(shè)定的哈希函數(shù)映射出相應(yīng)的跳數(shù)層，再根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)找到相應(yīng)跳數(shù)層的某個(gè)節(jié)點(diǎn)，此時(shí)查詢與事件之間連接成功，可以開始傳輸數(shù)據(jù)信息。

3.1 網(wǎng)絡(luò)模型

假設(shè)無線傳感器網(wǎng)絡(luò)中存在以下特性[9]：所有傳感器節(jié)點(diǎn)固定，不存在Sink節(jié)點(diǎn)，節(jié)點(diǎn)攜帶有限電池，不攜帶GPS設(shè)備，每個(gè)節(jié)點(diǎn)具有相同特性且分配唯一ID，具有事件監(jiān)測和查詢功能，節(jié)點(diǎn)可以通過接收到的信號(hào)強(qiáng)度估算相鄰節(jié)點(diǎn)間的近似距離。

3.2 能量模型

基于通用的能量消耗模型[10]，在兩個(gè)相距d米的相鄰節(jié)點(diǎn)間傳輸一k比特位數(shù)據(jù)包，其傳輸和接收的能量消耗分別為：

(1)

(2)

其中，Eelec表示電池能量，Eamp表示發(fā)送放大功率。

3.3 哈希函數(shù)

建立哈希函數(shù)H(k)，k為事件類型屬性值，將事件和查詢數(shù)據(jù)標(biāo)識(shí)中的特定屬性值關(guān)鍵字k哈希映射到相應(yīng)的跳數(shù)層，并根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)選擇該跳數(shù)層的某個(gè)節(jié)點(diǎn)為存取點(diǎn)。

算法支持存和取兩種相關(guān)操作：

(1)Put(k,v)：基于監(jiān)測數(shù)據(jù)屬性值的關(guān)鍵字為k的監(jiān)測數(shù)據(jù)v；

(2)Get(k)：獲取屬性值關(guān)鍵字為k的監(jiān)測數(shù)據(jù)。

特定的k值通過Put()操作或Get()操作都將映射到相同的跳數(shù)層，從而使對(duì)k-v對(duì)的存或取都在同一跳數(shù)層上進(jìn)行。

對(duì)于用戶感興趣的事件分為幾種類型，每種類型有一個(gè)唯一的關(guān)鍵字。通過設(shè)置哈希函數(shù)H(k)，關(guān)鍵字被映射到相應(yīng)的跳數(shù)層。即有：

(3)

其中，E是事件類型集合，T是跳數(shù)層集合。

3.4 HFEBEQ算法描述

本文提出的HFEBEQ算法分為兩個(gè)階段：拓?fù)鋽U(kuò)散階段和事件查詢階段。

(1)拓?fù)鋽U(kuò)散階段。

在無線傳感器網(wǎng)絡(luò)邊界上選擇最外圍的傳感器節(jié)點(diǎn)作為根節(jié)點(diǎn)，開始以洪泛方式向鄰居節(jié)點(diǎn)廣播信息，其中包括跳數(shù)字段和距離字段，初始值都為0。當(dāng)鄰居節(jié)點(diǎn)接收信息后，將跳數(shù)值加1，同時(shí)節(jié)點(diǎn)Ni傳送信息包給節(jié)點(diǎn)Nj，滿足以下方程式：

d(i,j)

(4)

(5)

其中，Rangei表示節(jié)點(diǎn)Ni的傳感范圍，d(i,s)表示節(jié)點(diǎn)Ni到根節(jié)點(diǎn)的距離，d(i,j)表示節(jié)點(diǎn)Ni到節(jié)點(diǎn)Nj的距離。為了確定發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)間的距離，接收節(jié)點(diǎn)通過接收數(shù)據(jù)包的信號(hào)強(qiáng)度可以估算兩個(gè)節(jié)點(diǎn)間的近似距離。

每個(gè)節(jié)點(diǎn)都有一張鄰居節(jié)點(diǎn)信息表，其結(jié)構(gòu)如表1所示。

Table 1 Information structure of neighbor node表1 鄰居節(jié)點(diǎn)信息表結(jié)構(gòu)

當(dāng)節(jié)點(diǎn)收到信息包，就更新鄰居節(jié)點(diǎn)信息表。節(jié)點(diǎn)狀態(tài)通過節(jié)點(diǎn)剩余能量與臨界值α(臨界值αi取值為節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)中剩余能量值最大的一半)比較確定。如果剩余能量小于選定的臨界值α，就不是相關(guān)節(jié)點(diǎn)，否則是相關(guān)節(jié)點(diǎn)；當(dāng)過了一段時(shí)間后，剩余能量大于重新選定的臨界值α，節(jié)點(diǎn)就可以從非相關(guān)狀態(tài)轉(zhuǎn)換到相關(guān)狀態(tài)。接著計(jì)算發(fā)送信息包的鄰居節(jié)點(diǎn)路徑能量消耗，如果數(shù)據(jù)信息包從節(jié)點(diǎn)Nj發(fā)送到節(jié)點(diǎn)Ni，節(jié)點(diǎn)Ni計(jì)算能量消耗公式為：

(6)

(7)

(8)

Ri表示節(jié)點(diǎn)Ni的剩余能量，Et+Er表示節(jié)點(diǎn)Ni與節(jié)點(diǎn)Nj連通路徑發(fā)送和接收數(shù)據(jù)信息包消耗的能量。接著各鄰居節(jié)點(diǎn)又以同樣的方式向各自的鄰居節(jié)點(diǎn)廣播信息，將跳數(shù)值逐漸累加1，作為對(duì)根節(jié)點(diǎn)的跳數(shù)。最后到了沒有鄰居節(jié)點(diǎn)結(jié)束也就是到了無線傳感器網(wǎng)絡(luò)的另一相對(duì)邊界，這樣就把無線傳感器網(wǎng)絡(luò)相對(duì)于根節(jié)點(diǎn)分成了若干個(gè)跳數(shù)層，如圖1所示，具體算法如算法1所示。

Figure 1 Wireless sensor network hops distribution map圖1 無線傳感器網(wǎng)絡(luò)跳數(shù)分布圖

算法1HFEBEQ算法初始化

//確定每個(gè)節(jié)點(diǎn)與指定初始化節(jié)點(diǎn)的跳數(shù)

1. random select nodeAas initial node; /*選擇的任意節(jié)點(diǎn)作為起始節(jié)點(diǎn)*/

2. For 節(jié)點(diǎn)Ni接收到數(shù)據(jù)信息包 do

3.Ni.hops+1;//把接收到的跳數(shù)值加1

4. if 節(jié)點(diǎn)Nj在節(jié)點(diǎn)Ni和根節(jié)點(diǎn)之間 then

5. ifNj·Rj>αithen/*節(jié)點(diǎn)Nj剩余能量Rj大于臨界值αi*/

6.Nj.Status=1；/*節(jié)點(diǎn)Nj狀態(tài)標(biāo)記為相關(guān)節(jié)點(diǎn)*/

7. 計(jì)算節(jié)點(diǎn)Ni到節(jié)點(diǎn)Nj的能量消耗；

8. else

9.Nj.Status=0；/*節(jié)點(diǎn)Nj狀態(tài)標(biāo)記為非相關(guān)節(jié)點(diǎn)*/

10. end if

11. 增加節(jié)點(diǎn)Nj到節(jié)點(diǎn)Ni的鄰居節(jié)點(diǎn)信息表中；

12. else

13. 節(jié)點(diǎn)Ni丟棄這個(gè)數(shù)據(jù)信息包；

14. end if

15. end for

(2)事件查詢階段。

當(dāng)一個(gè)節(jié)點(diǎn)監(jiān)測到相應(yīng)的某一個(gè)事件時(shí)，根據(jù)設(shè)定的哈希函數(shù)映射得到相應(yīng)的跳數(shù)層，接著通過

多跳的形式發(fā)送數(shù)據(jù)信息包給相應(yīng)的跳數(shù)層的某個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)再把數(shù)據(jù)信息傳輸給同層的節(jié)點(diǎn)。監(jiān)測事件節(jié)點(diǎn)及中間節(jié)點(diǎn)通過節(jié)點(diǎn)狀態(tài)和最小路徑能量消耗在鄰居節(jié)點(diǎn)信息表中搜尋下一跳鄰居節(jié)點(diǎn)，因此選擇同一個(gè)節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)的概率減少了，也就是可能事件相同也不會(huì)始終使用一條路由路徑傳輸數(shù)據(jù)信息。這樣在節(jié)點(diǎn)上可以存儲(chǔ)更多的能量，達(dá)到了能量均衡的目的，從而也延長了網(wǎng)絡(luò)的生命周期。依次搜尋選擇下一跳鄰居節(jié)點(diǎn)，直到數(shù)據(jù)信息包傳輸?shù)较鄳?yīng)的跳數(shù)層的某個(gè)節(jié)點(diǎn)，具體算法如算法2所示。

算法2HFEBEQ算法事件信息的存儲(chǔ)

1.j=h(K);/*節(jié)點(diǎn)監(jiān)測到事件時(shí)，根據(jù)設(shè)定的哈希函數(shù)映射得到相應(yīng)的跳數(shù)層*/

2. ForNj.hops=jdo

3. 節(jié)點(diǎn)Nj向同跳數(shù)層的鄰居節(jié)點(diǎn)傳輸數(shù)據(jù)信息包；

4. For 節(jié)點(diǎn)Ni接收到的數(shù)據(jù)信息包 do

5. if 節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)信息表不為空 then

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

7. 選擇下一跳鄰居節(jié)點(diǎn)Nj；

8. end if

9. else

10. 重新選定臨界值αi；

11. 重新確定節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)狀態(tài)；

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

13. 選擇下一跳鄰居節(jié)點(diǎn)Nj；

14. end if

15. end if

16. 發(fā)送數(shù)據(jù)信息包給節(jié)點(diǎn)Nj；

17. end for

18. end for

當(dāng)有查詢發(fā)生時(shí)，查詢節(jié)點(diǎn)同樣根據(jù)設(shè)定的哈希函數(shù)映射出相應(yīng)的跳數(shù)層，再根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)找到相應(yīng)跳數(shù)層的某個(gè)節(jié)點(diǎn)。此時(shí)，查詢與事件之間完成連接，數(shù)據(jù)信息可以沿著查詢的原路徑傳輸給查詢節(jié)點(diǎn)。具體算法如算法3所示。

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

1.j=h(K) /*查詢節(jié)點(diǎn)根據(jù)設(shè)定的哈希函數(shù)映射得到相應(yīng)的跳數(shù)層*/

2. ForNj.hops=jdo

3. 節(jié)點(diǎn)Nj傳輸數(shù)據(jù)信息包給查詢節(jié)點(diǎn)；

4. For 節(jié)點(diǎn)Ni接收到的數(shù)據(jù)信息包 do

5. if 節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)信息表不為空 then

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

7. 選擇下一跳鄰居節(jié)點(diǎn)Nj；

8. end if

9. else

10. 重新選定臨界值αi；

11. 重新確定節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)狀態(tài)；

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

13. 選擇下一跳鄰居節(jié)點(diǎn)Nj；

14. end if

15. end if

16. 發(fā)送數(shù)據(jù)信息包給節(jié)點(diǎn)Nj；

17. end for

18. end for

假設(shè)A節(jié)點(diǎn)監(jiān)測了某個(gè)事件發(fā)生，通過設(shè)定的哈希函數(shù)映射出相應(yīng)的跳數(shù)層為7，根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)傳輸數(shù)據(jù)信息到相應(yīng)跳數(shù)層為7的某個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)再把數(shù)據(jù)信息傳輸給同層的節(jié)點(diǎn)；同樣假設(shè)B節(jié)點(diǎn)要查詢相應(yīng)的事件信息，通過設(shè)定的哈希函數(shù)映射出相應(yīng)的跳數(shù)層為7，根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)找到相應(yīng)跳數(shù)層為7的某個(gè)節(jié)點(diǎn)。此時(shí)，查詢與事件之間完成連接，數(shù)據(jù)信息可以沿著查詢的原路徑傳輸給查詢節(jié)點(diǎn)，也就意味著B節(jié)點(diǎn)知道了事件發(fā)生在A節(jié)點(diǎn)處。如圖2所示。

Figure 2 Schematic diagram of event query圖2 事件查詢階段示意圖

4 仿真實(shí)驗(yàn)及分析

借助OMNET++網(wǎng)絡(luò)模擬器[11]，對(duì)本文中的事件查詢算法與Flooding路由算法[4]和Rumor路由算法[7]進(jìn)行平均能量消耗、時(shí)間延遲和網(wǎng)絡(luò)生命周期三個(gè)性能測試比較，只考慮其數(shù)據(jù)傳送過程中的能耗和時(shí)間延遲。仿真環(huán)境使用的面積大小為1 000 m×1 000 m，節(jié)點(diǎn)個(gè)數(shù)從50到800逐漸增加且均勻分布在區(qū)域里，其它實(shí)驗(yàn)參數(shù)如表2所示。

Table 2 Experimental parameters表2 實(shí)驗(yàn)參數(shù)

網(wǎng)絡(luò)平均能量消耗等于N個(gè)節(jié)點(diǎn)能量消耗累加和的平均值，節(jié)點(diǎn)能量消耗等于初始能量值減去剩余能量值。圖3的仿真實(shí)驗(yàn)結(jié)果表明本文中的事件查詢算法比Flooding路由算法及Rumor路由算法的平均能量消耗要小很多。因?yàn)楸疚闹械氖录樵兯惴ㄔ谕負(fù)鋽U(kuò)散階段只僅僅使用了一次洪泛方式廣播，而在Flooding路由算法中只要有事件或查詢發(fā)生都會(huì)使用洪泛方式廣播；對(duì)于Rumor路由算法查詢需要n條查詢路徑，查詢路徑越多，查詢消耗的能量越多；本文中的事件查詢算法在選擇鄰居節(jié)點(diǎn)的時(shí)候根據(jù)節(jié)點(diǎn)狀態(tài)和路徑能量消耗函數(shù)進(jìn)行能量均衡選擇，因此選擇同一個(gè)節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)的概率減少了，在節(jié)點(diǎn)上可以存儲(chǔ)更多的能量，達(dá)到了能量平衡和公平使用節(jié)點(diǎn)的目的。

Figure 3 Comparison of average energy consumption圖3 平均能量消耗比較圖

時(shí)間延遲是指查詢到相應(yīng)事件信息的時(shí)間間隔。圖4的仿真實(shí)驗(yàn)結(jié)果表明，本文中的事件查詢算法比Flooding路由算法及Rumor路由算法的時(shí)間延遲要小很多。因?yàn)楸疚闹械氖录樵兯惴ㄔ诓樵兿嚓P(guān)事件信息時(shí)，目的非常明確且通過設(shè)定的哈希函數(shù)能夠快速定位；而Flooding算法不考慮用戶需求定期將大量數(shù)據(jù)傳給Sink節(jié)點(diǎn)，Sink節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的融合處理，再返回給用戶需要的事件信息，同時(shí)頻繁地使用洪泛方式廣播會(huì)造成網(wǎng)絡(luò)擁塞而延長了時(shí)間延遲；Rumor路由算法沒有辦法找到較短的路徑，而且會(huì)有回路問題，更甚至于在回路的狀況下，根本就沒有辦法找到適當(dāng)?shù)穆窂竭B接查詢與事件。

Figure 4 Comparison of time delay圖4 時(shí)間延遲比較圖

網(wǎng)絡(luò)生命周期是無線傳感器網(wǎng)絡(luò)最重要的性能參數(shù)之一。本文的網(wǎng)絡(luò)生命周期定義為網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)能量消亡的時(shí)間。圖5的仿真實(shí)驗(yàn)結(jié)果表明，本文中的事件查詢算法比Flooding路由算法及Rumor路由算法網(wǎng)絡(luò)生命周期要長。因?yàn)楸疚闹械氖录樵兯惴ɡ昧瞬煌陌l(fā)現(xiàn)路徑傳輸數(shù)據(jù)，使用了路徑能量消耗函數(shù)及節(jié)點(diǎn)的狀態(tài)，在高能量節(jié)點(diǎn)中分散了能量負(fù)載，在不同的節(jié)點(diǎn)間減小了能量差距，從而延長了網(wǎng)絡(luò)的生命周期，確保了能量均衡和避免了網(wǎng)絡(luò)過早的消亡；而Flooding路由算法頻繁地使用洪泛方式廣播，需要所有的節(jié)點(diǎn)消耗能量在尋找路徑上，導(dǎo)致整個(gè)網(wǎng)絡(luò)的生命周期變短；Rumor路由算法可以通過控制所發(fā)出代理程序數(shù)量的多少來減少找不到的情況發(fā)生，但過多的代理程序一樣會(huì)增加傳感器節(jié)點(diǎn)能量的消耗，即查詢路徑越多，查詢消耗的能量越多，最終導(dǎo)致整個(gè)網(wǎng)絡(luò)的生命周期變短。

Figure 5 Comparison of network life cycle圖5 網(wǎng)絡(luò)生命周期比較圖

5 結(jié)束語

在無線傳感器網(wǎng)絡(luò)中對(duì)于無固定位置的事件及查詢，在設(shè)計(jì)路由協(xié)議時(shí)最重要的性能是快速、高效且節(jié)省能量。傳感器能量消耗主要在數(shù)據(jù)傳輸和接收，因此路由設(shè)計(jì)對(duì)于節(jié)能方面應(yīng)該盡可能延長單個(gè)傳感器及整個(gè)網(wǎng)絡(luò)的生命周期，其主要目標(biāo)是優(yōu)化能量消耗。本文提出的基于哈希函數(shù)及能量均衡的事件查詢算法，目的非常明確且通過設(shè)定的哈希函數(shù)能夠快速定位，用最小的路徑能量消耗在鄰居節(jié)點(diǎn)信息表中查找所有相關(guān)的鄰居節(jié)點(diǎn)。仿真實(shí)驗(yàn)結(jié)果表明，本文算法能快速高效地進(jìn)行事件查詢，在傳感器節(jié)點(diǎn)間達(dá)到了最小化和平衡能量消耗，從而延長了網(wǎng)絡(luò)的生命周期。但是，該算法是在假設(shè)節(jié)點(diǎn)非移動(dòng)的理想情況下提出的，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)開始死亡或者節(jié)點(diǎn)大規(guī)模移動(dòng)時(shí)事件查詢就會(huì)遇到一定困難，這是今后要研究的重點(diǎn)問題。

[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/.

附中文參考文獻(xiàn):

[1] 任繪錦,戴曉華,王智.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的系統(tǒng)設(shè)計(jì)[J].電子測量與儀器學(xué)報(bào),2009,20(6):31-35.

[2] 李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報(bào)，2003,14(10):1717-1727.

[3] 郭龍江,李建中,李貴林.無線傳感器網(wǎng)絡(luò)環(huán)境下時(shí)空查詢處理方法[J]. 軟件學(xué)報(bào), 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),男，湖南益陽人，教授，研究方向?yàn)樾畔踩c計(jì)算機(jī)教育。E-mail:gdl2865605@163.com

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

李盛欣(1981),男，湖南郴州人，碩士，講師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)和網(wǎng)格計(jì)算。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

湖南省教育廳科技資助項(xiàng)目(12C0884)；湖南省教育科學(xué)“十二五”規(guī)劃課題資助項(xiàng)目(XJK012CGD034)；郴州市科技計(jì)劃資助項(xiàng)目(2012cj120)；湖南省普通高?！笆濉本W(wǎng)絡(luò)工程專業(yè)綜合改革試點(diǎn)資助項(xiàng)目(湘教通[2012]112號(hào));湘南學(xué)院計(jì)算機(jī)應(yīng)用技術(shù)重點(diǎn)學(xué)科資助項(xiàng)目

TP393

：A

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

章才能(1978),男，湖南常寧人，碩士，講師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)安全和云計(jì)算。E-mail:51809699@qq.com

通信地址：423000 湖南省郴州市湘南學(xué)院計(jì)算機(jī)系

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