基于LF-GFG的物聯網動態路由算法①

梁藝懷,張立臣

(廣東工業大學 計算機學院,廣州 510006)

引言

物聯網裝置一般是通過無線網絡傳輸,裝置可能會移動,并且可能使用電池作電源.這就要求物聯網的路由協議不僅需要具備低耗能的特性,還必須能適應動態網絡環境的特性.

目前最常見的路由協議有AODV與DSR等,這些路由協定會先通過一個或多個洪泛廣播,得到將封包送達目的地的傳輸路徑,再將數據沿著這條路徑傳到目的地.但是,隨著物聯網的規模逐漸擴大,這些洪泛廣播會造成大量的廣播風暴,導致網絡效能低下.因此,通過目的地的位置信息來取得所需要的傳輸路徑,來避免洪泛廣播風暴問題位置路由協議(Geographic Routing Protocol,GRP)頗受學界關注和研究.

位置路由協議假設每個裝置都有一樣的傳輸半徑,并且每個裝置都能通過一些定位的方法取得自己的精確位置.目前,位置路由協議研究意向產生了GPSR[1]、GFG[2]、GOAFR+[3]、VRR[4]、VPC[5]、和 ABVCap[6]等方法,這些方法大都將網絡轉換為一個平面化的圖形,然后通過右手法則設置虛擬坐標動作,取得所需的傳輸路徑.但是,這些方法完全解決了假設的問題,可以實際應用到真實的環境中,但是為了要保持虛擬坐標所具備的特殊性質,反而讓它們失去了適應動態網絡的能力.當物聯網內的裝置有移動或是開關,這些方法的傳輸能力就會開始下降并且不容易修復.針對這一問題,本文根據LF-GFG方法,設計一種動態物聯網的路由算法.算法可以不需要額外的封包就將整個網絡轉換成一個平面化的圖形,取得所需的傳輸路徑,克服了實際環境應用的問題.

1 算法設計

1.1 設計思路

GFG路由協議中提出的右手法則是早期所有位置路由協議的基礎.在右手法則中,將圖上的邊想象成墻壁,將右手放在墻上往前走(走在墻的左側),若這是一個平面化圖形,則右手法則保證可以越走越靠近目的地.簡而言之,如能將網絡聯機轉化成一個平面化圖形,重復地使用右手法則來決定路由路徑,可以在理論上保證將封包送達目的地.并且不用任何額外的封包,僅僅通過無線網絡傳輸時的RTS、CTS封包,就直接將數據傳到傳輸路徑上的下一點.在研究多跳無線隨意網絡路由協議時,最常使用的方法是將每個裝置表示成一個二維平面上的節點,若2個裝置間可以互相傳輸數據,就在這2個節點間加上一條邊.如此,網絡就可以表示成一個圖形,而路由協議問題就轉化成圖形學問題了.在一個平面化圖形中,所有邊都不會交叉,如何將圖形平面化,是一個很復雜的問題.在物聯網中,為了減少網絡的負擔,每個節點不可能有完整的網絡架構信息,只會有其鄰近節點信息.因此,讓每個節點,利用鄰近節點的信息,就能分布式地將整個圖形平面化,這就是使用右手法則要面臨的問題.傳統做法是通過讓每個節點分布式地滿足Gabriel Graph(GG)[7]或Relative Neighborhood Graph(RNG)[8]等圖形特性,來取得平面化圖形,但是這個做法很難在實際的環境中實現.另一個方法是通過維諾圖(Voronoi diagram)來取得,即LF-GFG所使用的虛擬坐標方法.

為了能夠適應動態網絡環境,必須讓LF-GFG所使用的虛擬坐標轉化為一個分布式的平面化圖形.因此,如何設計這個二維虛擬坐標尤為關鍵.本文按照維諾圖理論,將每個節點劃分一個區域.再將區域相鄰的節點連起來,就會得到一個平面化圖形[9].

在圖1中,有A到L共12個節點,兩個節點之間若有聯機則表示這兩個裝置可以互相通訊.每個節點都劃分一個區域,在執行算法時,先進行網絡拓撲圖平面化動作,通過判斷兩個區域是否相鄰,移除網絡拓撲中不必要的連接,從而達到節省運算開銷問題.圖中的粗線表示可以聯機通信,虛線表示被移除的不必要連接.由于這種方法不需要復雜的計算和多余的封包傳輸被廣為應用.但這種算法沒有考慮通信節點的通信半徑,且只能將網絡拓撲圖進行平面化計算.

圖1 LF-GFG的概念示意圖

1.2 分配虛擬坐標

假設現在有一個物聯網網絡如圖2所示.在網絡中,共有A到K共11個裝置,彼此間可以互相通訊的裝置就會有一條邊將它們連起來.這些裝置并不知道它們自己的位置,只知道它附近有哪些其它節點.

圖2 實際網絡聯機情形

首先,LF-GFG會從一個預先設定好的起始點開始分配虛擬坐標的工作.由于本研究中針對坐標點層級不會太深,且更需保證及時性,要求求解速度且目標節點的層次較淺的情況下深度優先搜尋優于寬度優先搜尋,所以我們使用較優的深度優先搜尋.在提出的算法中,A點是這個起始點.A點會先被分配到一個虛擬坐標a1(0,0),注意這里的坐標是用極坐標表示.同時A點會為這個虛擬坐標劃分出一個區域R(a1).把R(a1)用4個字段(0,1,0,2π)來記錄,分別代表這個區域的內半徑、外半徑、起始角度、結束角度,如圖3中間的圓形所示.接下來,A會發出一個封包,將剛才被分配的虛擬坐標與區域信息通知給周圍的其它節點B、C、D.這個控制封包內還會包含一個串行FL(A),它包含了深度優先搜尋(Depth-First Search,DFS)算法在由A、B、C、D所組成的子圖(subgraph)中間節點造訪的順序[10],也就是FL(A)=(B,C,D,A).收到這個封包的節點就會開始分配虛擬坐標.分配的方法如下：

圖3 分配虛擬坐標

(1)觀察FL(A)內有幾個節點,就將封包內存的角度區間分成幾等分,依序分給每個節點.而每個節點的角度坐標就設為分得角度區間的正中間.

(2)距離坐標則是封包內存區域的外半徑.這樣一來,如圖3中的A、B、C、D4個點都各被分配到一個虛擬坐標a2、b1、c1、d1.a2、b1、c1、d1也會被分配到相對應的區域,其中角度區間就是前面通過FL(A)分得的角度區間,而內半徑就是a1的外半徑,新的外半徑則會被設成比內半徑的1/cosθ大的值,其中θ是所分配到的角度區間.例如c1分配到的區域R(c1)就會被記錄成(1,1 cos 4,2,π),其中δ是一個很小的常數.虛擬坐標計算公式如下：

在A、B、C、D分配完虛擬坐標后,會檢查是否有相鄰的節點還沒有被分配到虛擬坐標,然后重復之前的動作,將坐標分配給還沒有坐標的節點.其中因為A和B的所有相鄰節點都有至少一個虛擬坐標了,所以A和B并不會再發送分配坐標的指令封包.而假如D先發送了分配坐標的指令封包,里面包含的FL(D)會是(F,G,D).此時C要發送分配坐標的指令封包時,它周圍就只剩下E還沒有拿到任何的虛擬坐標,所以FL(C)=(E,C).每個分配到虛擬坐標的節點都重復這個動作,最后整個網絡的節點就會都分配到至少一個虛擬坐標了,如圖3所示.

1.3 建立平面化圖形

在每個節點都有虛擬坐標之后,先將代表網絡的圖2轉化成一張虛擬的二維網絡圖.由于每個節點可能會分配到超過一個虛擬坐標,所以每個節點可能會對應到超過一個虛擬節點.屬于同一個節點的虛擬節點之間當然可以互相溝通,所以我們會在它們之間加上虛擬的邊.而對照圖2,若兩個虛擬節點屬于可以互相溝通的兩個節點,則我們也在它們之間加上虛擬的邊.最后的虛擬網絡圖如圖4所示.

圖4 建立虛擬網絡圖

這時,就能獲得平面化的虛擬圖形,方法如下：如兩個虛擬節點所分配到的區域是相鄰的,而且它們之間有一條邊相連,那么我們就把這條邊加入平面化的虛擬圖形中.例如c2和h1之間有一條邊而且R(c2)和R(h1)相連(參考圖4和圖3),所以c2和h1之間的邊會被加入平面化的虛擬圖形中,如圖5所示.

是否保證取得平面化的虛擬圖形和分配虛擬坐標的方法有很大關聯,并不是隨意分配的虛擬坐標和區域都能用這個方法取得平面化的圖形,而其中的關鍵在于分配區域的內外半徑差距.從圖3我們可以看出來,其實這些分配的區域會形成一個的類似同心圓的架構.每一層同心圓的厚度如果不足,就不能夠保證這個方法取得的圖形是一個平面化的圖形.而我們在分配虛擬坐標時所設定的外半徑需大于內半徑的1/cosθ倍,就是滿足平面化的最低半徑要求,我們可以設定任何大于1/cosθ倍內半徑的值,都能夠保證讓我們得到平面化的圖形[11].

圖5 虛擬平面化結果圖

1.4 決定路由路徑

在取得平面化圖形之后,可以開始運行GFG的右手法則.在GFG中,先使用貪婪算法盡量地將封包送到更靠近目的地的地方.但是貪婪算法并不能保證將封包送達,有些時候,封包會卡在某個節點,而相鄰的節點都比這個節點離目的地更遠.這個時候,就需要靠右手法則來幫我們解決這個問題[12].當有一個封包要從K點送往E點時,我們會先找到K點的一個虛擬坐標k1,然后將目的地設定成E點的一個虛擬坐標e1.我們會發現沒有其它與k1相連的虛擬節點比k1更靠近e1,所以開始使用右手法則.在使用右手法則的時候,我們只看平面化圖形,想象人站在k1的位置,將右手放在k1上沿著平面化圖形走,這樣我們就會遇到了下一個虛擬節點g4,而G就被我們選擇為路由路徑上的下一個節點,并將封包傳送給G.

在節點G,我們會進行同樣的動作,先檢查是否可以使用貪婪算法決定下一個節點,這時我們就發現有與g4相連的其它節點比g4更靠近e1,而我們通過貪婪算法選擇了其中最靠近e1的f1,并將封包傳給f1由擁有者F.最后封包就成功地被送往了E.如圖6所示.

圖6 確定路由路徑

1.5 適應動態網絡

在動態網絡中,要怎么迅速的維護虛擬坐標,讓網絡維持高效能不受影響.動態網絡的各種行為,可以簡化為節點離開與節點加入這兩種,隨著節點從甲地離開到乙地加入則可以組成各種動態網絡的移動行為.因此,當LF-GFG在有節點離開或加入時,則會重新分配虛擬坐標.假設D節點離開了網絡,這時候首先與節點D相連的節點會發現D已經離開了,然后屬于節點D的虛擬節點會被移除,與這些虛擬節點相連的虛擬邊也會被移除.最后的虛擬坐標分配情形如圖7所示.

圖7 D節點離開后虛擬坐標分配

當有一個新的節點L加入這個網絡時,與L相鄰的節點會發現L還沒有虛擬節點,并發送一個分配虛擬節點的控制封包給L.假設是由節點B先發現L的加入,并且要發送分配虛擬節點的控制封包,這個控制封包內會包含B的一個最外層的虛擬節點信息,還有FL(B)=(L,B).這個例子中因為B只有b1一個虛擬節點,所以會將b1的信息傳給L.當L收到這個控制封包后,B和L都會再分配到新的虛擬節點.

如圖8中的l1和b2所示.上述情形虛擬節點的區域外相鄰的區域,在還沒有分配給其它的虛擬節點情況下,當有新的節點加入時,就可以保證找到這種虛擬節點,發送控制封包分配新的虛擬節點給這些新加入網絡的節點.從而實現可以不需要額外的封包就可將整個網絡轉換成一個平面化的圖形,使物聯網裝置快速獲得所需的傳輸路徑.并能有效避免網絡擁塞及洪泛廣播風暴問題.

圖8 L節點加入后虛擬坐標分配

2 算法實驗與結果分析

采用NS-2進行仿真實驗.在實驗中,用不同顏色區分APIT+GFG、ABVCap、VCP和LF-GFG等4種路由協定.隨機建立了100張網絡圖,每張網絡圖都有450個物聯網的裝置.實驗持續了500個時間單位,在第50個時間單位的時候,我們讓網絡發生隨機的1個(粗線)、5%個相連(虛線)、5%個分散(細線)的節點故障,觀察節點故障對網絡效能的影響.每0.1個時間單位,網絡中就有隨機一個裝置送出一個封包到另一個隨機選擇的裝置,我們將10秒內100個網絡圖的所有封包傳輸結果平均之后,得到了下面的實驗結果.

圖9顯示了封包傳達率的實驗結果,我們可以發現,在網絡內有450個節點時,雖然這4個方法在理論上都有百分之百的封包傳達率,但是實際實驗卻會有封包傳輸失敗的情形發生.其中APIT+GFG會傳輸失敗是因為它需要假設每個節點的傳輸半徑都是一個完美的圓,但是計算機程序會有小數點精確度的限制,無法達到這個假設.當第50個時間單位發生節點故障時,VCP因為沒有維護的機制,會導致封包傳達率大幅下降且難以回復；APIT+GFG受影響比較小是因為它假設每個節點都是被散布在一個二維平面且都有精確的坐標,在這個情況下,GFG本身就能理論上有100%的封包傳達率.LF-GFG在節點壞掉時受影響較小也是因為它使用了GFG的右手法則的關系.ABVCap和LFGFG都有維護的機制,所以隨著維護機制的啟動,我們會發現封包傳達率降低后會慢慢的回升,其中我們發現,由于LF-GFG的維護機制十分簡單迅速,所以封包傳達率回升的速度比ABVCap高出很多.

圖9 封包傳達率比較圖

圖10顯示了封包傳輸時間的比較圖,封包傳輸的時間除了受到路徑長度的影響之外,還會受到網絡壅塞程度影響.從圖中我們會發現,雖然LF-GFG較能夠適應動態的網絡環境,但是由于它的虛擬坐標分配并沒有真的平均分散在二維平面上,當使用GFG的右手法則時會容易產生一些熱點,讓這些熱點的負擔很大,造成網絡壅塞,拉長傳輸時間.當有節點壞掉,LFGFG進行維護之后,因為維護時分配的虛擬坐標會在較外層的位置,所以反而讓虛擬坐標的分配較為分散,降低了網絡擁塞的情形.

實驗還比較了LF-GFG和ABVCap在維護動態網絡時所需要的封包量.同樣是5%相連節點壞掉時,在LF-GFG中平均只需要使用9.3個封包就能夠使網絡效能恢復,而ABVCap則平均需要112.9個封包.當只有1個節點壞掉時的數據則是1.3與3.7個封包,從數據中我們可以發現LF-GFG具有較好的容錯效能.實際上,我們發現假如只有1個節點壞掉,60%概率下網絡的效能不會受到影響.

圖10 封包傳輸時間比較圖

3 結語

本文根據LF-GFG提出的路由概念,結合傳統位置路由協議所使用的右手法則和虛擬坐標系統的易實現特性,提出了一種動態物聯網的路由算法.NS-2實驗結果表明,該算法相較于其它的路由協定,具有較高的容錯率,較低的維護成本,和較快的維護速度.