文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.09.003
中文引用格式： 張頡，柴繼文，王海，等. 基于無線Mesh網絡的集中式自愈路由算法研究[J].電子技術應用，2015，41(9)：14-17,28.
英文引用格式： Zhang Jie，Chai Jiwen，Wang Hai，et al. Research on centralized self-healing routing protocol for wireless mesh networks[J].Application of Electronic Technique，2015，41(9)：14-17,28.
0 引言
無線Mesh網絡是一種多跳、具有自組織和自愈特點的寬帶無線網絡結構。與傳統網絡相比，它能夠提供更大的便利性和更強的可靠性，能夠更好地適應不斷變化的網絡狀況以及提供優化的網絡性能[1，2]。
當前無線Mesh網絡路由算法尋路過程一般伴隨洪泛現象造成網絡性能下降。另外，由于無線鏈路的不穩定性使得路由的可靠性得不到保障。針對上述問題，已經有不少學者做了相關研究。文獻[3]提出一種基于最優搜索模型限制下一跳節點搜索區域的方法，抑制了網絡中的洪泛現象；文獻[4]則通過限制Hello幀的周期性廣播來達到降低路由開銷的目的。但上述兩種方法都需要獲取地理位置信息；文獻[5]中利用分級地址結構，設計了一種不需要地理位置信息的定向廣播尋路方法，但該方法過度依賴于Root節點建立的樹狀路由，魯棒性較差。在保證路由可靠性方面，多路徑路由是一種行之有效的方法[6-9]，并且，節點不相交多路徑相比于鏈路不相交多路徑在負載均衡及路由可靠性方面更有優勢[8]，但獲取節點不相交多路徑的過程通常較為復雜，并且多路徑路由的質量得不到保障。
集中式路由[10]是人們在控制與轉發分離的基礎上提出的一種新的路由方法，目前的研究主要集中在IP網絡，針對無線Mesh網絡的研究較少。文獻[11]中提出一種由網關節點為網內通信連接計算最優路的路由算法RDR(Root Driven Routing)，但到網關節點的路由仍然采用廣播方式建立，并且由網關節點計算最優路的方式進一步加重了網關節點的負擔，其性能并不理想。本文引入集中式路由的思想，設計了一種由Root節點為任意節點對之間計算最優路及備份路的路由算法CSRP，該算法在尋路和自愈過程不存在洪泛現象，另外，加入Root節點動態切換機制以提高網絡的穩定性。
1 網絡模型及研究思路
1.1 網絡模型
假設網絡中各節點隨機分布在一個矩形區域內，并且具有如下性質：(1)網絡內網關節點和Root節點唯一。(2)節點靜止或具有弱移動性。(3)每個節點有惟一的標識。(4)所有節點平等，具有相同的計算、通信能力。
節點運動均遵循運動模型(Random Way Point，RWP)[12]，該模型可以描述為：節點在運動空間A內隨機選取目的點D，隨機選取v作為此次運動的速度，其速率在(vmin，vmax)范圍內選取，勻速從起始點S沿直線運動到D，并以時間PauseTime保持靜止，這樣完成一次運動過程，如此重復。
1.2 研究思路
現有無線Mesh網絡路由算法一般采用分布式的路由方式，這種分布式的路由方式保證了網絡的可靠性，然而卻導致了尋路洪泛等問題。尤其在網絡負荷較重的場景下，進一步加重了網絡的負擔，嚴重影響網絡的性能。
集中式路由是一種由路由控制平臺統一計算路由信息的路由方法，各節點負責收集拓撲信息并且向路由控制平臺通告，路由控制平臺根據當前網絡拓撲使用Dijkstra算法為節點間計算路由，節點根據計算的路由消息轉發報文。在集中式路由方法中各節點不再具備尋路能力，因此需要預先構建一種具備保護功能的路由機制，使得節點的路徑失效后都有立即可用的備份路徑。
多路徑路由通過路徑信息的冗余性來保證主路由失效后分組傳輸的有效性。多路徑通常分為節點不相交多路徑和鏈路不相交多路徑，如圖1所示，但節點不相交多路徑策略能夠保證備份路由和主路由具有最大不相關性，更能保證路由的可靠性。
因此，在CSRP路由算法中由Root節點(路由控制平臺)匯聚全網拓撲，為源目節點間計算路由，并結合節點不相交多路徑策略提升網絡的性能。
2 CSRP路由算法
CSRP路由算法分為鏈路狀態信息上傳、路徑選擇及分組轉發、路由自愈3個階段，下面分別加以介紹。
2.1 鏈路狀態消息上傳
各節點在建立起到Root節點的路由后會首先將與各鄰居節點之間的鏈路狀態信息(包含鄰居地址列表及其對應的鏈路質量度量值)發送給Root節點，Root節點以此掌握全網拓撲信息。
另外，各節點每隔QueryInterval查詢一次鄰接鏈路的鏈路狀態，在式(1)和式(2)兩個條件任意一個滿足時向Root節點上傳鏈路狀態信息。
NeighborListnow?鄞=NeighborListlast(1)
即節點的鄰居節點發生變化。例如，有新的節點與當前節點建立鄰居關系或者某個鄰居節點拆除了與當前節點的鄰居關系。
Dmetric1>MetricThreshold(2)
即節點與某個鄰居節點I間的鏈路累計變化值大于閾值。
另外，各節點如果連續次查詢鏈路狀態未滿足式(1)和式(2)上傳條件，仍上傳鏈路狀態消息以探測根路由的有效性。
Root節點收到鏈路狀態信息后，會更新全網拓撲信息。另外，各節點上傳的鏈路狀態信息通過ACK確認機制來確保上傳成功，如果一次傳輸未成功，則在QueryInterval時間后再次上傳。
2.2 路徑選擇及分組轉發流程
當要發送分組時，節點首先查詢路由表項中是否有到達目的節點的路由信息。如果有，按照當前路由信息直接發送至目的節點；如果沒有，查詢是否有到達Root節點的路由信息。
如果不存在到Root節點的路由，則需要首先請求到Root節點的路由，在此過程中使用序列號機制保證任何時候節點間都無環路。每個節點都保持著自己的一個序列號，這個序列號通過PREQ被發送到其他節點，其他節點只處理序列號更大的PREQ。請求到Root節點路由的具體步驟如下：
步驟(1)：向所有鄰居節點發送路由查詢幀。
步驟(2)：鄰居節點收到路由查詢幀后查看自身根路由是否有效，如果有效，回復有效確認幀，否則回復無效確認幀。
步驟(3)：如果節點接收到有效確認幀，則從回復有效確認幀的鄰居節點中隨機選取一個節點向其發送路由請求幀PREQ。
步驟(4)：如果沒有收到有效確認幀，向其所有鄰居節點發送路徑請求幀PREQ。
步驟(5)：節點收到PREQ后，首先檢查PREQ是否包含了一個更大的序列號，如果不是，丟棄該幀。如果是，再檢查根路由有效，如果有效，上傳PREQ至Root節點，否則，重復步驟(1)~(4)。
步驟(6)：Root節點收到PREQ。
Root節點收到序列號更大的PREQ后，計算源節點到Root節點的最優路及節點不相交的備份路，分別將最優路和備份路封裝成PNTF幀，并沿各自路徑發送到源節點，中間節點及源節點建立路由。
如果源節點存在根路由信息，將分組Mesh幀頭中PathReq字段置1，表示請求源節點到目的節點的路由。如果傳輸采用根路由的備份路由，需要將Mesh幀頭中IsSparePath字段也置1，表示需要重新請求源節點到Root節點的路由，然后將分組發送到Root節點。
Root節點接收到分組后的處理流程如下：
1Root節點接收到一個分組；
2if (dst_address == m_address) 處理該分組；
3else 將分組轉發到目的節點；
4查看Mesh幀頭中的路由請求PathReq標記；
5if (PathReq==1)
{
6計算源節點到目的節點的最優路；
7將最優路徑封裝成路徑消息幀(Path Information
PIFM)發送到源節點；
8源節點接收到PIFM幀后解析得到最優路徑；
9源節點將最優路徑封裝成PNTF幀，并沿最優路徑
發送到目的節點；
10中間節點建立到源目節點的路由；
11目的節點建立到源節點的路由；
}
12查看Mesh幀頭中的備份路徑IsSparePath標記；
13if (IsSparePath==1)
{
14計算源節點到Root節點的最優路及節點不相交的
備份路；
15分別將最優路和備份路封裝成PNTF幀，并沿各自
路徑發送到源節點；
16中間節點建立到源節點及Root節點的路由；
17源節點更新到Root節點的最優路由和備份路由；
}
2.3 路由自愈流程
在CSRP算法中，各節點到Root節點的路由采用節點不相交的備份路進行備份，而到其他節點的路由采用根路由進行備份。下面以圖例的方式詳細說明利用備份鏈路進行自愈的流程。
根路由失效后的自愈過程如圖2所示。以節點I為例，到根節點的主路由為I-F-D-A-R，備份路由為I-G-B-R。某一時刻，F探測到F-D鏈路發生失效后，會立刻通過自身的根路由F-G-B-R發送鏈路失效報文LinkPerr給Root節點，并向源節點I返回PERR錯誤報文，Root節點收到LinkPerr失效報文后，從全網拓撲中刪除失效鏈路，隨后F將緩存在本地的分組通過F-G-B-R發送至R，I在收到PERR錯誤報文后，會刪除本地路由表中的最優路由，將需要發送的分組切換至備份路I-G-B-R繼續傳輸，并在Mesh幀頭中標記為使用備份路發送。當分組到達Root節點時，Root節點查詢到數據是由備份路由傳輸到達，會計算Root節點R到I的當前全局最優路由和備份路由，并將計算結果通過PNTF報文發送到I，I在收到PNTF報文后，會更新本地的最優路由和備份路由，后續分組通過當前的最優路由I-G-B-R為傳輸。
對于到網內其他節點路由的自愈流程如圖3所示，源節點為F，目的節點為H，最優路由為F-G-H。G探測到鏈路G-H失效后，會立即返回PERR給源節點F，并利用本地的根路由(主路由或備份路由)將鏈路失效報文LinkPerr和數據幀發送至Root節點，Root節點收到LinkPerr報文后，從全網拓撲中刪除失效鏈路，并將接收到數據幀后轉發到目的節點H。源節點收到PERR錯誤報文后，刪除失效路由表項，將后續數據利用根路由(主路由或備份路由)發送，并在Mesh幀頭中設置路由請求標記，Root節點接收到數據幀后重新計算F和H間的當前最優路由，并將其通過路徑消息報文PIFM發送至源節點F。F收到解析PIFM后得到最優路徑，并將最優路徑封裝成PNTF幀，向目的節點H發送PNTF路由通告消息，中間節點和目的節點建立路由，后續數據將通過新建立最優路由傳輸。
3 仿真及結果分析
為了驗證CSRP路由算法的有效性，仿真實驗中將時延、包遞交率和路由開銷(定義路由開銷為路由協議分組字節總和占網絡傳輸數據字節總和的比例)作為評價指標，對不同網絡負荷、鏈路失效場景下CSRP、HWMP和RDR的網絡性能仿真結果進行比較和分析。仿真軟件為NS-3[13]，仿真參數如表1所示，節點隨機均勻分布在網絡覆蓋范圍內，網關節點位于網絡覆蓋區域的左上角，Root節點初始時刻位于網絡的中心。仿真結果均為統計30次取平均的結果。
3.1 不同網絡負荷下的性能仿真
圖4為不同負荷場景下CSRP與HWMP[14]、RDR[11]的性能仿真。
3.2 自愈性能仿真
在本小節對比了路由失效場景下CSRP與HWMP、RDR的性能。通信連接數為20，節點移動速率為0~5 m/s之間的隨機值，通過設置不同的PauseTime值來模擬網絡拓撲變化的劇烈程度。圖5中的仿真結果表明：在時延和包遞交率方面，節點的移動性越強(PauseTime越小)，CSRP算法相比HWMP、RDR性能提升越明顯。這是因為CSRP采用多路徑備份策略，當路由失效后可以切換到備用路由進行分組傳輸，確保時效路由的快速恢復及分組的最小損失。在路由開銷方面，如圖5(c)，對于HWMP，其路由開銷主要來源于Root節點的周期性廣播和節點的尋路廣播，鏈路越不穩定，重新廣播尋路越頻繁，路由開銷越大。而對于RDR，隨著鏈路逐漸穩定，鏈路狀態消息上傳越少，路由開銷越小。對于CSRP，其路由開銷主要來源于鏈路狀態消息的上傳，其路由開銷最小，比HWMP和RDR路由開銷至少降低67%。
4 結束語
該文將集中式路由方法用于無線Mesh網絡，提出了一種集中式自愈路由算法CSRP，在該算法中各節點匯聚鏈路狀態消息至Root節點，由Root節點集中計算最佳路由。相比于傳統路由算法的洪泛尋路機制，該算法在很大程度上降低了路由開銷。另外，該算法采用多路徑備份策略及Root節點切換機制保證路由的可靠性。通過仿真表明，CSRP路由算法較HWMP、RDR路由算法在不同仿真場景下都有明顯改善，路由開銷至少降低67%，時延平均降低45%，包遞交率平均提升8%。在未來的工作中，考慮在網絡中加入多個路由控制平臺(Root節點)，各路由控制平臺之間相互備份，以進一步增加網絡的魯棒性。
參考文獻
[1] BENYAMINA D，HAFID A，GENDREAU M.Wireless mesh networks design-A survey[J].Communications Surveys & Tutorials，2011，14(2)：299-310.
[2] AKYILDIZ I，WANG X D.A survey on wireless mesh net-works[J].Communications Magazine，IEEE，2005，43(9)：S23-S30.
[3] 秦丹陽，馬琳，沙學軍，等.移動Ad Hoc網絡中路由自愈的實現[J].哈爾濱工業大學學報，2010，42(1)：46-50.
[4] DONG P，QIAN H Y，WEI X F，et al.Beacon-less geo-graphic multipath routing protocol for ad hoc networks[J].Mobile Networks and Applications，2013，18(4)：500-512.
[5] KIM S，CHONG P，KIM D.A location-free semi-direction-al-flooding technique for on-demand routing in low-rate wireless mesh networks[J].IEEE Transactions on Parallel and Distributed Systems，2014，PP(99)：1-11.
[6] TARIQUE M，TEPE K E，ADIBI S，et al.Survey of multi-path routing protocols for mobile ad hoc networks[J].Journalof Network and Computer Applications，2009，32(6)：1125-1143.
[7] 郝曉辰，賈楠，劉彬.基于擁塞預知的WSN多徑尋優路由協議[J].電子與信息學報，2011，33(5)：1261-1265.
[8] LAL C，LAXMI V，GAUR M S.A node-disjoint multipath routing method based on AODV protocol for MANETs[C].26th IEEE International Conference on Advanced InformationNetworking and Applications，Fukuoka，2012：399-405.
[9] OBAIDAT M，ALI M，SHAHWAN I，et al.QoS-aware mul-tipath communications over MANETs[J].Journal of Networks，2013，8(1)：26-36.
[10] 譚晶，羅軍舟，李偉.一種適合低連接度拓撲的集中式保護路由機制[J].軟件學報，2013，24(3)：575-592.
[11] LIM A O，WANG X D，KADO Y，et al.A hybrid central-ized routing protocol for 802.11s WMNs[J].Mobile Net-works and Applications，2008，13(1-2)：117-131.
[12] MUHAMMAD A，ROBERT S.Simulation study of common mobility models for opportunistic networks[C].Simulation Symposium，ANSS 2008，41st Annual，Ottawa，2008：43-50.
[13] IKEDA M，ODA T，KULLA E，et al.Performance evaluationof WMN considering number of connections using ns-3 simulator[C].The Third International Workshop on Methods，Analysis and Protocols for Wireless Communication，Victo-ria，2012：498-502.
[14] BARI S M S，ANWAR F，MASUD M H.Performance of hybrid wireless mesh protocol(HWMP) for IEEE 802.11s WLAN mesh networks[C].IEEE International Conference on Computer and Communication Engineering，Kuala Lumpur，2012：712-716.