雷宏江，鄧 科，鄭 淵，任 智

(重慶郵電大學移動通信技術(shù)重慶市重點實驗室，重慶 400065)

0 引言

無線個域網(wǎng)(wireless personal area network，WPAN)是一種能使便攜式家用電子產(chǎn)品和通信設(shè)備以 Ad Hoc 方式組網(wǎng)工作的無線網(wǎng)絡(luò)［1－2］，WPAN Mesh網(wǎng)絡(luò)在不增加無線接入點的基礎(chǔ)上，利用WMN(wirelessmesh network)網(wǎng)絡(luò)的組網(wǎng)方式完成了網(wǎng)絡(luò)連接。在WPAN Mesh網(wǎng)絡(luò)中，網(wǎng)狀網(wǎng)的組網(wǎng)方式不僅增大了網(wǎng)絡(luò)的覆蓋范圍，而且還增加了網(wǎng)絡(luò)的吞吐量，提高了數(shù)據(jù)傳輸?shù)目煽啃裕?－4］。

目前，WPAN Mesh網(wǎng)絡(luò)的路由協(xié)議主要都是基于mesh樹路由協(xié)議的改進。文獻［5］以IEEE802.15.5標準低速WPAN中的網(wǎng)狀自適應(yīng)樹(meshed adaptive tree，MAT)為基礎(chǔ)，將MAT劃分為2層結(jié)構(gòu)，且在劃分后的2層結(jié)構(gòu)采用不同的路由算法，提出了分級路由算法。但是，該路由算法由于采用傳統(tǒng)的無線自組網(wǎng)按需平面距離矢量路由協(xié)議(ad hoc on－demand distance vector routing，AODV)［6］，從而存在由泛洪引起的過多控制開銷、消耗大量網(wǎng)絡(luò)資源等問題。文獻［7］中以MAT為基礎(chǔ)，將MAT和 AODV 結(jié)合，提出了 TLMR(two－level mesh routing)路由算法。即先在MAT中查詢有效路徑，如果不存在有效路由，則采用AODV。該路由算法同樣存在AODV的缺點。文獻［8］提出了一種基于樹的先驗式路由協(xié)議，在該協(xié)議中路由不是統(tǒng)一在根節(jié)點進行計算，而是分散到各個枝干上的節(jié)點進行分布式計算，該算法能夠有效地避免在根節(jié)點處出現(xiàn)擁塞現(xiàn)象，但是該算法仍然會引起過多的控制開銷。文獻［9］提出了一種基于拓撲服務(wù)器的高效率低時延的尋路算法，但沒有考慮到基于拓撲服務(wù)器的路由(server routing，SR)算法在路由修復操作上存在冗余控制開銷和操作。

1 基于拓撲服務(wù)器的路由算法

基于拓撲服務(wù)器的路由算法［1，8］是針對高速WPAN Mesh網(wǎng)絡(luò)拓撲結(jié)構(gòu)特點和網(wǎng)絡(luò)中節(jié)點特性而設(shè)計的路由協(xié)議。其主要思想是源節(jié)點通過訪問距離源和目的節(jié)點最近的公共父節(jié)點來獲得到達目的節(jié)點的最優(yōu)路徑。

SR算法路由建立過程如圖1所示，由源節(jié)點(Src節(jié)點)向目的節(jié)點(Dest節(jié)點)傳送數(shù)據(jù)。根據(jù)基于拓撲服務(wù)器的路由算法原理，Src節(jié)點通過向它們的公共父節(jié)點MC發(fā)送Route Discovery消息請求最優(yōu)路徑信息，在MC節(jié)點計算完最優(yōu)路徑后，將發(fā)送捎帶有該最優(yōu)路徑信息的Route Notification消息給Dest節(jié)點，Dest節(jié)點再根據(jù)最優(yōu)路徑信息轉(zhuǎn)發(fā)Route Formation消息給Src節(jié)點，最后，Src節(jié)點將沿著最優(yōu)路徑傳送數(shù)據(jù)。

圖1 SR算法路由建立過程Fig.1 Process of SR routing establishment

當有鏈路失效時，節(jié)點發(fā)送Route Error消息通知源節(jié)點，并由源節(jié)點轉(zhuǎn)發(fā)Route Error消息給公共父節(jié)點，如圖2所示。當公共父節(jié)點收到Route Error消息后，重新計算被失效鏈路所影響的源和目的節(jié)點之間的最優(yōu)路徑，之后的路由修復過程與最優(yōu)路徑建立過程相同。

SR路由修復過程中存在以下問題。

1 )基于SR算法在轉(zhuǎn)發(fā)Route Error消息時是先轉(zhuǎn)發(fā)給源節(jié)點，然后轉(zhuǎn)發(fā)給公共父節(jié)點，沒有實際考慮當前探測到鏈路失效節(jié)點到公共父節(jié)點的距離是否比源節(jié)點到公共父節(jié)點的距離近。圖2中的G節(jié)點要比Src節(jié)點離公共父節(jié)點MC更近一些，在此，可能存在冗余的Route Error控制消息。

2 )基于SR算法由于Route Error消息的轉(zhuǎn)發(fā)路徑不是最優(yōu)的，使得路由修復過程存在明顯的時延。

本文針對以上缺點提出了一種自適應(yīng)快速路由修復算法(self－adaptive and fast route recovery algorithm，SFRR)。

圖2 SR算法路由修復過程Fig.2 Process of SR routing recovery

2 SFRR算法

SFRR算法包含2種新機制:捎帶式發(fā)布源節(jié)點信息機制和自適應(yīng)選擇路由修復過程機制。新機制的采用使SFRR路由算法比原始基于SR算法減少了不必要的控制開銷，并加快了路由修復過程。

2.1 捎帶式發(fā)布源節(jié)點信息機制

在最優(yōu)路徑建立階段中，在公共父節(jié)點計算完最優(yōu)路徑時，將會發(fā)送裝有最優(yōu)路徑信息的Route Notification消息到目的節(jié)點，此時，在Route Notification消息中增加源節(jié)點信息域，用來存放跳數(shù)信息，并將該信息傳遞給目的節(jié)點。目的節(jié)點再將跳數(shù)信息裝入到Route Formation消息中的新增源節(jié)點信息域，同時轉(zhuǎn)發(fā)給中繼節(jié)點，中繼節(jié)點收到更改后的Route Formation消息后保存源節(jié)點信息域中所存的跳數(shù)信息。新機制的采用使得中繼節(jié)點能夠直接知道源節(jié)點跳數(shù)信息，為后續(xù)路由修復做鋪墊，同時刪除了“長度”和“路徑控制開銷類型”2個不必要的字節(jié)域，總體上減小了控制開銷。更改后的Route Notification消息格式和更改后的Route Formation消息格式如圖3和圖4所示。

圖3 更改后的Route Notification控制消息格式Fig.3 Corrected Route Notification controlmessage style

圖4 更改后的Route Formation控制消息格式Fig.4 Corrected Route Formation controlmessage style

2.2 自適應(yīng)選擇路由修復過程機制

在采用捎帶式發(fā)布源節(jié)點信息新機制的前提下，當節(jié)點檢測到鏈路失效時，本節(jié)點判斷并找到源節(jié)點和鄰居節(jié)點集中距離公共父節(jié)點最短的節(jié)點，并將沿著該節(jié)點轉(zhuǎn)發(fā)Route Error控制消息給公共父節(jié)點。新機制在完成Route Error控制消息向源節(jié)點和公共父節(jié)點轉(zhuǎn)發(fā)操作的同時，減少了控制開銷。同時為了區(qū)分是否采用本機制，借助Route Error控制消息中的“長度”域的值(該值為7字節(jié)固定值，用于表征Route Error控制消息長度)，當采用了本機制，長度值就會增加 1;否則長度值不變，即沒有采用本機制。

2.3 SFRR路由算法具體過程

SFRR路由算法建立過程和數(shù)據(jù)傳輸過程與基于拓撲服務(wù)器的路由算法一致。其鏈路修復過程如下。

步驟1 當節(jié)點檢測到鏈路失效(鏈路斷開、容量低、電量低等)時，節(jié)點根據(jù)已知的源節(jié)點和鄰居節(jié)點集信息(到公共父節(jié)點距離，用跳數(shù)表示)選擇距離公共父節(jié)點最近的節(jié)點(當源節(jié)點和鄰居節(jié)點距離公共父節(jié)點相同時，選擇鄰居節(jié)點，因為鄰居節(jié)點能較早地將Route Error消息通知給公共父節(jié)點，并由公共父節(jié)點進行后續(xù)最優(yōu)路徑的計算)。

步驟2 當節(jié)點收到Route Error消息后，判斷“長度”域的值:①為固定值“7”時，表明收到原始的Route Error消息，則直接轉(zhuǎn)發(fā)給下一跳;②為固定值“8”時，表明收到更改后的Route Error消息，當前節(jié)點若不為源節(jié)點則直接轉(zhuǎn)發(fā)給下一跳。

步驟3 當源節(jié)點收到Route Error消息后或更改后的Route Error消息，判斷“長度”域的值，若為固定值“7”時，則在修改幀頭值后沿著樹結(jié)構(gòu)轉(zhuǎn)發(fā)給公共父節(jié)點;若為固定值“8”時，則銷毀該Route Error消息，停止地轉(zhuǎn)發(fā)。

步驟4 當公共父節(jié)點收到Route Error消息或更改后的Route Error消息時，則根據(jù)消息中錯誤信息重新計算受失效鏈路影響的源和目的節(jié)點對之間的最優(yōu)路徑，之后的最優(yōu)路徑通知、最優(yōu)路徑形成以及數(shù)據(jù)的傳輸與SR路由算法的路由建立過程一致。

根據(jù)以上4個步驟得出最優(yōu)Route Error消息的轉(zhuǎn)發(fā)路徑如圖5所示。由此可見，SFRR路由算法省去了冗余的Route Error消息。

圖5 SFRR路由修復算法Fig.5 SFRR route recovery algorithm

2.4 計算復雜度

為了驗證所提算法的效率，本文從時間復雜度、存儲復雜度和通信復雜度3個方面比較SR算法和SFRR算法的計算復雜度。

2.4.1 時間復雜度

設(shè)節(jié)點平均度為D，節(jié)點最大深度為M，則網(wǎng)絡(luò)直徑為2M。根據(jù)數(shù)據(jù)傳輸?shù)姆绞娇芍?，?shù)據(jù)在相鄰節(jié)點間傳送的時間與D正相關(guān);則SR算法的時間復雜度為o(D(2M+M+M+2M))，即 o(6DM)。設(shè)SFRR算法找到通往MC節(jié)點捷徑的概率為p，顯然，0＜p＜1，則SFRR算法的時間復雜度為o(D((2M+M)(1－p)+Mp+M+2M))，即 o(D(6M －2Mp))。顯然，o(D(6M－2Mp))＜o(6DM)，即SFRR算法的時間復雜度更低。

2.4.2 存儲復雜度

SR算法中占用節(jié)點較大存儲空間的是到達全網(wǎng)其他節(jié)點的路由信息，因此，它的存儲復雜度為O(N)，其中，N是網(wǎng)絡(luò)中節(jié)點個數(shù);SFRR算法中節(jié)點主要存儲路由信息，因此，SFRR算法的存儲復雜度也是由網(wǎng)絡(luò)中節(jié)點個數(shù)決定，為O(N)，即SFRR算法和SR算法的存儲復雜度相同。

2.4.3 通信復雜度

設(shè)節(jié)點最大深度為M，則網(wǎng)絡(luò)直徑為2M。根據(jù)Route Error轉(zhuǎn)發(fā)方式可知，其轉(zhuǎn)發(fā)次數(shù)與深度M正相關(guān);則SR算法的通信復雜度為o(2M+M+M+2M)，即o(6M)。設(shè)SFRR算法找到通往MC捷徑的概率為p，顯然，0＜p＜1，則SFRR算法的通信復雜度為o((2M+M)(1－p)+Mp+M+2M))，即o(6M－2Mp)。顯然，o(6M －2Mp)＜o(6M)，即SFRR算法通信復雜度更低。

3 仿真結(jié)果及性能分析

3.1 仿真場景設(shè)置

為了驗證所提算法的性能，在網(wǎng)絡(luò)仿真器OPNET［10－11］上將 SFRR 算法和傳統(tǒng)的 SR 算法進行了性能比較。整個網(wǎng)絡(luò)中每個節(jié)點隨機選擇非本節(jié)點作為自己的目的節(jié)點，并按照均值為5的指數(shù)分布發(fā)送長度為 116 Byte［1，12］的數(shù)據(jù)分組，仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameters set

3.2 統(tǒng)計量定義

本文統(tǒng)計了平均端到端時延，網(wǎng)絡(luò)開銷，路由修復平均時間3個性能指標。其中，平均端到端時延、網(wǎng)絡(luò)開銷的定義詳見文獻［9］。路由修復平均時間定義為當整個網(wǎng)絡(luò)中有鏈路失效時，節(jié)點從發(fā)送Route Error消息起到公共父節(jié)點收到Route Error消息為止的時間差之和除以失效鏈路，計算公式為

(1)式中:Treci表示網(wǎng)絡(luò)中節(jié)點(公共父節(jié)點)第i次收到Route Error消息的時刻;Tsendi表示檢測到鏈路斷開的節(jié)點第i次發(fā)送Route Error消息的時刻;N為失效鏈路數(shù)。該統(tǒng)計量能很好地表明改進后的算法能更快速進入重新計算最優(yōu)路徑的過程，縮短路由修復過程的時間。

3.3 仿真結(jié)果及分析

3.3.1 路由修復平均時間

在網(wǎng)絡(luò)節(jié)點數(shù)不同的情況下，SFRR算法和SR算法路由平均修復時間的比較如圖6所示。由圖6可見，與SR算法相比，SFRR算法具有更小的路由修復平均時間。這是由于SFRR算法在轉(zhuǎn)發(fā)Route Error消息的時候選擇了更優(yōu)的路徑，從而縮短了路由修復時間。

3.3.2 平均端到端時延

在網(wǎng)絡(luò)節(jié)點不同的情況下，SFRR算法和SR算法在平均端到端時延方面的比較如圖7所示。由圖7可見，與SR路由算法相比，SFRR算法具有更小的平均端到端時延，這是因為SFRR算法能快速地進入最優(yōu)路徑重新建立階段，使得數(shù)據(jù)包能夠及時地到達目的節(jié)點，縮短了時延。

圖6 路由修復平均時間Fig.6 Route recovery average time

圖7 平均端到端時延Fig.7 Average end－to－end delay

3.3.3 網(wǎng)絡(luò)開銷

在網(wǎng)絡(luò)節(jié)點不同情況下，SFRR算法和SR算法在網(wǎng)絡(luò)開銷上的比較如圖8所示。由圖8可見，在網(wǎng)絡(luò)開銷方面，SFRR算法在各個仿真場景上都比SR算法低。這主要是因為SFRR中Route Notification和Route Formation控制包長度的減小以及最優(yōu)路徑的選擇會導致控制包轉(zhuǎn)發(fā)次數(shù)減少的原因。

4 結(jié)束語

本文針對IEEE 802.15.5標準中高速部分的SR算法在路由修復部分存在冗余開銷和操作的問題，提出了SFRR路由算法，通過捎帶式發(fā)布源節(jié)點信息、自適應(yīng)選擇路由修復機制解決了SR算法存在的問題。理論分析和仿真結(jié)果表明，SFRR算法相對于SR算法，在路由修復平均時間、網(wǎng)絡(luò)開銷、平均端到端時延性能上具有更好的表現(xiàn)。

圖8 網(wǎng)絡(luò)開銷Fig.8 Network overhead

［1］LAN/WAN Standards Committee of the IEEE Computer Society.IEEE Std.802.15.5－2009，part 15.5:mesh topology capability in wireless personal area networks(WPANs)［S］.New York:IEEE Press，2009.

［2］雷震洲.高速率無線個域網(wǎng)(WPAN)［J］.電信科學，2002，18(6):5－7.

LEIZhenzhou.The High－rate Wireless Personal Area Networks［J］.Telecommunications Science，2002，18(6):5－7.

［3］LEE Myung，ZHANG Rui，ZHU Chunhui.Meshing Wireless Personal Area Networks:Introducing IEEE 802.15.5［J］.IEEECommunications Magazine，2010，48(1):54－61.

［4］史曉晨，劉凱明，高錦春，等.無線個域網(wǎng)mesh網(wǎng)絡(luò)標準——IEEE 802.15.5［J］.計算機應(yīng)用研究，2011，28(1):243－246.

SHIXiaochen，LIU Kaiming，GAO Jinchun，et al.Standard of Mesh Wireless Personal Area Network ——IEEE 802.15.5 ［J］.Application Research of Computers，2011，28(1):243－246.

［5］江禹生，何芳.改進的WPAN網(wǎng)狀自適應(yīng)樹路由算法［J］.重慶大學學報，2010，33(4):88－91，97.

JIANG Yusheng，HE Fang.Improved WPAN Meshed A－daptive Tree Routing Algorithm［J］.Journal of Chongqing University，2010，33(4):88－91，97.

［6］CHAKERES I D，KLEIN B L.AODV simplified［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2002，6(3):100－101.

［7］江禹生，何芳，宋香麗.改進的WPAN mesh路由協(xié)議［J］.計算機工程與應(yīng)用，2011，47(9):109－111.

JIANG Yusheng，HE Fang，SONG Chunli.Improved WPAN Mesh Routing Protocol［J］.Computer Engine－ ering and Application，2011，47(9):109－111.

［8］JIW J，MA J F，MA Z，et al.Tree－Based Proactive Routing Protocol forWireless Mesh Network［J］.China Communications，2012，1:25－33.

［9］REN Z，WANG K，LEIH，et al.An Effective Low－Delay Server Routing Algorithm in WPAN Meshes［C］//2012 Second International Conference on Business Computing and Global Informatization. Shanghai:IEEE Press，2012:611－614.

［10］李馨.OPNETModeler網(wǎng)絡(luò)建模與仿真［M］.西安:西安電子科技大學出版，2006:148－218.

LIXin.OPNETModeler Network Simulation［M］.Xian:Xidian University Press，2006:148－218.

［11］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.北京:清華大學出版社，2004:51－97.CHEN Min.OPNET Network Simulation［M］.Beijing:Tsinghua University Press，2004:51－97.

［12］EUNCHANG C，JAEDOO H，KWANGSIK K，et al.Selection of Serving PNCs Based on Measured FER within IEEE 802.15.5Wireless Mesh Network［C］//2007 International Conference on Convergence Information Technology.Gyeongju:IEEE Press，2007:2130－2135.

(編輯:劉 勇)