高效節能的無線傳感器網絡數據收集協議

摘要：現有的數據收集協議的性能不是很好，為此提出了一種基于數據收集樹的數據收集協議。它通過減少數據收集樹中的節點深度和中間節點數來減少制約系統生命期的節點傳輸數據給基站的能量消耗和節點空閑偵聽的能量消耗。仿真實驗表明，該協議能將系統生命期延長36%左右。

關鍵詞：無線傳感器網絡； 數據收集協議； 系統生命期； 數據收集樹

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

文章編號：1001－3695(2008)04－1201－03

0引言

由眾多微型傳感器節點以Ad hoc方式組成的無線傳感器網絡正在逐漸投入應用[1~3]。傳感器節點主要由傳感器、處理器和通信部件組成，具有感知能力、計算能力和無線通信能力。傳感器節點的無線通信距離很短，在此距離內的兩傳感器節點之間可以直接相互通信。在無線傳感器網絡中，傳感器節點既可做數據產生節點，又可兼做路由節點，這樣相距較遠的兩傳感器節點之間可以通過其他傳感器節點作為路由節點來實現通信。

利用無線傳感器網絡來進行數據收集是無線傳感器網絡的一個重要用途，可以應用在國防軍事、國家安全、環境監測、交通管理、醫療衛生、制造業、反恐抗災等重要領域。例如可以在動物棲息地布置無線傳感器網絡，利用傳感器來感知動物的活動狀況，從中獲取有用的信息，發送給外界處理分析。由于監控區域可能比較遠，為了能夠獲取感應數據，通常還要在監控區域內配置一個基站?；緩臒o線傳感器網絡中收集收據，再轉發給外界用戶。

傳感器節點由自帶的電池供電，其提供的能量十分有限，而大部分數據收集應用均要求較長的周期，因此節省能量以延長生命期是無線傳感器網絡的一個重要設計目標。傳感器節點的能量主要消耗在通信部件上[4]，即發送數據、接收數據和空閑偵聽。其中，空閑偵聽所消耗的能量并不能忽略不計[5，6]，所以既要減少發送接收數據消耗的能量，又要減少空閑偵聽消耗的能量。路由節點需要接收其他節點的數據，所以必須空閑偵聽，而非路由節點在無數據發送時就可關閉自身的通信設備，以節省能量消耗。綜上所述，在數據收集的過程中，既要減少節點傳輸數據給基站的路徑（以下簡稱節點的傳輸路徑）長度，以節省發送接收數據的能量消耗，又要減少總的路由節點數，以節省空閑偵聽的能量消耗。

文獻[7]中提出了LEACH協議。節點被劃分為簇，每個簇選取一個簇頭節點，接收簇中其他節點的數據并直接傳送給基站。然而離基站較遠的簇頭節點向基站傳送數據時，通信距離較遠，將會消耗大量的能量，因此LEACH只適用于小型的傳感器網絡。文獻[8]中提出了GAF協議，監控區域被劃分為大小相等的正方形網格，每個網格選取一個頭節點，接收網格中其他節點的數據并傳送給基站。當網格的大小為無線通信距離的1/5倍，頭節點就可直接與其相鄰的四個網格中的頭節點通信。然而在GAF中，節點的傳輸路徑在最壞情況下可達到直線距離的2倍；此外每跳的平均距離僅為無線通信距離的49%左右，這樣導致節點的傳輸路徑較長，能量消耗較大。

本文提出了一種基于數據收集樹的數據收集協議。數據收集樹是一棵根在基站的生成樹，節點通過數據收集樹中的路徑將數據傳送給基站。這樣數據收集樹的中間節點就是路由節點，而節點的深度就是節點的傳輸路徑長度。通過減少數據收集樹的中間節點數和節點深度，以減少數據收集的能量消耗。

1數據收集協議

1．1數據收集樹的構造

本文采用局部式方法在無線傳感器網絡中動態維持一個數據收集樹。局部式方法是指每個節點僅需知道鄰居的信息，而無須收集全局節點信息。無線傳感器網絡中節點較多，收集全局的節點信息需要消耗大量能量，采用局部式方法可有效減少構造數據收集樹的能量消耗。動態維持是指不需要所有節點去同步構造一個數據收集樹，每個節點可異步工作。這樣當數據收集樹失效時，無須所有節點均參與重新構造數據收集樹，只需失效節點處重新構造即可。

每個傳感器節點動態選取其父節點，并且保證連通無圈，即可在無線傳感器網絡中維持一個數據收集樹。為了使得節點在數據收集樹的深度最小，節點應選取深度最小的鄰居作為父節點。因此每個節點需記錄其在數據收集樹中的深度d，如果節點尚不在數據收集樹中，則d=∞。初始時只有根節點即基站的深度d=0，而其他點的深度d=∞。在數據收集樹中，除根節點以外的每個節點均有一個父節點，因此所有中間節點（包括根節點）的子節點數和為n（n為傳感器節點總數）。中間節點的平均子節點數越多，中間節點就越少。為了減少數據收集樹的中間節點數，節點應優先選取子節點數多的鄰居作為父節點，記節點的子節點數為c。

在無線傳感器網絡運行的過程中，每個節點周期性地獲取鄰居信息，信息中包含節點的深度d和子節點數c。記權值w=(1/d，c)，節點每次選取權值w最大的鄰居作為其父節點，即優先選取深度最小的鄰居作為父節點。深度相同時，優先選取子節點最多的鄰居作為父節點。此外如果所有鄰居的深度d均等于∞，則此節點不選取任何鄰居作為父節點。無線傳感器網絡中的每個傳感器節點s可做如下工作：

a) 節點s向鄰居廣播adv消息。

b) 某節點如收到adv消息，則發送inf消息給節點s。

c) 節點s接收inf消息，從而得知所有鄰居的深度d和子節點數c。

d) 節點s從所有鄰居中選取w=(1/d，c)最大的節點q。如果節點q的深度d不等于∞，則節點s選取q作為其父節點，并將其深度設置為d+1；否則不選取任何節點作為其父節點（可記做其父節點為空節點）。

e) 設節點s的舊父節點為fatherold，新父節點為fathernew。如果fatherold=fathernew，則直接轉至j）。

f)如果節點fatherold不為空節點，則節點s向fatherold發送reselect消息；否則轉至步驟h）。

g)節點fatherold接收reselect消息，將其子節點數c減1。

h)如果節點fathernew不為空節點，則節點s向fathernew發送father消息；否則轉至步驟j）。

i)節點fathernew接收father消息，將其子節點數c加1。

j)節點s等待一段時間，再轉至a）。

1．2理論分析

寬度優先搜索生成樹是指樹中任意節點的深度等于此節點和根節點的距離，即在寬度優先搜索生成樹中，節點到根的路徑是最短的。

定理1數據收集樹的構造完成后，得到的數據收集樹是一棵根在基站的寬度優先搜索生成樹。

證明通過歸納法來證明數據收集樹中任意節點的深度等于此節點到根節點的距離。

與根節點的距離為0的節點是基站，初始時就在數據收集樹中，在數據收集樹中的深度為0，滿足要求。

假設與根節點的距離為m的節點在數據收集樹中的深度為m?，F在考慮與根節點的距離為m+1的任一節點在數據收集樹中的深度。假設某一節點s與根節點的距離為m+1，則節點s必有一鄰居，此鄰居與根節點的距離為m。根據歸納條件，此鄰居在數據收集樹中的深度為m。而節點s的鄰居在數據收集樹中的深度最小為m，且節點s優先選取深度最小的鄰居作為父節點，所以節點s在數據收集樹中的深度為m+1。得證。

根據定理1，在本文提出的數據收集協議中，節點的傳輸路徑長度是最短的，節點傳輸數據給基站的能量消耗是最小的，同時延遲最小。

2實驗結果

為了衡量本文提出的基于數據收集樹（data collection tree based，DCTB）的數據收集協議的性能，筆者采用NS－2.28[9]作為實驗平臺，與文獻[8]中提出的GAF協議進行對比分析。選取的參數如下：MAC層的協議為802.11 DCF；帶寬為128 kbps；發送、接收和空閑能量消耗分別為0.660、0.395和0.003 5 W；傳感器節點的無線通信距離為250 m；每個數據包的大小為64 Byte；傳感器節點的初始能量為10 000 J（大約一節5號1 800 mAh電池的能量）。

在實驗中，將1 000個傳感器節點均勻布置在2 000 m×2 000 m的平面區域上，基站放置在此平面區域的中心。監控區域中的事件滿足泊松分布，以平均1個事件/s的速度隨機發生在監控區域內某一點，傳感器節點對事件的感應數據的平均大小為2 000 Byte。對每個實驗模擬50次，再對實驗結果求平均，以使得實驗結果比較準確。

先比較DCTB和GAF協議的路由節點數。仿真實驗中，DCTB協議的平均路由節點數為149.6，而GAF協議的平均路由節點數為320。DCTB協議的平均路由節點數僅為GAF協議的47%左右。

再比較DCTB和GAF協議的節點傳輸路徑長度。圖1列出了仿真實驗中DCTB和GAF協議的不同傳輸路徑長度的節點數。在GAF協議中，大部分節點的傳輸路徑長度在7以上；而在DCTB協議中，大部分節點的傳輸路徑長度在4左右。GAF協議的平均傳輸路徑長度為9.8，DCTB協議的平均傳輸路徑長度為3.7，僅為GAF協議的38%左右。由于DCTB協議中的數據收集樹是一棵根在基站的寬度優先搜索生成樹，所有節點的傳輸路徑長度均是最短的。

系統生命期是最主要的性能指標。筆者選擇從開始到事件監控成功率低于80%的時間作為系統生命期。一個事件被成功監控是指基站能接收到這個事件的感應數據。事件監控成功率是指最近一段時間內，事件的成功監控次數與事件的總次數之比。仿真實驗中，DCTB協議的系統生命期為25.2 d，而GAF協議的系統生命期為18.5 d，DCTB協議將系統生命期延長了36%左右。

3結束語

本文提出了一種基于數據收集樹的數據收集協議，節點通過數據收集樹中的路徑將數據傳輸給基站。該協議是一個局部式協議，每個節點只需知道鄰居節點的深度和子節點數。節點動態選擇深度最小且子節點數多的鄰居作為其父節點，因此得到的數據收集樹是一棵根在基站的寬度優先搜索生成樹，節點傳輸數據給基站的路徑長度是最短的，同時樹中的中間節點比較少，即路由節點比較少。仿真實驗表明，此協議的平均路由節點數僅為GAF協議的47%左右，平均傳輸路徑長度僅為GAF協議的38%左右，可將系統生命期延長36%左右。

參考文獻：

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

［2]崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展， 2005， 42(1): 163－174.

［3]任豐源，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7): 1282－1291.

［4]ESTRIN D， GOVINDAN R， HEIDEMANN J， et al. Next century challenges: scalable coordination in sensor networks[C]//Proc ofACM MobiCom’99. Seattle：[s.n.]， 1999: 263-270.

［5]KASTEN O. Energy consumption [EB/OL].（2001）. http:// www.inf.ethz.ch/ ~kasten/research/bathtub/energy_consumption.html.

［6]STEMM M， KATZ R H. Measuring and reducing energy consumption of network interfaces in hand－held devices [J]. IEICE Trans on Communications，1997， E80－B (8): 1125-1131.

［7]HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy－ efficient communication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Annual Hawaii International Conference on System Sciences. 2000: 3005-3014.

［8]XU Y， HEIDEMANN J， ESTRIN D. Geography－informed energy conservation for Ad hoc routing[C]//Proc of ACM/IEEE Internatio－nal Conference on Mobile Computing and Networking.Rome:[s.n.]， 2001: 70-84.

［9］Network simulator [CP/OL]. http://www.isi.edu/nsnam/ns.

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