能量高效的傳感器網絡數據查詢路由

摘要:提出一種能量高效的傳感器網絡數據查詢路由EEDQ(energy－efficient data query)，EEDQ以sink節點為根節點，構造最小路由生成樹， 由sink節點發出查詢任務，查詢結果由葉子節點向sink節點傳輸，傳輸過程中進行數據匯聚。實驗表明，EEDQ相比direct transmission，大大提高了傳感器網絡的生命周期。

關鍵詞:數據查詢; 路由協議; 數據匯聚; 定向擴散

中圖分類號:TP393文獻標志碼:A

文章編號:1001－3695(2008)02－0562－03

傳感器技術#65380;微機電系統#65380;現代網絡和無線通信技術的進步，推動了具有現代意義的無線傳感器網絡的產生和發展。無線傳感器網絡由具有感知#65380;計算存儲和通信能力的微型傳感器組成，能實現實時監測#65380;感知和采集網絡分布區域內的各種監測對象信息，并對這些信息進行處理，傳送給需要這些信息的用戶[1，2]。傳感器網絡節點的資源十分有限，主要體現在電池能量#65380;處理能力#65380;存儲容量以及通信帶寬等幾個方面，所以傳感器網絡中的數據查詢處理不同于傳統數據庫，傳感器網絡中的查詢路由協議應該能夠有效地利用節點有限的能量延長網絡的生命周期[2] 。目前已有大量的研究工作從不同角度來力求延長傳感器網絡的生命[3~5]。本文則從傳感器網絡查詢路由協議的角度出發，提出一種能量高效的傳感器網絡數據查詢路由。

1相關工作

定向擴散是一種典型的基于查詢的路由協議[6]，該協議用屬性/值對命名數據。匯聚節點(sink)通過興趣消息發出查詢任務，采用洪泛方式傳播興趣消息到整個區域或部分區域內的所有傳感器。興趣消息用來表示查詢的任務，表達網絡用戶對監測區域內感興趣的信息，如監測區域內的溫度#65380;濕度和光照等環境信息。在興趣消息的傳播過程中，協議逐跳地在每個傳感器節點上建立反向的從數據源到匯聚節點的數據傳輸梯度(gradient)，傳感器節點將采集到的數據沿著梯度方向傳送到匯聚節點。使用查詢驅動機制按需建立路由，避免了保存全網信息，但是定向擴散路由在路由建立時需要一個興趣擴散的洪泛傳播，能量和時間開銷都比較大。尤其是當底層MAC協議采用休眠機制時可能造成興趣建立的不一致。圖1表示了DD協議的路由建立過程。

有些傳感器網絡的應用中，數據傳輸量較少或者已知事件區域，如果采用定向擴散路由，需要經過查詢消息的洪泛傳播和路由增強機制才能確定一條優化的數據傳輸路徑。因此在這類應用中，定向擴散路由并不是高效的路由機制。Boulis等人提出了謠傳路由(rumor routing)[7]，適用于數據傳輸量較小的傳感器網絡。

謠傳路由的基本思想是:事件區域中的傳感器節點產生代理(agent)消息，代理消息沿隨機路徑向外擴散傳播，同時匯聚點發送的查詢消息也沿隨機路徑在網絡中傳播;當代理消息和查詢消息的傳輸路徑交叉在一起時，就會形成一條匯聚節點到事件區域的完整路徑。圖2所示為謠傳路由原理圖。

在sink節點多#65380;查詢請求數目很大#65380;網絡事件很少的情況下，rumor協議較為有效。但如果事件非常多，維護事件表和收發agent帶來的開銷會很大。

2系統模型

1)網絡模型

本文采用文獻[8]中的網絡模型:N個傳感器節點隨機均勻分布在一個正方形區域A內， 傳感器節點部署后不再移動;惟一的基站部署在區域A以外的一個固定位置，并且部署后網絡不需要人為維護; 所有節點具有相似的能力(處理/通信)，并且地位平等;節點沒有裝備GPS，也不能通過測量的方法知道其具體位置;線發射功率可控，即節點可以根據距離來調整發射功率的大小。

2)無線通信模型

在無線傳輸中，發射功率的衰減隨著傳輸距離的增大而呈指數衰減。 文獻[9]中提出了兩種信道模型:自由空間(free space) 和多路徑衰減(multipath fading)。當發送和接收節點之間的距離d小于某個值d0時，采用自由空間模型，發射功率呈d2衰減;否則采用多路徑衰減模型，發射功率呈d4衰減。

3)無線能量模型

本文采用與文獻[10]相同的無線能量模型。式(1)為發射k bit數據耗損的能量，由發射電路耗損和功率放大耗損兩部分構成。功率放大耗損則根據發送者和接收者之間的距離分別采用自由空間模型和多路徑衰減模型。Eelec為發射電路的耗損能量;εfs #65380;εamp分別為兩種信道模型下功率放大所需能量。式(2)為接收k bit數據的能量耗損，僅由電路耗損引起。

本文假設無線信道是對稱的，即從節點u傳送消息到v消耗的能量等于從v傳送同樣的消息到u所消耗的能量。

3高效節能的查詢路由

本文提出一種高效節能的查詢路由協議。該協議的主要思想是以sink為樹根，傳感區域的其他所有節點為sink節點的子孫創建一棵最小代價樹。查詢信息由sink發出，沿樹的層次洪泛到各節點，查詢結果由樹中的葉子節點沿反方向傳送到sink節點。其間，每個節點在各自的父節點處進行數據聚集。

3.1最小代價生成樹

本文所采用的網絡模型是N個節點隨機均勻地分布在正方形區域A中。這樣，傳感器網絡內的所有節點和能夠實現直接通信的節點對就構成了一個連通圖。因為又假設了無線通信模型是對稱的，所以該連通圖是無向圖。設此無向連通圖G=。其中:V為傳感器網絡中節點的集合;{E}為連接兩個節點的邊的集合，給每條邊賦上權值;U是頂點集合V的一個非空子集。若(u，v)是一條具有最小權值的邊。其中:u∈U，v∈V-U，則存在一棵包含邊(u，v)的最小生成樹。用Prim算法可以構造最小生成樹。假設G=(V，{E})是連通網，TE是G上最小生成樹中邊的集合。算法從U={u0}(這里u0為sink節點)，TE={}開始，重復執行下述操作:在所有u∈U，v∈V-U的邊(u，v)∈E中找一條代價最小的邊(u0，v0)并入集合TE;同時v0并入U，直到U=V為止。此時TE中必有n-1條邊，則T=(V，{TE})為G的最小生成樹。

3.2構造查詢路由

Sink節點發出查詢任務，采用洪泛的方式傳播查詢消息M到整個區域的所有傳感器節點。任務M可以用如下查詢語句給出:

Selectroom_no，average(light)

from sensors

group by room_no

having average(light)>1

epoch duration 5 min

傳感器網絡中的節點收到消息M后，在消息M中加上sink節點到該節點的路由信息，然后繼續廣播，即用洪泛的方式直到所有節點得到其通向sink節點的路由信息。如果在節點收到的路由消息中，路由跳數大于該節點收到的其他路由消息中的路由跳數，則丟棄該廣播消息;當廣播過程結束后，每個節點保留了所有sink到本節點的最短路徑消息，然后從中選擇最近的上游節點作為父親(根據權值)，并向其發送子孫消息;最后將生成以sink節點為根節點的最小生成樹。圖3為查詢路由示意圖。葉子節點將它們的數據傳送到父節點;父節點首先利用聚集函數f聚集自己與子節點的數據;然后沿著路由樹向上發送部分聚集結果以及需要更新聚集的額外數據，sink 節點對收集到的所有信息進行匯聚。

4模擬與分析

傳感器網絡模型的主要參數如下:100 個節點平均分布在100 m ×100 m 的地域范圍A內，sink節點在傳感器區域A之外。為了測試EEDQ的性能，將其與direct transmission 進行比較，用C++完成模擬。圖4為初始能量相同時不同協議的網絡生命周期。從圖中可以看到，EEDQ比direct transmission將傳感器網絡的生命周期提高了約11倍(以最后一個節點死亡為標準)。圖5~7分別表示傳感器網絡中初始能量為0.25#65380;0.5#65380;1 J時第一個節點死亡(FND)#65380;一半節點死亡(HND)#65380;最后一個節點死亡(LND)的情況。從圖5~7中可以看出，EEDQ比direct transmission分別將傳感器網絡的FND#65380;HND#65380;LND提高了約3#65380;20和11倍。

5結束語

本文提出了一種能量高效的傳感器網絡數據查詢路由EEDQ，由查詢驅動建立以sink節點為根節點的最小路由生成樹，任務消息由sink通過flooding給傳感區域的每個節點并構造最小生成樹，查詢結果由葉子節點向sink節點傳輸，傳輸過程中每個節點在父節點處進行匯聚，sink節點對每一輪查詢結果進行匯聚。每個節點只與它的父節點通信，大大地節約了傳感器節點的能量，降低了能量消耗，延長了整個傳感器網絡的生命周期。

參考文獻:

[1]AKYILDIZI F， SU W， SANKARASUBRAMANIAM Y，et al. Wireless sensor networks:a survey[J].Computer Networks， 2002，38(4):393－422.

[2]ESTRIN D， GOVINDANR， HEIDEMANN J， et al. Next century challenges:scalable coordination in sensor networks[C]//KODESH H.Proc of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York:ACM Press，1999:263－270.

[3]YE Wei，HEIDENMANN J， ESTRIN D.An energry efficient MAC protocol for wireless sensor networks[C]//Proc of the IEEE INFOCOM. San Francisco:IEEE Computer Society，2002.

[4]KULIK J， HEINZELMAN W R， BALAKRISHNAN H. Negotiation－based protocols for dissemination information in wireless sensor networks[J].ACM Wireless Networks，2002，8(2):169－185.

[5]HEINZELMAN W R，KULIK J， BALAKRISHNAN H. Adaptive protocols for information dissemination in wireless sensor networks[C]//Proc of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York: ACM Press:174－185.

[6]INTANAGONWIWAT C， GOVINDAN R， ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual ACM/IEEE Interational Confe－rence on Mobile Computing and Networking. New York: ACM Press， 2000:56－67.

[7]BRAGINSKY D， ESTRIN D. Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications.Atlanta:ACM Press， 2002:22－31.

[8]YONIS O， FAHMY S.HEED:a hybrid，energy efficient distributed clustering approachfor Ad hoc sensor networks[J]. IEEE Trans on Mobile Computing，2004，3(4):366 －379.

[9]RAPPAPORT T. Wireless communications: principles and practice [M]. New Jersey:Prentice Hall Inc，1996.

[10]HEINZELMAN W R， CHANDRAKASAN A，BALA KRISHNAN H. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communications， 2002，1(4):660 －670.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”