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

（南京理工大學(xué)自動(dòng)化學(xué)院，江蘇南京 210094）

0 引言

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

在實(shí)際網(wǎng)絡(luò)中，由于節(jié)點(diǎn)部署不均勻，節(jié)點(diǎn)間存在障礙物或部分節(jié)點(diǎn)失效等原因，貪婪轉(zhuǎn)發(fā)往往會(huì)遭遇“路由空洞”，即在鄰居中找不到比自己更接近目的節(jié)點(diǎn)的下一跳節(jié)點(diǎn)。為解決該問題，人們提出了許多改進(jìn)算法［4～6］。文獻(xiàn)［4］提出的GPSR協(xié)議使用基于右手法則的邊緣轉(zhuǎn)發(fā)模式處理路由空洞問題，協(xié)議簡單，但對(duì)空洞不具有感知性，因而，選路盲目。對(duì)此，文獻(xiàn)［5］提出了改進(jìn)，讓節(jié)點(diǎn)掌握兩跳鄰居信息，提前感知空洞的存在，從而盡可能及時(shí)繞開，但顯著增加了節(jié)點(diǎn)存儲(chǔ)開銷。文獻(xiàn)［6］在網(wǎng)絡(luò)拓?fù)渚植科矫婊幕A(chǔ)上，通過探測(cè)包建立的路標(biāo)，使后續(xù)數(shù)據(jù)包避開空洞，但大量探測(cè)包的發(fā)送增加了節(jié)點(diǎn)通信開銷。同時(shí)，這些協(xié)議均依賴于平面化算法，而該算法對(duì)節(jié)點(diǎn)位置和通信半徑誤差敏感:隨著誤差增大，算法會(huì)逐漸失效，進(jìn)而導(dǎo)致路由環(huán)路。另外，平面化算法對(duì)節(jié)點(diǎn)的運(yùn)算和存儲(chǔ)能力要求較高。

為此，本文提出了一種基于節(jié)點(diǎn)標(biāo)號(hào)的貪婪轉(zhuǎn)發(fā)（label-based greedy forwarding，LBGF）算法，其核心思想是:將網(wǎng)絡(luò)中的節(jié)點(diǎn)組成一個(gè)以位于網(wǎng)絡(luò)中心的參考節(jié)點(diǎn)（通常為Sink節(jié)點(diǎn)）為根的帶環(huán)樹，樹中根節(jié)點(diǎn)根據(jù)子節(jié)點(diǎn)的位置信息為其分配特征序號(hào)，并將其接在自身標(biāo)號(hào)（label）后產(chǎn)生子節(jié)點(diǎn)標(biāo)號(hào)，重復(fù)該過程，最終形成一個(gè)以參考節(jié)點(diǎn)為根的樹型標(biāo)號(hào)系統(tǒng)，而貪婪轉(zhuǎn)發(fā)算法便運(yùn)行于該系統(tǒng)之上。仿真實(shí)驗(yàn)表明:在網(wǎng)絡(luò)中存在較多或較大空洞時(shí)，相對(duì)于GPSR算法，LBGF算法路由效率更高，容錯(cuò)性更強(qiáng)，對(duì)節(jié)點(diǎn)的運(yùn)算和存儲(chǔ)能力要求更低。

1 標(biāo)號(hào)系統(tǒng)的建立

標(biāo)號(hào)系統(tǒng)和LBGF算法基于3個(gè)假設(shè):1）節(jié)點(diǎn)有唯一ID，以彼此區(qū)別;2）通過某種定位算法，節(jié)點(diǎn)已知其地理位置與參考節(jié)點(diǎn)的位置;3）通信鏈路為雙向鏈路。

標(biāo)號(hào)系統(tǒng)的建立是基于節(jié)點(diǎn)狀態(tài)的，根據(jù)父節(jié)點(diǎn)ID（pID）和節(jié)點(diǎn)標(biāo)號(hào)（label）的值的情況，節(jié)點(diǎn)狀態(tài)可分為黑色（均為空）、灰色（label為空）和白色（均不為空）3種，初始時(shí)所有節(jié)點(diǎn)均處于黑色狀態(tài)，建立過程結(jié)束后，狀態(tài)均轉(zhuǎn)為白色，節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換由消息驅(qū)動(dòng)。整個(gè)建立過程主要包括以下四步:

1）參考節(jié)點(diǎn)將label置為0（設(shè)置pID為某一特殊值），進(jìn)入白色狀態(tài)，并向周圍節(jié)點(diǎn)廣播selfMsg以啟動(dòng)建立過程。

2）黑色節(jié)點(diǎn)（處于黑色狀態(tài)的節(jié)點(diǎn)）收到selfMsg后，設(shè)置pID為srcID，進(jìn)入灰色狀態(tài)，并向父節(jié)點(diǎn)發(fā)送reqMsg。

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

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

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

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

2 LBGF算法

2．1 LBGF 理論分析

圖1 標(biāo)號(hào)系統(tǒng)結(jié)構(gòu)圖Fig 1 Figure of label system structure

A，B為網(wǎng)絡(luò)中的任意兩節(jié)點(diǎn)，lb（A）和lb（B）分別表示其標(biāo)號(hào)值，若兩者長度和相應(yīng)位均相等，則稱它們相等或相同，記為lb（A）=lb（B）;若前者長度小于后者，且從高位開始每位均與后者相應(yīng)位相等，則稱前者包含后者即lb（A）包含lb（B）。

定理1 節(jié)點(diǎn)標(biāo)號(hào)唯一。

證明 根據(jù)第一節(jié)中標(biāo)號(hào)系統(tǒng)的建立過程應(yīng)用遞推的方法易證結(jié)論。

推論1 從高位開始，lb（A）和lb（B）的相同部分必為A與B最近共同祖先（least common ancestor，LCA）的標(biāo)號(hào)，記為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為同一節(jié)點(diǎn)。

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

定理2 兩節(jié)點(diǎn)A，B，若dist（A，B）=0，那么，A，B必為同一節(jié)點(diǎn)。

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

定理3 LBGF具有無環(huán)性和空洞避免性。

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

2．2 LBGF算法路由過程

節(jié)點(diǎn)使用貪婪原則轉(zhuǎn)發(fā)數(shù)據(jù)包直到到達(dá)目的節(jié)點(diǎn)，如圖2中S到D的虛線路徑。該路徑并非最短路徑，這主要是因?yàn)長BGF算法建立的標(biāo)號(hào)系統(tǒng)為樹型結(jié)構(gòu)，節(jié)點(diǎn)間血緣越遠(yuǎn)，其標(biāo)號(hào)相似度愈低，相互間通信的實(shí)際路徑偏離最短路徑的可能性愈高。同時(shí)，因父節(jié)點(diǎn)往往比子節(jié)點(diǎn)距離目的節(jié)點(diǎn)更近，致使LBGF算法傾向于選擇父節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，這會(huì)導(dǎo)致靠近樹根的節(jié)點(diǎn)“過載”。

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

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

3 仿真分析

使用OMNET++對(duì)LBGF算法進(jìn)行仿真，主要參數(shù):部署區(qū)域?yàn)?00 m×300 m;通信半徑為30 m;節(jié)點(diǎn)數(shù)目為200;鄰居表跳數(shù)為2;空洞尺寸為60m×50m，120m×50m。

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

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

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

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

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

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

圖5 路由成功率對(duì)比Fig 5 Comparison of routing success rate

4 結(jié)束語

在解決無線傳感器網(wǎng)絡(luò)路由空洞問題時(shí)，大多數(shù)地理路由依據(jù)平面化的網(wǎng)絡(luò)拓?fù)洳捎眠吘壔謴?fù)機(jī)制使數(shù)據(jù)傳輸重新回到貪婪轉(zhuǎn)發(fā)模式，這種被動(dòng)式的反應(yīng)策略大大降低了路由效率，尤其當(dāng)網(wǎng)絡(luò)中空洞密集時(shí)更嚴(yán)重，而且，平面化算法對(duì)節(jié)點(diǎn)位置精度、運(yùn)算和存儲(chǔ)能力要求較高，這些都導(dǎo)致該類算法很難用于實(shí)際。本文提出的LBGF算法，并不直接使用節(jié)點(diǎn)位置信息作為路由的依據(jù)，而是以之為參考建立一個(gè)樹型標(biāo)號(hào)系統(tǒng)并重新定義節(jié)點(diǎn)間的距離，使貪婪轉(zhuǎn)發(fā)算法運(yùn)行在標(biāo)號(hào)系統(tǒng)上，以此來主動(dòng)避免“路由空洞”。仿真表明:在存在不同大小和數(shù)目空洞的情況下，LBGF算法能以較小的開銷獲得較好的性能，從而較適用于空洞較大、較密集的無線傳感器網(wǎng)絡(luò)環(huán)境。

［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］ 沙 超，王汝傳，孫力娟，等．無線傳感器網(wǎng)絡(luò)中一種信標(biāo)節(jié)點(diǎn)可遷移的協(xié)作定位方法［J］．電子學(xué)報(bào)，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］．電子學(xué)報(bào)，2008，36（10）:1903 －1909．

［6］ 張衡陽，王 玲，劉云輝，等．路標(biāo)迭代提取和剔除的自適應(yīng)空洞處理算法［J］．軟件學(xué)報(bào)，2009，20（10）:2744 －2751．