無線傳感器網絡中一種基于標號的貪婪轉發算法*

侯貴升，吳曉蓓，黃 成，徐志良

（南京理工大學自動化學院，江蘇南京 210094）

0 引言

在無線傳感器網絡（wireless sensor networks，WSNs）中［1］，因應用的需求，通過定位算法［2，3］節點能在大多數情況下較容易地獲得自身的物理位置。因此，基于地理位置的路由算法在WSNs中得到了廣泛的研究。地理路由普遍使用貪婪轉發策略傳輸數據，即在鄰居中選擇距離目的節點最近的節點作為下一跳節點。

在實際網絡中，由于節點部署不均勻，節點間存在障礙物或部分節點失效等原因，貪婪轉發往往會遭遇“路由空洞”，即在鄰居中找不到比自己更接近目的節點的下一跳節點。為解決該問題，人們提出了許多改進算法［4～6］。文獻［4］提出的GPSR協議使用基于右手法則的邊緣轉發模式處理路由空洞問題，協議簡單，但對空洞不具有感知性，因而，選路盲目。對此，文獻［5］提出了改進，讓節點掌握兩跳鄰居信息，提前感知空洞的存在，從而盡可能及時繞開，但顯著增加了節點存儲開銷。文獻［6］在網絡拓撲局部平面化的基礎上，通過探測包建立的路標，使后續數據包避開空洞，但大量探測包的發送增加了節點通信開銷。同時，這些協議均依賴于平面化算法，而該算法對節點位置和通信半徑誤差敏感:隨著誤差增大，算法會逐漸失效，進而導致路由環路。另外，平面化算法對節點的運算和存儲能力要求較高。

為此，本文提出了一種基于節點標號的貪婪轉發（label-based greedy forwarding，LBGF）算法，其核心思想是:將網絡中的節點組成一個以位于網絡中心的參考節點（通常為Sink節點）為根的帶環樹，樹中根節點根據子節點的位置信息為其分配特征序號，并將其接在自身標號（label）后產生子節點標號，重復該過程，最終形成一個以參考節點為根的樹型標號系統，而貪婪轉發算法便運行于該系統之上。仿真實驗表明:在網絡中存在較多或較大空洞時，相對于GPSR算法，LBGF算法路由效率更高，容錯性更強，對節點的運算和存儲能力要求更低。

1 標號系統的建立

標號系統和LBGF算法基于3個假設:1）節點有唯一ID，以彼此區別;2）通過某種定位算法，節點已知其地理位置與參考節點的位置;3）通信鏈路為雙向鏈路。

標號系統的建立是基于節點狀態的，根據父節點ID（pID）和節點標號（label）的值的情況，節點狀態可分為黑色（均為空）、灰色（label為空）和白色（均不為空）3種，初始時所有節點均處于黑色狀態，建立過程結束后，狀態均轉為白色，節點的狀態轉換由消息驅動。整個建立過程主要包括以下四步:

1）參考節點將label置為0（設置pID為某一特殊值），進入白色狀態，并向周圍節點廣播selfMsg以啟動建立過程。

2）黑色節點（處于黑色狀態的節點）收到selfMsg后，設置pID為srcID，進入灰色狀態，并向父節點發送reqMsg。

3）白色節點收到reqMsg后，將其源節點加入子節點集，然后根據它們的位置信息按輻角大小（以參考節點為坐標原點）從0開始依次為其分配序號，最大序號值不超過子節點數上限值減1，所以，輻角較大的子節點將可能被拒絕，分配結果通過labelMsg廣播出去。

4）灰色節點收到labelMsg后，首先確認是否被拒絕，若被拒絕，則重新回到黑色狀態，否則，從中取出自己的序號（特征序號）并將其接在父節點label后作為自身label，同時將自身狀態設為白色，然后廣播selfMsg以推進建立過程。主要消息列表如表1。

表1 主要消息列表Tab 1 Sheet of main messages

另外，無論處于何狀態，收到selfMsg后，節點都須將其源節點加入鄰居表中，待label確定后按它們與自身的關系重新組織鄰居表，這些關系包括父子、兄弟、叔侄和其他共6種關系，除其他外，其余5種關系中的節點都只需存儲其特征序號即可，而特征序號一般都很小，這樣可最大限度地壓縮鄰居表，降低節點存儲開銷。當節點狀態都轉為白色后，標號系統建立成功，如圖1所示。

2 LBGF算法

2．1 LBGF 理論分析

圖1 標號系統結構圖Fig 1 Figure of label system structure

A，B為網絡中的任意兩節點，lb（A）和lb（B）分別表示其標號值，若兩者長度和相應位均相等，則稱它們相等或相同，記為lb（A）=lb（B）;若前者長度小于后者，且從高位開始每位均與后者相應位相等，則稱前者包含后者即lb（A）包含lb（B）。

定理1 節點標號唯一。

證明 根據第一節中標號系統的建立過程應用遞推的方法易證結論。

推論1 從高位開始，lb（A）和lb（B）的相同部分必為A與B最近共同祖先（least common ancestor，LCA）的標號，記為lb（LCA［A，B］）;若lb（LCA［A，B］）與lb（A）的長度相等且小于lb（B），那么，lb（A）包含lb（B）亦即B在A子樹上;若lb（LCA［A，B］），lb（A）與lb（B）長度相等，那么，lb（A）=lb（B）且A，B為同一節點。

定義1 定義dist（A，B）為A，B間的距離，其值為lb（A）與lb（B）的長度和減去lb（LCA［A，B］）長度的2倍。

定理2 兩節點A，B，若dist（A，B）=0，那么，A，B必為同一節點。

證明 用反證法。假設A，B為不同節點，那么，lb（A）與lb（B）不等。如果兩者長度不等，lb（LCA［A，B］）的長度必定不大于兩者中的較小者;如果兩者長度相等，則lb（LCA［A，B］）的長度必定小于其中任何一個，所以，dist（A，B）就應大于0，而這與已知條件“dist（A，B）=0”相矛盾。因而，結論成立。

定理3 LBGF具有無環性和空洞避免性。

證明 不妨設S為當前節點，D為目的節點:1）若dist（S，D）=0，則S，D為同一節點，消息到達;2）若dist（S，D）＞0且lb（S）包含lb（D），此時D位于S子樹上，消息將沿著S子樹向下直達D;3）若dist（S，D）＞0，但lb（S）不包含lb（D），此時D不在S子樹上，因而，S不是參考節點，不妨設其父節點為P，顯然，lb（P）的長度比lb（S）小1，而此時lb（LCA［S，P］）與lb（LCA［S，D］）的長度相等，所以，dist（S，D）比dist（S，P）大1，因而，S始終能找到比自己更接近D的下一跳節點。綜上所述，結論獲證。

2．2 LBGF算法路由過程

節點使用貪婪原則轉發數據包直到到達目的節點，如圖2中S到D的虛線路徑。該路徑并非最短路徑，這主要是因為LBGF算法建立的標號系統為樹型結構，節點間血緣越遠，其標號相似度愈低，相互間通信的實際路徑偏離最短路徑的可能性愈高。同時，因父節點往往比子節點距離目的節點更近，致使LBGF算法傾向于選擇父節點作為下一跳節點，這會導致靠近樹根的節點“過載”。

解決以上2個問題的一種可行方案是讓節點維護一個2跳或多跳（3跳與3跳以上）鄰居表，這樣，節點便能在一個較大范圍內選擇合適的下一跳節點，所選路徑必然更接近最短路徑，同時，“過載”問題也會得到緩解，如圖2中S到D的實線路徑即為2跳鄰居表下LBGF算法所選路徑。增加鄰居表跳數固然能提高LBGF算法的某些性能，如路徑長度、時延、負載平衡等，但卻會相應增加節點的存儲開銷，實際應用中可根據具體情況作一個權衡。一般而言，因2跳范圍內節點間的血緣關系較近，2跳鄰居表相對于1跳鄰居表在采用第一節所述壓縮存儲方式下不會明顯增加節點存儲開銷，但能幫助LBGF算法顯著提高路由性能，所以，LBGF算法在多數情況下可采用2跳鄰居表。

圖2 LBGF算法路由示意圖Fig 2 Sketch map of LBGF algorithm routing

3 仿真分析

使用OMNET++對LBGF算法進行仿真，主要參數:部署區域為300 m×300 m;通信半徑為30 m;節點數目為200;鄰居表跳數為2;空洞尺寸為60m×50m，120m×50m。

3．1 平均路徑長度比與路由包包頭開銷

平均路徑長度比即實際路徑與最短路徑長度比的平均值，它集中反映一個路由算法的路由效率:平均路徑長度比愈小，實際路徑愈接近最短路徑，傳輸數據到目的節點所消耗的總能量愈少，時延也越小，因而，路由效率愈高。圖3顯示了不同空洞數目和大小下LBGF算法和GPSR算法的平均路徑長度比，從中不難看出:LBGF算法受空洞影響較小，而GPSR算法在空洞數目較多或空洞尺寸較大時，路由效率會顯著降低。所以，相對于GPSR算法，LBGF算法在節點稀疏或存在較大、較多障礙物的網絡中有更好的性能。圖4顯示了大尺寸空洞（120 m×50 m）數目下2種算法的路由包包頭開銷。GPSR算法在遭遇“路由空洞”時以邊界轉發模式繞過空洞，而該模式下路由包包頭比貪婪轉發模式下要復雜得多，所以，空洞愈多，邊界轉發模式使用愈頻繁，包頭開銷自然愈高。

3．2 不同位置誤差下的路由成功率

圖3 平均路徑長度比對比Fig 3 Comparison of average path length ratio

圖4 路由包包頭開銷對比Fig 4 Comparison of packet head cost of routing packet

LBGF算法和GPSR都需要節點的位置信息，不同之處在于對精度的要求:LBGF算法只將節點的位置信息作為給子節點分配特征序號的參考依據，對精度要求不高;而GPSR以節點的位置信息作為路由的依據，對節點位置誤差敏感。圖5顯示了不同位置誤差下2種算法的路由成功率。節點位置誤差會影響LBGF算法的路由效率，但卻不會造成目的節點不可達，而GPSR算法的情況則不同:隨著位置誤差增大，GPSR算法的平面化策略會逐漸失效，即把本應移除平面圖的節點保留，而將本應保留的節點錯誤移除，前者在邊界轉發模式時會造成路由環路，后者則會導致目的節點不可達，而兩者都會致使路由失敗。

圖5 路由成功率對比Fig 5 Comparison of routing success rate

4 結束語

在解決無線傳感器網絡路由空洞問題時，大多數地理路由依據平面化的網絡拓撲采用邊緣恢復機制使數據傳輸重新回到貪婪轉發模式，這種被動式的反應策略大大降低了路由效率，尤其當網絡中空洞密集時更嚴重，而且，平面化算法對節點位置精度、運算和存儲能力要求較高，這些都導致該類算法很難用于實際。本文提出的LBGF算法，并不直接使用節點位置信息作為路由的依據，而是以之為參考建立一個樹型標號系統并重新定義節點間的距離，使貪婪轉發算法運行在標號系統上，以此來主動避免“路由空洞”。仿真表明:在存在不同大小和數目空洞的情況下，LBGF算法能以較小的開銷獲得較好的性能，從而較適用于空洞較大、較密集的無線傳感器網絡環境。

［1］ Liu G X，Yu Z W．Survey on wireless sensor networks［C］∥Proceedings of the 2011 International Conference on Internet Technology and Applications（ITA），2011:1 －8．

［2］ Ssu K F，Ou C H，Jiau H C．Localization with mobile anchor points in wireless sensor networks［J］．IEEE Trans on Vehicular Technology，2005，54（3）:1187 －1197．

［3］ 沙 超，王汝傳，孫力娟，等．無線傳感器網絡中一種信標節點可遷移的協作定位方法［J］．電子學報，2010，38（11）:2625－2629．

［4］ Karp B，Kung H T．GPSR:Greedy perimeter stateless routing for wireless networks［C］∥The 6th Annual International Conference on Mobile Computing and Networking，Boston，2000:243 －254．

［5］ 王建新，趙湘寧，劉輝宇．一種基于兩跳鄰居信息的貪婪地理路由算法［J］．電子學報，2008，36（10）:1903 －1909．

［6］ 張衡陽，王 玲，劉云輝，等．路標迭代提取和剔除的自適應空洞處理算法［J］．軟件學報，2009，20（10）:2744 －2751．