優(yōu)化鏈路狀態(tài)路由多點中繼選擇策略改進

孫友偉， 張　晶， 王辰寰

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

優(yōu)化鏈路狀態(tài)路由多點中繼選擇策略改進

孫友偉， 張晶， 王辰寰

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

摘要:對優(yōu)化鏈路狀態(tài)路由協(xié)議中多點中繼選擇策略加以改進。在求解中繼節(jié)點集時，對源節(jié)點的一跳鄰居節(jié)點中已被其他源節(jié)點選進中繼節(jié)點集的節(jié)點，視其具有較高二跳節(jié)點覆蓋數(shù)，并將其加入退出檢測隊列，以減少網(wǎng)絡中繼節(jié)點的冗余。仿真結(jié)果顯示，在節(jié)點速率為1～30 m/s時，改進策略能夠降低網(wǎng)絡時延1%～4%，減少網(wǎng)絡拓撲控制分組2%～7%。

關鍵詞:優(yōu)化鏈路狀態(tài)路由協(xié)議；貪心算法；中繼節(jié)點；局部優(yōu)化；選擇策略

作為信息技術的重要組成部分,被納入重大發(fā)展規(guī)劃的物聯(lián)網(wǎng)技術已深入到了人們?nèi)粘Ｉ畹母鱾€方面[1]：智能家庭可用電力線進行載波通信，以方便各種家用電器進行數(shù)據(jù)通信[2]；交通智能化領域則采用無線通信技術實現(xiàn)車輛間的相互連接，以實現(xiàn)汽車互聯(lián)網(wǎng)。

汽車互聯(lián)網(wǎng)是一種特殊的移動自組織網(wǎng)絡(adhoc)。移動自組織網(wǎng)絡具有自組織，無中心，多跳路由和動態(tài)拓撲的特點。優(yōu)化鏈路狀態(tài)路由(OptimizedLinkStateRouting，OLSR)是adhoc網(wǎng)絡中常用的路由協(xié)議,其關鍵概念是消息的多點轉(zhuǎn)播，主要通過選取多個中繼節(jié)點(MultiPointRelay，MPR)來代替全部的一跳節(jié)點轉(zhuǎn)發(fā)消息[3]。MPR集是在消息廣播洪泛的過程中由MPR選擇者節(jié)點挑選的轉(zhuǎn)發(fā)消息的節(jié)點集。在優(yōu)化鏈路協(xié)議中，鏈路拓撲控制信息 (TopologyControl，TC)是由MPR集中的節(jié)點產(chǎn)生的。這種機制可克服表驅(qū)動式路由協(xié)議中網(wǎng)絡維護開銷大的缺點[4]，但傳統(tǒng)優(yōu)化鏈路狀態(tài)路由中MPR集的選取使用貪心策略，而此策略并不從整體優(yōu)化上加以考慮，只是通過局部優(yōu)化來求得一種近似最優(yōu)解，不能有效減少整個網(wǎng)絡中洪泛的信息數(shù)量[5]，容易造成網(wǎng)絡堵塞。

本文給出一種全局性選擇策略(Global-MultiPointRelay,G-MPR)，以繼承貪心策略簡單高效的優(yōu)點，并綜合考慮全局優(yōu)化且無法回避各源節(jié)點之間選擇的關聯(lián)性，在符合MPR選擇準則的基礎上減小其對選取的影響，使其達到近似最優(yōu)。

1MPR集選擇準則及問題

1.1傳統(tǒng)MPR集選擇準則

傳統(tǒng)OLSR路由協(xié)議中MPR選擇策略比較簡單，其每個節(jié)點相對獨立地選擇各自的MPR集。MPR集的選取需要滿足兩個條件：首先，源節(jié)點所選取的MPR集應全部取自源節(jié)點的一跳鄰居節(jié)點。其次，選定的MPR集須覆蓋源節(jié)點的所有二跳鄰居節(jié)點。MPR選擇的問題就是在符合以上兩個條件的情況下，使得MPR集的成員節(jié)點數(shù)最少。

1.2存在的問題

傳統(tǒng)的選擇策略使用貪心策略，正是由于貪心策略僅采用一跳鄰居節(jié)點的覆蓋數(shù)作為衡量尺度，因此求解的近似解很大程度上帶有冗余，且其只針對局部求最小集，沒有做全局考慮。

關于MPR的改進大多局限于單個節(jié)點的MPR集選擇策略，并未考慮多節(jié)點的選擇情況(圖1)，要減少網(wǎng)絡中產(chǎn)生的信息分組數(shù)，必須降低整個網(wǎng)絡的MPR節(jié)點。僅僅意識到從全局考慮選擇MPR集的重要性[6]，但缺乏一種具體優(yōu)化的選擇策略，想提高MPR鏈路的穩(wěn)定性還遠遠不夠。全局選擇策略(Global_OP_MPR)[7]引入了全局因素，但策略第三步將一跳節(jié)點中已被其他源節(jié)點選為MPR節(jié)點,且轉(zhuǎn)發(fā)承載值不為0的所有節(jié)點,加入MPR集中，即源節(jié)點的一跳鄰居節(jié)點中有一些節(jié)點早已經(jīng)被默認選為MPR節(jié)點。這種選擇策略勢必造成節(jié)點間的關聯(lián)性增加，且某源節(jié)點選擇MPR節(jié)點時需要依賴其他節(jié)點所選擇的MPR節(jié)點，不做任何判斷地將其他節(jié)點所選MPR節(jié)點加入本節(jié)點的MPR集，會在很大程度上干擾原MPR選擇策略，造成整個網(wǎng)絡冗余度大幅增加。

圖1　一個自組織網(wǎng)絡的簡單拓撲

在整個網(wǎng)絡中，各源節(jié)點選取各自MPR節(jié)點時互相存在的關聯(lián)性，除過第一個選取MPR集的節(jié)點，所有的其他源節(jié)點被迫選擇一個不僅大于最小的，而且大于在不考慮其他源節(jié)點的情況下選擇的MPR集。由于現(xiàn)實網(wǎng)絡中節(jié)點眾多，這種關聯(lián)性造成的冗余可能會大幅度的增加，使網(wǎng)絡中洪泛的信息量增加[8]，從而導致信息擁塞。

2改進的選擇策略

2.1G-MPR選擇策略

在G-MPR選擇策略中，對于已被其他源節(jié)點選入MPR集的一跳鄰居節(jié)點，且其轉(zhuǎn)發(fā)承載值不為0，則默認其有高的優(yōu)先權，也加入退出判斷行列中。G-MPR選擇策略是一種能使全局網(wǎng)絡中MPR節(jié)點數(shù)達到優(yōu)化的改進策略，具體描述如下。

步驟1定義源節(jié)點i的MPR集為S。

步驟2對于一跳鄰居節(jié)點N1(i)中所有節(jié)點，計算他們各自在二跳鄰居節(jié)點N2(i)中能覆蓋的節(jié)點個數(shù)。

步驟3檢測N1(i)中所有節(jié)點，選出其中已被其他源節(jié)點選為MPR的節(jié)點,并判斷其轉(zhuǎn)發(fā)承載值是否為0，若為0則將其從N1(i)中剔除；然后分別將未被其他源節(jié)點選為MPR的節(jié)點和已被選為MPR的節(jié)點,按照每個節(jié)點在二跳鄰居節(jié)點集中的覆蓋數(shù),從小到大進行各自排序；分別將未被其他源節(jié)點選中和已被選中的兩部分，先后加入S集。

步驟4按照S集中節(jié)點的順序，將節(jié)點依次退出，每次查看N2(i)中是否還有未被S中其他任何節(jié)點覆蓋的節(jié)點，如果存在則說明該節(jié)點不能退出S，否則，將此節(jié)點退出S。

從多個源節(jié)點選取MPR節(jié)點的角度出發(fā)，考慮已被其他節(jié)點選為MPR的節(jié)點在整個網(wǎng)絡中的特殊性，將已被其他源節(jié)點選為MPR的節(jié)點集和剩余節(jié)點集分為兩部分各自排序，然后重新整合，最后執(zhí)行退出檢測策略。這種新策略給已被其他源節(jié)點選為MPR的節(jié)點賦予更高的優(yōu)先權，默認其有多的覆蓋數(shù)，既能減少整個網(wǎng)絡的MPR節(jié)點數(shù)，也能減小相關性引起的冗余。

2.2實例分析

依據(jù)改進的選擇策略，對圖1所示實例，求解整個網(wǎng)絡的MPR節(jié)點集。

假設源節(jié)點1先選取MPR節(jié)點，因此，選取不受源節(jié)點2的關聯(lián)性影響，源節(jié)點1的MPR集為

M1={2,3,4,6,7}。

源節(jié)點2的一跳鄰居節(jié)點

N1={1,6,7,8,9}。

節(jié)點6和7已被源節(jié)點1選定，且N1中的節(jié)點在二跳鄰居節(jié)點的覆蓋數(shù)分別是{3,4,2,3,2}，根據(jù)步驟3分別排序的結(jié)果是

S={9,8,1,7,6}。

依次退出，檢測是否影響其覆蓋完整性。通過測試發(fā)現(xiàn)節(jié)點7的退出不影響節(jié)點的覆蓋完整性，因此源節(jié)點2的MPR集為

M2={1,6,8,9}。

如果根據(jù)Global_OP_MPR選擇策略[7]，則在源節(jié)點2選擇MPR集時，節(jié)點7會被加入M2中且不能被剔除。

這個簡單的實例顯示，在全局網(wǎng)絡選擇MPR節(jié)點時，對已被其他節(jié)點選中的節(jié)點做退出判斷后剔除冗余節(jié)點，能減少網(wǎng)絡中消息的洪泛數(shù)量。

2.3性能分析

G-MPR選擇策略能快速選取局部優(yōu)化，減少相關性引起的冗余，從而獲得全局優(yōu)化，不會額外增加算法的時間復雜度，還能減少全局MPR集的節(jié)點數(shù)量和洪泛消息的數(shù)量。

在OLSR路由協(xié)議中，相鄰節(jié)點之間可以通過HELLO消息獲取相互的身份信息[9]。伴隨著網(wǎng)絡中節(jié)點拓撲的快速變化，MPR節(jié)點選取是一個持續(xù)過程，在網(wǎng)絡節(jié)點初始化的過程中，大部分節(jié)點都沒有獲取到是否已被其他節(jié)點選中的信息[10]。隨著選取自己的MPR集，且選取時間不同，節(jié)點將能夠檢測到已被其他節(jié)點選為MPR節(jié)點的節(jié)點，此時該選擇策略將呈現(xiàn)出全局優(yōu)化的趨勢。

OLSR路由協(xié)議通過選取中繼節(jié)點集(MPRs)來代替全部的一跳鄰居節(jié)點，實現(xiàn)消息的傳遞，被選為MPR的節(jié)點相對其他節(jié)點，會不可避免地產(chǎn)生額外傳輸負擔[11]。隨著網(wǎng)絡拓撲的變化，網(wǎng)絡中所有節(jié)點都有可能被選為MPR節(jié)點，最終，在網(wǎng)絡中的節(jié)點會基本達到負載均衡。

3仿真驗證

驗證基于G-MPR選擇策略的優(yōu)化鏈路路由 (Global-OptimizedLinkStateRouting,G-OLSR)協(xié)議在全局網(wǎng)絡中的性能。在不同場景下，對OLSR協(xié)議和G-OLSR協(xié)議在整個網(wǎng)絡中分別做時延和TC消息分組數(shù)比較。

3.1仿真環(huán)境

使用NS2.34仿真軟件，對基于G-MPR選擇策略的G-OLSR協(xié)議進行驗證。

根據(jù)汽車節(jié)點在路上的運動特性，選取平面式網(wǎng)絡結(jié)構(gòu)，MAC層使用IEEE802.11，采用Two-raygroundreflection無線傳輸模型[12]，仿真區(qū)域的范圍取為1 000m×1 000m，使用NS自帶的工具setdest生成節(jié)點隨機移動模型，網(wǎng)絡場景中有60個節(jié)點，仿真時間400s，移動模型中節(jié)點的移動速率最小為0m/s，最大分別為1m/s，5m/s，10m/s，15m/s，20m/s，25m/s和30m/s共7種[9]，節(jié)點停留時間為0s，節(jié)點的無線覆蓋半徑默認為250m，數(shù)據(jù)流的業(yè)務類型采用由NS自帶的流量生成器cbrgen工具所產(chǎn)生的CBR流，其中數(shù)據(jù)包大小為512Bytes，發(fā)送速率為10packet/s。

對各場景進行多次仿真實驗，將實驗中采集的數(shù)據(jù)求其平均值。

3.2仿真結(jié)果

移動速率和網(wǎng)絡中TC分組數(shù)量的關系如圖2所示。在7種不同移動速率下，G-OLSR相比OLSR減少了TC消息的數(shù)量，這說明G-OLSR選擇策略能有效減少全局網(wǎng)絡中MPR節(jié)點的數(shù)量，使MPR集得到優(yōu)化。

圖2　移動速率和TC分組數(shù)

移動速率和傳輸時延的關系如圖3所示。隨著節(jié)點運動速率的加快，OLSR的傳輸時延都會隨之加大，但G-OLSR因在全局網(wǎng)絡中有優(yōu)化的MPR集，能減少消息的洪泛，從而相比OLSR能減少時延。

圖3　移動速率和節(jié)點時延

4結(jié)語

文中提出的G-MPR選擇策略能有效減少各個源節(jié)點之間選取MPR節(jié)點時相互之間的相關性，從全局上優(yōu)化了MPR選擇策略，減少了網(wǎng)絡中MPR集的冗余，達到全局網(wǎng)絡中洪泛消息的減少，從而提升網(wǎng)絡的性能。使用NS進行移動多點仿真，從仿真結(jié)果可以看出G-OLSR協(xié)議能有效減少網(wǎng)絡中消息的洪泛并減小網(wǎng)絡時延提升了網(wǎng)絡性能。

參考文獻

[1]孫友偉，溫雙濤．基于電力線通信的新型物聯(lián)網(wǎng)架構(gòu)[J].西安郵電大學學報，2014,19(3):43-48 [2015-09-30].http://mall.cnki.net/magazine/article/XAYD201403010.htm.DOI:10.13682/j.issn.2095-6533.2014.03.009.

[2]王勇斌，孫友偉．基于ES0191的電力線物聯(lián)網(wǎng)控制平臺[J].西安郵電大學學報，2014,19(03):49-53[2015-09-30].http://mall.cnki.net/magazine/article/XAYD201403011.htm.DOI:10.13682/j.issn.2095-6533.2014.03.010.

[3]張洪,高楊,等．一種新型MPR集選擇算法[J].成都大學學報.2015.34(1):38-40[2015-09-30].http://mall.cnki.net/magazine/article/CDDD201501011.htm.

[4]楊彬,劉健,馮家剛.基于拓撲快速變化的OLSR改進路由協(xié)議研究[J].計算機工程與應用.2015,51(4):105-109[2015-09-30].http://mall.cnki.net/magazine/article/JSGG201504022.htm.DOI:10.3778/j.issn.1002-8331.1304-0356.

[5]PEREMontolio-Aranda,JOAQUINGarcia-Alfaro,DAVIDMegías.Improvedfloodingofbroadcastmessagesusingextendedmultipointrelaying[J].JournalofNetworkandComputerApplications. 2011.3(2):542-550[2015-09-30].http://www.sciencedirect.com/science/article/pii/S1084804510002225.DOI: 10.1016/j.jnca.2010.12.011.

[6]LEONARDOMaccari,RENATOLoCigno.HowtoreduceandstabilizeMPRsetsinOLSRnetworks[C]//ProceedingsoftheIEEE8thInternationalConferenceonWirelessandMobileComputing,NetworkingandCommunications.Piscataway:IEEE, 2012:373-380[2015-09-30].http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6379101.DOI:10.1109/WiMOB.2012.6379101.

[7]劉杰，王玲，王杉，等.基于OLSR協(xié)議的最小MPR集選擇算法[J].計算機應用，2015,35(2):305-308,339[2015-09-30].http://mall.cnki.net/magazine/article/JSJY201502004.htm.DOI:10.11772 /j.issn.1001-9081.2015.02.0305.

[8]趙健,孫俊鎖.OLSR路由協(xié)議的改進及其NS2仿真分析[J].計算機仿真.2008.25(1):161-163[2015-09-30].http://mall.cnki.net/magazine/article/JSJZ200801047.htm.

[9]陳立,楊瑞娟,戚浩,等．一種改進的高動態(tài)OLSR協(xié)議算法研究[J].無線電工程.2014,44(22):44-47,21[2015-09-30].http://mall.cnki.net/magazine/article/WXDG201412002.htm.DOI:10.3969/j.issn.1003-3106.2014.12.02.

[10] 鐘珞,趙先明,夏紅霞. 求解最小MPR集的蟻群算法與仿真[J]. 智能系統(tǒng)學報.2011(02):166-171[2015-09-30].http://mall.cnki.net/magazine/article/ZNXT201102015.htm.DOI:10.3969/j.issn.1673-4785.2011.02.012.

[11] 蘭鵬,李二濤,何桂仙. 基于改進OLSR路由協(xié)議mesh網(wǎng)絡的研究[J]. 杭州電子科技大學學報. 2013(04):54-57[2015-09-30].http://mall.cnki.net/magazine/article/HXDY201304014.htm.DOI:10.3969/j.issn.1001-9146.2013.04.014.

[12] 張繼榮,趙曉彤,等．改進的貪婪型周邊無狀態(tài)路由協(xié)議[J].西安郵電大學學報.2015(04):16-19[2015-09-30].http://mall.cnki.net/magazine/article/XAYD201504003.htm.DOI:10.13682/j.issn.2095-6533.2015.04.003.

[責任編輯:瑞金]

Animprovedmultipointrelayselectionstrategyinoptimizedlinkstaterouting

SUNYouwei,ZHANGJing,WANGChenhuan

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:An improved multipoint relay selection strategy in optimized link state routing is proposed. When solving the relay node sets, take source node’s one hop neighbor nodes, which have been drawn in relay node set by other source nodes, as that with a higher two hop node overlay number, and pull them into the exiting inspection queue to reduce the redundancy of relay nodes in the network. Simulation results show that, when the nodes move at a speed of 1～30 m/s, using the improved selection algorithm can reduce the network delay by 1%～4%, and cut down the number of network topology control group by 2%～7%.

Keywords:optimized link state routing protocol (OLSR), greedy algorithm，relay node，local optimization，selection strategy

doi:10.13682/j.issn.2095-6533.2016.02.007

收稿日期：2015-10-20

作者簡介：孫友偉(1956-)，男，教授，從事下一代通信網(wǎng)研究。E-mail: syw@xupt.edu.cn 張晶(1991-)，男，碩士研究生，研究方向為物聯(lián)網(wǎng)技術及應用。E-mail:296363682@qq.com

中圖分類號：TN913.6

文獻標識碼：A

文章編號：2095-6533(2016)02-0036-05