一種新的基于漫游代理的定向路由樹算法

摘要：分析了以數據為中心的無線傳感器網絡中的定向擴散路由算法，提出了一種基于隨機漫游的具有路由修復agent的定向路由樹算法。該算法用泛洪策略構造一棵以匯聚節點為根的定向匯聚樹，隨后agent以等概率的方式在各個相鄰傳感器節點之間移動，當agent發現某兩節點之間不再相鄰時，即采取以該節點為中心的、逐步增加搜索范圍的定向匯聚樹的層次修復工作。研究表明，該算法具有良好的路由修復功能，同時也能節省能量并延長無線傳感器網絡的壽命。

關鍵詞：隨機漫游； 有向傳輸路由樹； 路由修復； 無線傳感器網絡

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

文章編號：1001-3695(2007)11-0283-03

大量傳感器節點隨機部署在監測區域內部或附近，通過自組織方式構成網絡。傳感器節點將監測到的數據通過其他傳感器節點逐跳地傳播到匯聚節點，在傳輸過程中監測數據可能會被多個節點進行融合處理，最后通過互聯網或衛星到達管理節點[1，2]。用戶通過管理節點對傳感器網絡進行配置和管理，發布監測任務以及收集監測數據。匯聚節點既可以是一個具有增強功能的傳感器節點、有足夠的能量供給和更多的內存與計算資源，也可以是沒有監測功能僅帶有無線通信接口的特殊網關設備。

傳感器節點是一個微型的嵌入式系統，它的處理能力、存儲能力和通信能力相對較弱，通過攜帶能量有限的電池供電。從網絡功能上看，每個傳感器節點兼顧了傳統網絡節點的中斷和路由器雙重功能，除了進行本地信息收集和數據處理外，還要對其他節點轉發而來的數據進行存儲、管理和融合等處理，同時與其他節點協作完成一些特定任務[3，4]。

互聯網是一個以IP地址為中心的網絡，網絡設備用網絡中惟一的IP地址進行標志，資源定位和信息傳輸依賴于終端、路由器、服務器等網絡設備的IP地址。如果想訪問互聯網中的資源，必須要先知道存放資源的服務器IP地址。

傳感器網絡是一種任務型的、以數據為中心的網絡，網絡節點采用節點編號標志，節點編號是否需要全網惟一取決于網絡通信協議的設計[5]。由于傳感器節點隨機部署，構成的傳感器網絡與節點編號之間的關系是完全動態的，表現為節點編號與節點位置沒有必然的聯系。用戶使用傳感器網絡查詢事件時，直接將所關心的事件通告給網絡，而不是通告給某個確定編號的節點，網絡在獲得指定事件的信息后匯報給用戶。

定向擴散模型[5~7]是由Estrin等人專門為傳感器網絡設計的路由策略，與已有的路由算法有著截然不同的實現機制。節點用一組屬性值來命名它所生成的數據，sink節點發出的查詢業務也用屬性的組合表示，逐級擴散，最終遍歷全網，找到所有匹配的原始數據。本文提出了一種新的基于agent漫游的無線傳感器網絡中的定向路由樹算法，給出了該算法的詳細描述，同時也分析了算法的性能，并對定向路由樹算法和定向擴散算法進行了性能比較。

1基于漫游代理的定向路由樹算法

1．1模型

假定要研究的無線傳感器網絡中的每個傳感器節點具有惟一的標志，均勻地散布在指定的區域中，每個節點的通信覆蓋范圍也完全相同。無線傳感器網絡是一個單匯聚節點網絡，網絡中的每個節點不僅能感知周邊的敏感信息，同時也具有信息融合的能力。各個節點負責收集熱點地區的敏感信息，然后通過中間節點的轉發匯聚到sink節點，或是sink節點定期向網絡中發出查詢命令來收集某些感興趣的信息。

定義1無線傳感器網絡中，一棵以匯聚節點為根的有向生成樹，叫做sink樹。在一棵給定的sink樹中，如果在從sink到v的路中包含u，稱節點u是節點v的上游節點;否則稱節點u是節點v的下游節點。顯然，上游節點距sink節點的跳數距離更近。

2算法分析

無線傳感器網絡采用泛洪方式建立一棵sink樹，隨后sink節點產生一個隨機漫游的agent。當某節點收到agent時，立即發出探詢分組，檢測自己的鄰居節點是否仍然存活。如果所有鄰居均有應答，則將agent隨機地傳遞給某個鄰居；否則，啟動sink樹的修復進程，修復之后再將agent隨機地傳遞給某個鄰居節點。

在意外情況下，當擁有agent的節點突然失效時，agent也會隨之丟失。為了解決這一問題，可以在每個傳感器節點上增設一個記錄最近一次感知agent存活時間的寄存器（AVR）。當agent遷移發生或節點的計數器達到某個預設的門限值時，執行更新上游節點AVR的操作。因此，sink節點能記錄agent的存活狀態。

當某個節點u長時間沒有agent光顧時，就會向其上游節點發出查詢分組，詢問agent最新更新時間。當上游節點收到查詢分組時，計算兩個節點的AVR之差，如果超過設定的門限值，則繼續向上游節點轉發查詢分組，直到到達sink節點或某個上游節點w的AVR值足夠新為止。

如果w的AVR值很新，則更新從w到u的路徑上各個節點的AVR；否則，如果sink節點的AVR過時，那么sink節點就授權最先發現agent丟失的節點u完成agent的再生操作。

通過上述操作，無線傳感器網絡能夠在一定的時間范圍內檢測出agent丟失問題，并能很快地再生agent。假設無線傳感器網絡中有n個節點，構成的sink樹是一棵二叉樹，那么某個節點質疑agent存活的分組平均需要掃描0．5log2 n個節點，再生agent分組也需要傳遞0．5log2 n個節點，因此總的系統開銷為log2 n。

3仿真計算

為了測試算法的有效性，編程實現了基于agent的sink樹算法。假定傳感器節點均勻地分布在50×50 m2的區域內，分別考慮不同的節點密度和邊失效概率下修復sink樹中分組傳遞的數目，如圖2、3所示。

從上面的測試結果中不難得出如下結論，在邊失效幾率一定的條件下，隨著節點密度的增加，路由修復的代價在緩慢增加。在節點密度一定的情況下，隨著節點間的連接失效概率的增加，路由修復的代價呈下降趨勢，但它們的代價都不會高于重構定向路由樹的代價。

4結束語

在Estrin等人提出的定向路由樹中，一條邊或一個節點失效，就需要重構整棵路由樹；而在本文所提出的基于漫游agent的sink樹算法中，僅僅進行局部修復操作即能完成定向路由樹的修復工作。因此基于漫游agent的sink樹算法能節省節點能量，從而延長節點的使用壽命，具有很好的應用前景。

參考文獻：

[1]AKYILDIZ I F， SU W，SANKARASUBRAMANLAM Y，et al. A survey on sensor networks[J]. IEEE Communiations Magazine， 2002，40(8):102－114.

[2]BENNETT F， CLARK D， EVANS J B.Piconet: embedded mobile networking[J]. IEEE Personal Communications， 1997，4(5):8-15.

[3]HEINZELMAN W R， CHANDRAKASAN A P， et al. Energy－efficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Hawaii Int’l Conf on System Sciences.San Francisco:IEEE Computer Society， 2000:3005-3014.

[4]KRISHNAMACHARI B， ESTRIN D， WICKER S. Impact of data aggregation in wireless sensor networks[C]//Proc of the 22nd Int’l Conf on Distributed Computing Systems.Washington DC:IEEE Computer Society，2002:575-578.

[5]INTANAGONWIWAT C， GOVINDAN R， et al. Directed diffusion: a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual Int’l Conf on Mobile Computing and Networking.Boston:ACM Press，2000:56-67.

[6]KRISHNAMACHARI B， ESTRIN D， WICKER S. Modeling data－centric routing in wireless sensor networks[C]//Proc of the 21st Annual Joint Conf of IEEE Computer and Communications Socienties.New York:IEEE Computer Society，2002:2－14.

[7]LINDSEY S， RAGHAVENDRA C S， et al. Data gathering in sensor networks using the energy delay metric[C]//Proc of the 15th Int’l Parallel and Distributed Processing Symposium.Washington DC:IEEE Computer Society，2001:924-935.

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