基于位置信息的無(wú)線自組網(wǎng)路由算法對(duì)比研究?

胥建鵬 敖 欣

（1.西安工業(yè)大學(xué)電子信息工程學(xué)院 西安 710021）（2.東莞理工學(xué)院網(wǎng)絡(luò)空間安全學(xué)院 東莞 523808）

1 引言

不依賴于固定基礎(chǔ)設(shè)施，無(wú)線自組網(wǎng)中各節(jié)點(diǎn)通過(guò)自組織、自我管理的方式動(dòng)態(tài)組網(wǎng)［1］，具有很高的靈活性。因此，針對(duì)這種拓?fù)渥兓l繁的網(wǎng)絡(luò)設(shè)計(jì)適應(yīng)性強(qiáng)的路由協(xié)議成為國(guó)內(nèi)外學(xué)者研究的重點(diǎn)［2］。功率所限，無(wú)線節(jié)點(diǎn)只能直接與周圍一跳鄰居節(jié)點(diǎn)進(jìn)行通信。在此限制下，傳統(tǒng)無(wú)線路由協(xié)議所能依靠的決策信息非常有限，對(duì)鄰居節(jié)點(diǎn)的運(yùn)動(dòng)也缺乏預(yù)測(cè)性。雖然有些路由算法基于無(wú)線信號(hào)傳播經(jīng)驗(yàn)?zāi)Ｐ?、?jié)點(diǎn)運(yùn)動(dòng)與信號(hào)變化的關(guān)聯(lián)模型等分析手段，可以獲得一些粗粒度的相對(duì)位置信息，但仍然存在較大的決策誤差。

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

理想的Ad-Hoc網(wǎng)絡(luò)的路由協(xié)議必須具備以下功能：1）維護(hù)網(wǎng)絡(luò)拓?fù)涞逆溄樱?）快速地了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化；3）良好的自適應(yīng)能力［3］。由此而知，地理位置路由算法仍然存在一定的優(yōu)化空間，需要徹底解決路由空洞、位置信息交互頻率的自適應(yīng)調(diào)整等挑戰(zhàn)。為此，本文對(duì)GPSR及其改進(jìn)算法GPSR-R、WF-IGPSR進(jìn)行對(duì)比研究，并基于NS2仿真平臺(tái)，從端到端時(shí)延和分組交付率等角度對(duì)上述三種算法優(yōu)缺點(diǎn)進(jìn)行客觀分析與評(píng)價(jià)。

2 GPSR及其改進(jìn)算法基本原理

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

GPSR-R（Reliability Based GPSR Protocol）［11］是GPSR的一種改進(jìn)算法，針對(duì)GPSR算法中下一跳節(jié)點(diǎn)選擇機(jī)制的缺陷和鏈路質(zhì)量低下等問(wèn)題，GPSR-R算法側(cè)重強(qiáng)調(diào)鏈路質(zhì)量，關(guān)注分組交付率。為了獲得可靠的傳輸路徑，選擇相對(duì)穩(wěn)定的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，GPSR-R在鏈路穩(wěn)定性高于一定閾值的鏈路上完成分組的轉(zhuǎn)發(fā)任務(wù)，可以有效避免GPSR算法選擇下一跳節(jié)點(diǎn)分布在節(jié)點(diǎn)通信邊緣的風(fēng)險(xiǎn)所引起的鏈路不穩(wěn)定和極易斷裂情況，因此，GPSR-R算法獲得了較高的分組交付率，但同時(shí)，由于過(guò)分注重傳輸鏈路的穩(wěn)定性，增加了分組的轉(zhuǎn)發(fā)跳數(shù)，GPSR-R算法的時(shí)延特性比GPSR差。

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

3 仿真分析

無(wú)線自組網(wǎng)中路由算法的性能主要通過(guò)分組交付率和平均端到端時(shí)延等指標(biāo)進(jìn)行評(píng)價(jià)。分組丟包率越高表明路由協(xié)議的性能越穩(wěn)定［13］；平均端到端時(shí)延越小，表明網(wǎng)絡(luò)中路由投遞的分組越快［14］。為了驗(yàn)證GPSR、GPSR-R和WF-IGPSR的網(wǎng)絡(luò)性能，利用NS-2仿真平臺(tái)，通過(guò)多次實(shí)驗(yàn)取平均值的方法獲得不同算法對(duì)應(yīng)的性能參數(shù)，并對(duì)三種算法做出客觀的、合理的評(píng)價(jià)。由于在Ad-Hoc自組網(wǎng)中，路由的性能受網(wǎng)絡(luò)中節(jié)點(diǎn)密度和移動(dòng)速度影響顯著，因此，本次實(shí)驗(yàn)分成兩部分來(lái)完成。其中，第一部分是不同節(jié)點(diǎn)密度下三種路由協(xié)議的性能對(duì)比；第二部分是不同節(jié)點(diǎn)移動(dòng)速度下三種路由協(xié)議的性能對(duì)比。實(shí)驗(yàn)主要參數(shù)設(shè)置如表1所示。

表1 實(shí)驗(yàn)參數(shù)

3.1 不同節(jié)點(diǎn)密度下的路由性能分析與評(píng)價(jià)

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

圖1 平均端到端時(shí)延與節(jié)點(diǎn)密度的關(guān)系

圖2 分組交付率與節(jié)點(diǎn)密度的關(guān)系

由圖1可知，三者的變化曲線可描述為，三種路由算法的平均端到端時(shí)延曲線隨節(jié)點(diǎn)密度增大呈現(xiàn)下降趨勢(shì)，其中，GPSR的時(shí)延最小，WF-IGPSR次之，GPSR-R時(shí)延最大。具體表現(xiàn)為當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目在20～35個(gè)范圍變化時(shí)，GPSR、WF-IGPSR和GPSR-R之間的時(shí)延差距較大，隨著節(jié)點(diǎn)數(shù)目的增多，三者的時(shí)延差距呈現(xiàn)縮小態(tài)勢(shì)，時(shí)延性能相當(dāng)。其原因在于GPSR算法采用貪婪轉(zhuǎn)發(fā)策略，能夠維持較小的時(shí)延；WF-IGPSR算法在選擇下一節(jié)點(diǎn)時(shí)，因?yàn)榭紤]了距離和方向角因素，能夠使數(shù)據(jù)分組沿著目的節(jié)點(diǎn)方向快速的轉(zhuǎn)發(fā)，但由于兼顧了傳輸鏈路的質(zhì)量，所以，WF-IGPSR算法的傳輸時(shí)延性能不如GPSR；GPSR-R算法側(cè)重傳輸鏈路的穩(wěn)定性，為了選擇可靠的下一跳節(jié)點(diǎn)，犧牲了時(shí)延特性，所以，時(shí)延特性最差。但隨著節(jié)點(diǎn)密度的增加，可供選擇的中間轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)目也隨之增加，三者之間的差距不斷縮小；當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目為50個(gè)左右時(shí)，三者的時(shí)延特性表現(xiàn)相當(dāng)，均降至50ms左右。

由圖2可知，三者的變化曲線可描述為：三種路由算法的分組交付率隨節(jié)點(diǎn)密度增大呈上升趨勢(shì)，其中，GPSR的分組交付率最低，WF-IGPSR次之，GPSR-R最高。具體表現(xiàn)為當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目在20個(gè)左右時(shí)，GPSR和WF-IGPSR算法的分組交付率只有35%左右，而GPSR-R為50%左右，相差較大；其原因是網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目較少時(shí)，GPSR和WF-IGPSR算法可供選擇的下一跳節(jié)點(diǎn)數(shù)目相對(duì)較少，選擇的分組轉(zhuǎn)發(fā)路徑質(zhì)量較差，容易斷裂，分組交付率較低；GPSR-R算法側(cè)重傳輸鏈路的穩(wěn)定性，選擇可靠的、質(zhì)量高的鏈路進(jìn)行分組轉(zhuǎn)發(fā)，分組交付率最高。隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增加，三種算法都能選擇相對(duì)穩(wěn)定的鏈路進(jìn)行分組轉(zhuǎn)發(fā)，各自對(duì)應(yīng)的分組交付率也隨之不斷升高，相互間的差距也呈現(xiàn)縮小態(tài)勢(shì)，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目為50個(gè)左右時(shí)，GPSR、WF-IGPSR和GPSR-R算法的分組交付率分別達(dá)到86%、95%和98%左右。

3.2 不同節(jié)點(diǎn)移動(dòng)速度下的路由性能分析與評(píng)價(jià)

圖3 平均端到端時(shí)延與節(jié)點(diǎn)移動(dòng)性的關(guān)系

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

圖4 分組交付率與節(jié)點(diǎn)移動(dòng)性的關(guān)系

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

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

4 結(jié)語(yǔ)

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