基于位置信息的無線自組網路由算法對比研究?

胥建鵬 敖 欣

（1.西安工業大學電子信息工程學院 西安 710021）（2.東莞理工學院網絡空間安全學院 東莞 523808）

1 引言

不依賴于固定基礎設施，無線自組網中各節點通過自組織、自我管理的方式動態組網［1］，具有很高的靈活性。因此，針對這種拓撲變化頻繁的網絡設計適應性強的路由協議成為國內外學者研究的重點［2］。功率所限，無線節點只能直接與周圍一跳鄰居節點進行通信。在此限制下，傳統無線路由協議所能依靠的決策信息非常有限，對鄰居節點的運動也缺乏預測性。雖然有些路由算法基于無線信號傳播經驗模型、節點運動與信號變化的關聯模型等分析手段，可以獲得一些粗粒度的相對位置信息，但仍然存在較大的決策誤差。

近年來，隨著GPS接收裝置走向微型化、低功耗、低成本，越來越多的無線節點開始裝備GPS模塊。因此，利用節點位置這一新的決策信息，來更好地建立無線自組網路由，逐漸成為一種實用的路由選擇。此類算法也因此被稱為地理位置路由算法。其中，作為典型代表的GPSR協議應用最廣，并催生了包括GPSR-R、WF-IGPSR等在內的后續改進協議。利用內置的節點位置信息，地理位置路由算法可免于路由維護，具有路由開銷小、時延性能好等顯著特點。然而，受傳輸功率所限，節點間的位置信息交互仍然只能局限在一跳傳輸范圍，導致節點只有局部的位置視野，容易遭遇路由空洞而降低路由轉發效率。此外，考慮到節點運動方向、速度均可能發生變化，基于節點間交互的位置信息進行的位置預測很可能失效。特別是當節點移動速度較大、節點密度稀疏時，節點位置信息可能頻繁失效，并引起嚴重的丟包。

理想的Ad-Hoc網絡的路由協議必須具備以下功能：1）維護網絡拓撲的鏈接；2）快速地了解網絡拓撲結構的變化；3）良好的自適應能力［3］。由此而知，地理位置路由算法仍然存在一定的優化空間，需要徹底解決路由空洞、位置信息交互頻率的自適應調整等挑戰。為此，本文對GPSR及其改進算法GPSR-R、WF-IGPSR進行對比研究，并基于NS2仿真平臺，從端到端時延和分組交付率等角度對上述三種算法優缺點進行客觀分析與評價。

2 GPSR及其改進算法基本原理

GPSR（Greedy Perimeter Stateless Routing ，GPSR）［4］貪婪周邊無狀態路由協議是一種典型的基于地理位置信息的自組網路由算法。網絡中的每個節點通過GPS獲得自身位置，源節點根據數據分組中目的節點位置完成分組的轉發［5～6］任務。GPSR有兩種轉發模式，貪婪轉發和周邊轉發［7］。GPSR路由協議的貪婪轉發是將其傳輸范圍內離目的節點最近的節點作為下一跳節點［8］。在網絡中節點分布均勻且移動速度相對緩慢的情況下，GPSR能夠將分組較快的轉發到目的節點。但在網絡節點分布不均和節點移動速度較快的情況下，由于GPSR路由判據單一，選擇的下一跳節點大都分布在通信的邊界區域，容易引起路由空洞和丟包。在分組轉發過程中遇到路由空洞時，GPSR將自動切換到周邊轉發模式，借助平面圖和右手法則繞過空洞區域［9］，當再次滿足貪婪轉發條件時，網絡又將切換到貪婪轉發模式。GPSR路由協議存在當貪婪轉發失效而采用周邊轉發而造成路由冗余度增加的現象，此外，鄰居表信息更新過慢，在轉發數據包時，保存在表頭中的目的節點位置沒有更新等［10］。因此，GPSR路由協議依然有需要改進的地方。

GPSR-R（Reliability Based GPSR Protocol）［11］是GPSR的一種改進算法，針對GPSR算法中下一跳節點選擇機制的缺陷和鏈路質量低下等問題，GPSR-R算法側重強調鏈路質量，關注分組交付率。為了獲得可靠的傳輸路徑，選擇相對穩定的節點作為下一跳轉發節點，GPSR-R在鏈路穩定性高于一定閾值的鏈路上完成分組的轉發任務，可以有效避免GPSR算法選擇下一跳節點分布在節點通信邊緣的風險所引起的鏈路不穩定和極易斷裂情況，因此，GPSR-R算法獲得了較高的分組交付率，但同時，由于過分注重傳輸鏈路的穩定性，增加了分組的轉發跳數，GPSR-R算法的時延特性比GPSR差。

WF-IGPSR（The Weighted Function Based GPSR Protocol）［12］是GPSR的另為一種改進算法，針對GPSR路由算法選擇的下一跳節點缺乏穩定性、容易遭遇路由空洞等問題，WF-IGPSR算法提出了利用權重函數在鄰居節點中選擇可靠的下一跳分組轉發節點。權重函數受三方面的因素影響，第一，鏈路的穩定性，用來描述所選擇路徑的可靠程度；第二，距離，即下一跳轉發節點到目的節點的距離，用來描述下一跳節點與源節點的接近程度；第三，運動方向，用來描述下一跳節點運動方向與目的節點所在位置的偏向程度。源節點在鄰居節點中選擇權重函數最大的鄰居節點作為下一跳分組的轉發節點，既可以保證數據分組轉發鏈路的穩定性，又可以有效地降低路由空洞出現的概率，因此，WF-IGPSR算法能夠保證一定的分組交付率的情況下兼顧了時延特性，在兩者之間進行比較合理的折中和均衡。

3 仿真分析

無線自組網中路由算法的性能主要通過分組交付率和平均端到端時延等指標進行評價。分組丟包率越高表明路由協議的性能越穩定［13］；平均端到端時延越小，表明網絡中路由投遞的分組越快［14］。為了驗證GPSR、GPSR-R和WF-IGPSR的網絡性能，利用NS-2仿真平臺，通過多次實驗取平均值的方法獲得不同算法對應的性能參數，并對三種算法做出客觀的、合理的評價。由于在Ad-Hoc自組網中，路由的性能受網絡中節點密度和移動速度影響顯著，因此，本次實驗分成兩部分來完成。其中，第一部分是不同節點密度下三種路由協議的性能對比；第二部分是不同節點移動速度下三種路由協議的性能對比。實驗主要參數設置如表1所示。

表1 實驗參數

3.1 不同節點密度下的路由性能分析與評價

圖1和圖2描述的是不同節點數變化時，GPSR、GPSR-R和WF-IGPSR三種算法在平均端到端時延和分組交付率方面的比較。

圖1 平均端到端時延與節點密度的關系

圖2 分組交付率與節點密度的關系

由圖1可知，三者的變化曲線可描述為，三種路由算法的平均端到端時延曲線隨節點密度增大呈現下降趨勢，其中，GPSR的時延最小，WF-IGPSR次之，GPSR-R時延最大。具體表現為當網絡中節點數目在20～35個范圍變化時，GPSR、WF-IGPSR和GPSR-R之間的時延差距較大，隨著節點數目的增多，三者的時延差距呈現縮小態勢，時延性能相當。其原因在于GPSR算法采用貪婪轉發策略，能夠維持較小的時延；WF-IGPSR算法在選擇下一節點時，因為考慮了距離和方向角因素，能夠使數據分組沿著目的節點方向快速的轉發，但由于兼顧了傳輸鏈路的質量，所以，WF-IGPSR算法的傳輸時延性能不如GPSR；GPSR-R算法側重傳輸鏈路的穩定性，為了選擇可靠的下一跳節點，犧牲了時延特性，所以，時延特性最差。但隨著節點密度的增加，可供選擇的中間轉發節點數目也隨之增加，三者之間的差距不斷縮小；當網絡中節點數目為50個左右時，三者的時延特性表現相當，均降至50ms左右。

由圖2可知，三者的變化曲線可描述為：三種路由算法的分組交付率隨節點密度增大呈上升趨勢，其中，GPSR的分組交付率最低，WF-IGPSR次之，GPSR-R最高。具體表現為當網絡中節點數目在20個左右時，GPSR和WF-IGPSR算法的分組交付率只有35%左右，而GPSR-R為50%左右，相差較大；其原因是網絡中節點數目較少時，GPSR和WF-IGPSR算法可供選擇的下一跳節點數目相對較少，選擇的分組轉發路徑質量較差，容易斷裂，分組交付率較低；GPSR-R算法側重傳輸鏈路的穩定性，選擇可靠的、質量高的鏈路進行分組轉發，分組交付率最高。隨著網絡中節點數目的增加，三種算法都能選擇相對穩定的鏈路進行分組轉發，各自對應的分組交付率也隨之不斷升高，相互間的差距也呈現縮小態勢，當網絡中節點數目為50個左右時，GPSR、WF-IGPSR和GPSR-R算法的分組交付率分別達到86%、95%和98%左右。

3.2 不同節點移動速度下的路由性能分析與評價

圖3 平均端到端時延與節點移動性的關系

圖3 和圖4描述的是不同節點平均速度時，GP-SR、GPSR-R和WF-IGPSR三種算法在平均端到端時延和分組交付率方面的比較。

圖4 分組交付率與節點移動性的關系

由圖3可知，三者的變化曲線可描述為：三種路由算法的平均端到端時延曲線隨節點速度增大呈現上升趨勢，其中，GPSR的時延最小，WF-IGPSR次之，GPSR-R時延較大。具體表現為當網絡中節點的平均速度為40km/h～60km/h時，網絡拓撲結構變化相對緩慢，鏈路質量相對較好，數據分組在網絡中能夠得到及時的轉發，三種算法的平均端到端時延較小；隨著節點移動速度的增加，三種算法的平均端到端時延增大，當節點平均速度為120km/h時，引起網絡拓撲結構頻繁變化，下一跳節點可靠性和鏈路質量隨之下降，網絡中節點為了及時更新各自有效的鄰居節點表而需要使用大量的控制信息，這將占用大量的網絡資源，網絡擁堵程度隨之加重，數據分組不能得到及時轉發，GPSR、WF-IGPSR和GPSR-R三種算法的傳輸時延隨之分別增至175ms、210ms和250ms左右。具體原因在于GPSR算法選擇鄰居節點中距離目的節點最近的節點進行分組的轉發，時延最小；WF-IGPSR算法在鏈路質量和傳輸時延之間進行均衡，選擇鄰居節點中權重函數值最大的節點進行分組的轉發，時延方面比GPSR大；GPSR-R算法只注重傳輸鏈路的質量，時延特性表現最差。

由圖4可知，三者的變化曲線可描述為：三種路由算法的分組交付率隨節點運動速度的增大呈下降趨勢，其中，GPSR的分組交付率最低，WF-IGPSR次之，GPSR-R最高，并且GPSR算法的分組交付率性能較WF-IGPSR和GPSR-R算法下降速度較快。具體表現為當網絡中節點的平均速度為40km/h～60km/h時，三種算法所選擇的下一跳節點相對穩定，轉發路徑也相對可靠，分組交付率維持在85%以上；隨著節點運動速度的增大，三種算法的分組交付率呈現下降趨勢，其中GPSR算法的分組交付率的下降趨勢最為突出，當節點平均速度為120km/h時，由于快速移動導致網絡中所有節點位置的不確定性增大，選擇的下一跳分組轉發節點運動出源節點的通信范圍的風險隨之增大，數據轉發路徑越不可靠，GPSR、WF-IGPSR和GPSR-R算法的分組交付率分別降至60%、75%和80%。其具體原因是，GPSR算法僅以最短歐式距離為依據選擇的下一跳節點大都分布在節點通信的邊界區域，隨著節點運動速度的增大，下一跳節點移出源節點通信范圍的風險越大，對應著鏈路質量越差，分組交付率最低；WF-IGPSR算法較GPSR算法，以權重函數選擇的下一跳節點相對可靠，傳輸鏈路相對穩定，能夠維持一定的交付率；GPSR-R算法側重強調鏈路質量，選擇分組的轉發路徑可靠性最高，因此，交付率性能最好。

4 結語

為進一步探索地理位置路由的優化空間，本文對GPSR及其改進算法GPSR-R、WF-IGPSR進行對比研究。仿真實驗結果表明，在三種算法中，GPSR的時延特性表現最好，而分組交付率特性表現最差；WF-IGPSR的時延特性和交付率特性表現居中；GPSR-R的交付率特性表現最好，而時延特性表現最差。三種算法的設計有不同側重點和應用需求，整體而言，WF-IGPSR算法能夠保證一定的分組交付率的情況下兼顧了時延特性，在兩者之間進行了比較合理的折中和均衡。三種算法共同的缺點是，都采用固定的信標交互周期。這在一定程度上嚴重影響和制約了路由算法的性能和適用空間。在Ad-Hoc網絡中，節點的隨機移動是最顯著的特征，也是引起網絡拓撲結構隨時都可能發生變化的根本原因，因此，網絡拓撲結構變化快慢和鄰居節點表更新間隔的同步性顯得尤為重要，而鄰居節點表的更新需要借助節點間的信標交互信息來完成，所以，網絡中節點之間的信標交互間隔的選擇成為了研究的重點。當信標交互間隔選擇較小時，當網絡規模較大時，頻繁的信標交互信息占用大量的網絡資源，容易引起擁堵；當信標交互間隔選擇較大時，鄰居節點表的更新將滯后于網絡拓撲變化，容易出現鄰居節點表失效問題。鑒于固定式信標間隔的上述缺點，如能夠根據網絡環境的變化自動調整信標交互間隔，即采用自適應式信標交互間隔，將有望解決頻繁交互的網絡擁堵或交互遲滯引發的鄰居節點表失效等問題。換言之，自適應信標交互周期體制更適用于拓撲變化快的無線自組網，并可考慮作為進一步優化無線自組網地理位置路由算法的一個實際著手點。