一種基于鏈路穩定性的最小MPR選擇算法

吳佳琪，任 智，王 磊，趙子軍

(重慶郵電大學 通信與信息工程學院，重慶 400065)

1 引 言

移動自組織網絡[1]領域的快速發展使移動節點可以形成一個自我創建，自我組織和自我管理的無線網絡.它的動態配置，靈活性，低成本以及各種吸引人的功能使其成為未來趨勢環境的重要組成部分[2].由于其缺少任何預先存在的基礎架構，節點可以自由移動到任何方向，可以與任何設備隨時通信，不受任何控制的獨立性以及其它特征是其獲得廣泛關注的關鍵[3].雖然近些年來在Ad-hoc[4,5]研究上取得一些的成果，但是MANET網絡仍然存在動態拓撲變化、鏈路帶寬資源有限、能量持續消耗、網絡不安全等一系列問題[6].

OLSR(Optimized Link State Routing)專門為自組織網絡設計，是一種主動的鏈路狀態路由協議，其體現在需要傳輸數據分組時能快速提供路由.通過要求較少的節點轉發信息來減少泛洪鏈路狀態信息的開銷，使用HELLO和TC消息來發現，然后在整個移動自組織網絡中分發鏈路狀態信息，各個節點使用此拓撲信息用最短的跳數轉發路徑為網絡中的所有節點計算下一跳[7].

為了克服由于節點快速移動引起整個網絡鏈路不穩定的問題，首先要解決的是去量化移動性，然后將其集成到路由過程中.許多研究者已經對此主題進行了研究，Loutfi A等人提出了一種與節點通信范圍附近的鏈路狀態變化有關的量化節點密度方法去選擇MPR(multipoint relays)集，不是以優先節點的覆蓋度大的節點作為MPR節點，而是選擇具有高密度鄰居的節點作為MPR節點，雖然兩者含義相差不大，但是需要去統計計算一段時間內節點局部鄰居變化情況，并沒有節點的當前覆蓋度更直觀的反響當前鄰居鏈路的連接情況，也不能保證MPR集最小[8].文獻[9]提出EMP-OLSR協議它通過記錄收到HELLO消息時的信號能量和持續時間，然后根據兩射線地面模型中的信號能量損失公式，計算出節點之間的相對距離之后，當節點發送下一個HELLO消息時，將估計該節點的位置.然后根據估計的結果，節點計算出的路由選擇更穩定可靠的轉發下一跳.文獻[10]提出了一種用于UAV Ad-hoc網絡的移動性和負載感知OLSR(MLOLSR)協議引入了移動感知算法和負載感知算法，在選擇MPR中避免選擇高速節點作為MPR，并且避免通過高速和擁塞的節點進行路由以發現更穩定的路由.Moussaoui A等人提出了一種ST_OLSR[11]協議，計算了節點相對于其鄰居的移動程度，將穩定性函數用作主要路徑選擇標準，同時在選取MPR的過程中首先選取保真度FND值最大作為MPR，在幾個節點的FND值相等的情況下，具有最大可達性的節點選為MPR.從而使MPR節點和拓撲結構更穩定，極大地減少了MPR的重新計算和路由表的重新計算過程.

文獻[12]提出了一種ADLB-OLSR協議，引入了吸收度機制和負載均衡機制去減少網絡中TC分組的數目和平衡網絡擁塞，吸收度機制中選取吸收度更高的節點作為MPR節點，但是吸收度低的節點更容易被其它節點選為MPR節點，所以并不會減少整個網絡MPR集的數量.

針對無人機的移動性帶來鏈路不穩定的問題，李燦提出了一種基于位置感知和鄰居感知的OLSR路由協議[13].該協議將節點的位置信息添加到HELLO數據包中在計算MPR集的時候通過節點的位置和鄰居改變率(NCR)的組合設置意愿值，去提高MPR節點選取的穩定性.但會增加網絡中的MPR數量，從而增大了整個網絡的控制開銷.

因此本文提出了一種鏈路穩定性考慮的最小MPR選擇算法(A Link-Stability-Based Minimum MPR Selection Algorithm，LSB-MPR)，在保證不增大網絡中MPR數量的前提條件下，通過延長了MPR節點集的有效時間，提升整個OLSR協議中節點通信的穩定性.

2 MPR選擇算法介紹與問題描述

優化鏈路狀態路由協議中MPR算法主要目的是減少TC消息洪泛開銷，其中TC消息只會在MPR節點間進行轉發，網絡中的MPR集越小，整體TC消息洪泛到全網被轉發的次數就越少.另外網絡中節點兩跳以上路由路徑計算也是通過與已有路徑相連且被選為MPR集的節點進行構建，所以MPR集穩定性也間接關系到數據分組傳遞穩定性.

2.1 MPR算法介紹

設節點N的一跳鄰居集合為M1(i)，節點的兩跳鄰居集為M2(i).MPR算法的宗旨是選取最小一跳對稱鄰居集合S中繼所有的兩跳對稱鄰居.RFC3626[7]中MPR算法的流程如下：

連接度D(y):初始一跳對稱節點覆蓋的兩跳對稱節點的數量；

步驟 1.初始化集合S為空集；

步驟 2.將N中所有意愿值為WILL_ALWAYS的節點加入到S中；

步驟 3.計算 N中所有節點的連接度D(y)；

步驟 4.將M1(i)中的節點添加到S中其中，只有通過該節點才能中繼到M2(i)的節點；從M2(i)中刪除由S中節點所覆蓋的節點.

步驟 5.若M2(i)為空，執行步驟6；否則計算M1(i)中還沒有加入到S中所有節點的覆蓋度；在覆蓋度為非0的節點中選擇N_willingness最高的節點加入到MPR集中；若意愿值相同的情況下選擇覆蓋度大的節點加入到S中；若意愿值和覆蓋度都相同的情況下，選擇D(y)更大的節點加入到MPR集中，從M2(i)中刪除由選定節點所覆蓋的節點，跳轉到步驟4.

步驟 6.若初始的兩跳鄰居中的所有節點仍由S中的至少一個節點覆蓋(不包括節點y)，并且節點y的N_Willing小于will_always則可以從S中刪除節點y.

2.2 問題描述

上述MPR選擇算法的前5步在選取最小MPR集是一個NP完全問題[14]，如果不執行第6步的優化，那么可能存在MPR節點冗余問題.針對MPR節點可能存在冗余的問題文獻[15]提出了一種基于OLSR協議的最小MPR選擇算法，該算法在每次選擇MPR節點的時候依次檢測剔除覆蓋度最低的節點看是否存在孤立的兩跳節點，若存在就說明該節點不能被剔除就將其加入到MPR集中.其實質上是將原始算法的第6步的優化工作融入到了MPR選擇之中，在理想情況下與原始算法前5步時間復雜度相同都為O(nlg(n))[16].另外，這兩種算法在選取MPR節點的過程中都會存在初始覆蓋度和當前覆蓋度都相同的節點，此時就會隨機選擇一個節點作為MPR節點，如圖1所示.

圖1 節點0選擇MPR集Fig.1 Node 0 selects the MPR set

如節點0在執行上述MPR算法選取MPR節點有兩種情況分別為：{1,2,4}、{1,3,4}.這樣就會隨機選擇一種情況，并沒有考慮節點2，3的穩定性，若節點3在鏈路的有效保持時間的下一個時刻脫離節點0，而節點0需要在節點3鏈路保持時間結束的前一個時刻計算MPR集，所以節點0在計算MPR的時候還是認為節點3沒有脫網還是雙向鏈路，若節點0選取節點3作為MPR節點，就會帶來鏈路的不穩定性.

3 LSB-MPR選擇算法

為解決上述問題，提出一種基于節點穩定性優化的最小MPR選擇算法—LSB-MPR，選擇具有更穩定鏈路的節點作為MPR.

鏈路保持時間問題在RFC3626[7]中建議了每個節點鄰居鏈路(包括一跳鄰居和兩跳鄰居)保持時間是3個HELLO消息間隔：

HEIGHB_HOLD_TIME=3×HELLO_INTEVAL=6s

(1)

刷新檢查時間為：

REFRESH_INTEVAL=HELLO_INTEVAL=2s

(2)

雖然網絡中的每個節點可以根據自己運動狀態改變HELLO消息的發射速率(鏈路的有效保持時間validity time也隨之改變)，但增大該速率會增大網絡的控制開銷，而減小該速率會造成鏈路感知遲鈍，所以選取建議的固定統一HELLO發射周期進行分析.

針對圖1中節點0在選取2、3節點作為MPR過程中的相應鏈路保持時間進行分析.

圖2為節點0針對接收到節點2和節點3的HELLO消息后保存時間的一個過程.假設在t0時刻節點收到了節點3的 HELLO消息，在t2時刻收到節點2的HELLO消息，若在t1時刻還沒有收到節點3的HELLO消息，那么已經有兩個周期還沒有收到該節點的HELLO消息了.在t2時刻，節點2的鄰居保持時間2_hold_time′=3T，節點3的鄰居保持時間3_hold_time′2T.當在時間段(t2，t4)之間任意一個時刻t3計算節點的MPR集時，兩節點當前鏈路保持時間差為：

2_hold_time-3-hold_time=
2_hold_time′-3_hold_time′>2T

圖2 節點0的時間軸Fig.2 Timeline of node 0

針對上述分析，節點0是能夠計算當前周圍一跳鄰居鏈路剩余保持時間，根據此依據定義當前鏈路穩定性評判標準為LSij(Link-Stability)表示節點i檢測與節點j的鏈路穩定性級別，分3個等級：

(3)

等級α:節點i檢測到與節點j鏈路在目前來說是危險鏈路，已經有兩個HELLO消息間隔內節點i沒有收到節點j發送過來的HELLO消息；

等級β:節點i檢測到與節點j鏈路在目前來說是潛伏鏈路，已經有一個HELLO消息間隔內節點i沒有收到節點j發送的HELLO消息；

等級γ:節點i檢測到與節點j鏈路目前來說是相對穩定鏈路，在節點j的HELLO消息間隔內已經檢查到了節點i收到節點j的HELLO消息.

定義：

γ-β=β-α=1

(4)

節點0在2、3節點之一選擇一個作為MPR節點的時候，需要計算兩條鏈路穩定性差值ΔLS(ΔLS=LS02-LS03),如表1所示.

對ΔLS≥0的情況進行討論：

I)若ΔLS=2，此時LS02=γ，LS03=α.可以推知2_hold_time-3_hold_time>2*HELLO_INTEVAL節點0收到節點2最新的HELLO消息包時間比節點3早2個周期，也就是說節點0有2個周期沒有收到節點3的HELLO消息包，如果節點0在下一個少于一個周期時間內還是沒有收到節點3的HELLO消息包后，就將該鏈路刪除.若此前節點0選擇節點3而不是節點2作為MPR節點，那么節點3就會被刪除，重新計算MPR集，此時選擇的MPR集為{1、2、4}.這一更換MPR節點的過程會使先前節點3產生包含節點0地址信息部分的TC消息失效了，而節點2的TC消息卻要添加節點0地址信息，這種改變需要重新廣播TC消息轉發到整個網絡中，從而造成網絡不穩定.如果選擇節點2作為MPR節點，那么節點0至少要等兩個以上的HELLO消息間隔沒收到才會將節點鏈路刪除，所以為了維持網絡中的MPR集穩定可以優先選擇2號節點作為MPR節點，給了整個網絡更多緩沖等待時間去判斷鏈路通斷.

表1 鏈路穩定性級別差值ΔLSTable 1 Link stability level difference ΔLS

II)若ΔLS=1，此時LS02=β，LS03=α或者LS03=β，LS02=α.可以推知2*HELLO_INTEVAL>2_hold_time-3_hold_time>HELLO_INTEVAL節點0收到節點2最新的HELLO消息包時間比節點3早一個周期，也就是說，相對于節點2來說節點0有一個周期沒有收到節點3的HELLO消息包，如果節點0在下兩個周期內還是沒有收到節點3的HELLO消息包后，就將該鏈路刪除，不參與MPR節點集的計算.這樣節點3參與MPR計算的穩定性相對于節點2來說更不穩定.

III)若ΔLS=0，此時LS03=LS02=α或者LS03=LS02=β或者LS03=LS02=γ.LS03和LS02鏈路穩定性評判等級相同，可以推知|2_hold_time-3_hold_time|

(5)

其中j為節點一跳對稱鄰居的數目，i_hold_time為與節點i的當前鏈路保持時間，NRR ∈(0,1).此時對計算MPR的節點來說，需要比較的兩個備選MPR節點初始覆蓋度和當前覆蓋度是相同的，可以推知這兩個備選節點的一跳對稱鄰居數目也肯定是相等(j值相等)，j值越大NRR值越小.

節點間通過HELLO消息的交互獲知周圍節點的鄰居保持率，同時，將HELLO數據包中Resserve保留字段更為NRR如圖3.

圖3 改進的HELLO消息格式Fig.3 Improved HELLO message format

整個LSB-MPR算法優化部分是步驟5將鏈路的保持時間影響鏈路穩定性的因素結合到算法中去，同時優化步驟6的具體實施過程，讓算法執行第優化速度更快，具體過程為：

步驟 1.初始化集合S為空集；

步驟 2.將N中所有意愿值為WILL_ALWAYS的節點加入到S中；

步驟 3.計算 N中所有節點的初始覆蓋度D(y)；

步驟 4.將M1(i)中的節點添加到S中其中，只有通過該節點才能中繼到M2(i)的節點；從M2(i)中刪除由S中節點所覆蓋的節點.

步驟 5.若M2(i)為空，執行步驟6；否則計算M1(i)中還沒有加入到S中所有節點的覆蓋度，在覆蓋度為非0的節點中選擇N_willingness最高的節點加入到MPR集中；若意愿值相同的情況下選擇覆蓋度大的節點加入到S中；若意愿值和覆蓋度都相同的情況下，選擇D(y)更大的節點加入到MPR集中，若出現了覆蓋度與初始覆蓋度D(y)相同兩個節點a,b時，執行如下操作：

計算節點i 的LSia、LSib、ΔLS=LSia-LSib；

If ΔLS==0

選NRR更大的節點；

else if

ΔLS≥1

選a節點作為MPR節點；

else

選b節點作為MPR節點；

從M2(i)中刪除由選定節點所覆蓋的節點，跳轉到步驟4.

步驟 6.依次檢測退出S中意愿值N_Willing小于will_always且D(y)最大的節點，若該節點覆蓋的兩跳鄰居能被S中的其它節點完全覆蓋，則將該節點從S中剔除.

算法步驟5的執行并沒有增大整個網絡的控制開銷，同時利用圖4對算法的步驟6優化進行說明.

節點0執行MPR算法的前5步選取的MPR節點為{d,a,b,f}，再執行第6步的時候要優化冗余節點，此時是隨機的依次檢測每個節點剔除的可能性，雖然最后都能得到最優的MPR集為{d,b,f}，但是優化的速度并不快.考慮到MPR算法在選取時候是優先選取覆蓋度高的節點作為MPR節點而沒有考慮其覆蓋的鄰居是否能完全被其它節點所覆蓋，再剔除已經覆蓋的兩條鄰居，那么接下來選擇的覆蓋度次之節點所覆蓋的兩跳鄰居中一定存在上一個覆蓋度高的節點所不能覆蓋的鄰居節點，其原因是先加入MPR集中的節點是按照覆蓋度更高，后面加入MPR集中的節點約束條件更多，其被剔除的級別相對于上一個覆蓋度高的節點來說更低，所以選取的集合S中覆蓋度更高的節點是冗余節點的概率更高，應該優先被排查，這樣可以加快MPR算法的計算時間，使其效率更高.

圖4 節點0選取MPR節點Fig.4 Node 0 selects the MPR node

4 仿真分析

選取標準OLSR路由協議中MPR選擇算法，LSB-MPR選擇算法，以及文獻[15]中OP-MPR選擇算法作為分析比較對象，通過仿真實驗分析它們之間的控制開銷、端到端時延、吞吐量、丟包率這些性能指標.

4.1 仿真參數設置

本文使用Windows XP平臺上OPENT Modeler 14.5 仿真軟件，設置了4個仿真場景.假設每個節點的發射、接收功率以及通信范圍均相同；所有節點HELLO消息和TC消息的發射周期都為固定值分別為2s和5s，N_willingness值設置為默認值3.主要考察節點不同移動速度對各性能指標的影響，其具體數值如表2所示.

表2 仿真參數設置Table 2 Simulation parameter settings

4.2 仿真結果分析

4.2.1 控制開銷

圖5表明：LSB-MPR選擇算法與另外兩種MPR算法在控制開銷上基本是相同的，原因是OP-MPR選擇算法是對標準MPR算法執行過程的改進，LSB-MPR選擇算法是對標準MPR算法的穩定性進行豐富，兩者并沒有引入新的消息類型或者控制字段，LSB-MPR選擇算法雖然修改了MPR集的選擇減少了不穩定鏈路的節點成為MPR機率，但是步驟5的執行并不會減少MPR集，而控制消息都是周期性發送，其大小并不會改變.

圖5 控制開銷對比Fig.5 Control overhead comparison

4.2.2 吞吐量

圖6表明：LSB-MPR選擇算法的吞吐量平均高出另外兩種算法0.08Mbps，雖然其并沒有減少網絡控制開銷，但是使網絡中的MPR節點鏈路更穩定，數據分組在傳送時會在整個網絡的MPR節點間轉發到達目的節點，從而間接的優化了路由的穩定性，而節點移動速度越快，整個網絡鏈路越不穩定，數據分組傳送時丟失機率更大，接收端成功接收數據更小，吞吐量下降越明顯.

圖6 吞吐量對比Fig.6 Throughput comparison

4.2.3 端到端平均時延

圖7表明：在OLSR協議中運行LSB-MPR選擇算法比運行標準MPR選擇算法、OP-MPR選擇算法的平均端到端時延低，原因是LSB-MPR選擇算法考慮了存在備選MPR節點鏈路的穩定性，選取了鏈路更穩定的節點作為MPR節點，減少了選擇不穩定MPR節點切換為穩定MPR節點的頻次，提升了鏈路局部的MPR節點穩定性.而當節點移動速度為40m/s時，系統開始出現運行不穩定了，此時運行LSB-MPR選擇算法協議的端到端時延相較來說波動較小，說明其在節點移動速度較大時效果較明顯.

圖7 端到端平均時延對比Fig.7 End-to-end average delay comparison

4.2.4 丟包率

圖8表明：LSB-MPR選擇算法丟包率較低的原因是MPR節點鏈路更穩定，數據分組傳送時丟失的概率更低，而標準MPR算法和OP-MPR算法兩者丟包率接近，OP-MPR算法是最小MPR集計算的另一種方式，與標準MPR算法的步驟6優化效果是一樣的，所以兩者丟包率接近.

圖8 丟包率對比Fig.8 Comparison of packet loss rates

5 結束語

本文針對現有OLSR路由協議中MPR算法在選取MPR節點時，對中繼節點周圍鏈路的穩定性進行了考慮，在保證不增大網絡MPR節點數量的前提下，選取網絡中更穩定的MPR節點，避免了部分不穩定MPR節點頻繁切換引起網絡路由震蕩.提出了一種基于鏈路穩定性優化的最小MPR選擇算法，通過計算鏈路穩定級別LSij根據級別差值ΔLS選取更穩定的節點加入MPR集，若穩定性級別相同則根據鄰居保持率去選擇更穩定的MPR節點，同時在原始算法上加快了剔除MPR集中冗余節點的執行過程.仿真結果表明，本文提出的算法在節點不同移動速度上使端到端時延、吞吐量、丟包率這些性能指標得到改善，提升了整個網絡的穩定性.下一步考慮不將標準MPR算法中節點當前覆蓋度作為選取MPR節點的首要依據，將節點鏈路穩定性和當前覆蓋度相結合一起作為首選依據，去在延長整個MPR集保持時間同時盡量優化該過程中照成MPR集增大的問題.