能量高效的傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢路由

摘要:提出一種能量高效的傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢路由EEDQ(energy－efficient data query)，EEDQ以sink節(jié)點(diǎn)為根節(jié)點(diǎn)，構(gòu)造最小路由生成樹， 由sink節(jié)點(diǎn)發(fā)出查詢?nèi)蝿?wù)，查詢結(jié)果由葉子節(jié)點(diǎn)向sink節(jié)點(diǎn)傳輸，傳輸過程中進(jìn)行數(shù)據(jù)匯聚。實(shí)驗(yàn)表明，EEDQ相比direct transmission，大大提高了傳感器網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞:數(shù)據(jù)查詢; 路由協(xié)議; 數(shù)據(jù)匯聚; 定向擴(kuò)散

中圖分類號(hào):TP393文獻(xiàn)標(biāo)志碼:A

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

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

1相關(guān)工作

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

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

謠傳路由的基本思想是:事件區(qū)域中的傳感器節(jié)點(diǎn)產(chǎn)生代理(agent)消息，代理消息沿隨機(jī)路徑向外擴(kuò)散傳播，同時(shí)匯聚點(diǎn)發(fā)送的查詢消息也沿隨機(jī)路徑在網(wǎng)絡(luò)中傳播;當(dāng)代理消息和查詢消息的傳輸路徑交叉在一起時(shí)，就會(huì)形成一條匯聚節(jié)點(diǎn)到事件區(qū)域的完整路徑。圖2所示為謠傳路由原理圖。

在sink節(jié)點(diǎn)多#65380;查詢請(qǐng)求數(shù)目很大#65380;網(wǎng)絡(luò)事件很少的情況下，rumor協(xié)議較為有效。但如果事件非常多，維護(hù)事件表和收發(fā)agent帶來的開銷會(huì)很大。

2系統(tǒng)模型

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

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

2)無線通信模型

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

3)無線能量模型

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

本文假設(shè)無線信道是對(duì)稱的，即從節(jié)點(diǎn)u傳送消息到v消耗的能量等于從v傳送同樣的消息到u所消耗的能量。

3高效節(jié)能的查詢路由

本文提出一種高效節(jié)能的查詢路由協(xié)議。該協(xié)議的主要思想是以sink為樹根，傳感區(qū)域的其他所有節(jié)點(diǎn)為sink節(jié)點(diǎn)的子孫創(chuàng)建一棵最小代價(jià)樹。查詢信息由sink發(fā)出，沿樹的層次洪泛到各節(jié)點(diǎn)，查詢結(jié)果由樹中的葉子節(jié)點(diǎn)沿反方向傳送到sink節(jié)點(diǎn)。其間，每個(gè)節(jié)點(diǎn)在各自的父節(jié)點(diǎn)處進(jìn)行數(shù)據(jù)聚集。

3.1最小代價(jià)生成樹

本文所采用的網(wǎng)絡(luò)模型是N個(gè)節(jié)點(diǎn)隨機(jī)均勻地分布在正方形區(qū)域A中。這樣，傳感器網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)和能夠?qū)崿F(xiàn)直接通信的節(jié)點(diǎn)對(duì)就構(gòu)成了一個(gè)連通圖。因?yàn)橛旨僭O(shè)了無線通信模型是對(duì)稱的，所以該連通圖是無向圖。設(shè)此無向連通圖G=。其中:V為傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的集合;{E}為連接兩個(gè)節(jié)點(diǎn)的邊的集合，給每條邊賦上權(quán)值;U是頂點(diǎn)集合V的一個(gè)非空子集。若(u，v)是一條具有最小權(quán)值的邊。其中:u∈U，v∈V-U，則存在一棵包含邊(u，v)的最小生成樹。用Prim算法可以構(gòu)造最小生成樹。假設(shè)G=(V，{E})是連通網(wǎng)，TE是G上最小生成樹中邊的集合。算法從U={u0}(這里u0為sink節(jié)點(diǎn))，TE={}開始，重復(fù)執(zhí)行下述操作:在所有u∈U，v∈V-U的邊(u，v)∈E中找一條代價(jià)最小的邊(u0，v0)并入集合TE;同時(shí)v0并入U(xiǎn)，直到U=V為止。此時(shí)TE中必有n-1條邊，則T=(V，{TE})為G的最小生成樹。

3.2構(gòu)造查詢路由

Sink節(jié)點(diǎn)發(fā)出查詢?nèi)蝿?wù)，采用洪泛的方式傳播查詢消息M到整個(gè)區(qū)域的所有傳感器節(jié)點(diǎn)。任務(wù)M可以用如下查詢語(yǔ)句給出:

Selectroom_no，average(light)

from sensors

group by room_no

having average(light)>1

epoch duration 5 min

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

4模擬與分析

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

5結(jié)束語(yǔ)

本文提出了一種能量高效的傳感器網(wǎng)絡(luò)數(shù)據(jù)查詢路由EEDQ，由查詢驅(qū)動(dòng)建立以sink節(jié)點(diǎn)為根節(jié)點(diǎn)的最小路由生成樹，任務(wù)消息由sink通過flooding給傳感區(qū)域的每個(gè)節(jié)點(diǎn)并構(gòu)造最小生成樹，查詢結(jié)果由葉子節(jié)點(diǎn)向sink節(jié)點(diǎn)傳輸，傳輸過程中每個(gè)節(jié)點(diǎn)在父節(jié)點(diǎn)處進(jìn)行匯聚，sink節(jié)點(diǎn)對(duì)每一輪查詢結(jié)果進(jìn)行匯聚。每個(gè)節(jié)點(diǎn)只與它的父節(jié)點(diǎn)通信，大大地節(jié)約了傳感器節(jié)點(diǎn)的能量，降低了能量消耗，延長(zhǎng)了整個(gè)傳感器網(wǎng)絡(luò)的生命周期。

參考文獻(xiàn):

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

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”