雷宏江，汪坤露，高 潮，任 智

(1.重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶 400065;2.重慶大學(xué)光電技術(shù)及系統(tǒng)教育部重點實驗室，重慶 400044)

0 引言

無線個域網(wǎng)(wireless personal area network，WPAN)是一種能使便攜式家用電子產(chǎn)品和通信設(shè)備以Ad hoc方式組網(wǎng)工作的無線網(wǎng)絡(luò)［1-2］，根據(jù)應(yīng)用場合的不同可分為高速WPAN和低速WPAN。其中，高速WPAN具有支持11～55 Mbit/s的數(shù)據(jù)傳輸速率、便于加入或離開網(wǎng)絡(luò)等特點。在WPAN中使用Mesh結(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)連接［3］，構(gòu)成了WPAN Mesh(無線個域網(wǎng)狀網(wǎng))，可以在保持WPAN特點的基礎(chǔ)上彌補其存在的帶寬較窄、覆蓋范圍小等不足，并具有以下優(yōu)點:不需要增加發(fā)射功率或提高接收靈敏度就可擴(kuò)展網(wǎng)絡(luò)的覆蓋范圍;能夠通過冗余路由增加數(shù)據(jù)傳遞的可靠性;可以簡化網(wǎng)絡(luò)節(jié)點配置、延長節(jié)點壽命。在高速 WPAN中，有兩種節(jié)點:PNCs(piconet coordinators)節(jié)點和DEVs(devices)節(jié)點。PNC節(jié)點通常是靜止且電源供電的復(fù)雜設(shè)備，而DEV節(jié)點通常是移動且電池供電的精簡設(shè)備。

適用于WPAN Mesh網(wǎng)絡(luò)的現(xiàn)有路由算法有很多，主要都是基于mesh樹路由協(xié)議的改進(jìn)。文獻(xiàn)［4］以IEEE802.15.5標(biāo)準(zhǔn)低速 WPAN 中的網(wǎng)狀自適應(yīng)樹(meshed adaptive tree，MAT)為基礎(chǔ)，將MAT劃分為兩層結(jié)構(gòu)，且在劃分后的兩層結(jié)構(gòu)采用不同的路由算法，提出了分級路由算法。但是，該路由算法由于采用傳統(tǒng)的無線自組網(wǎng)按需平面距離矢量路由協(xié)議(ad hoc on-demand distance vector routing，AODV)，從而存在由泛洪引起的過多控制開銷、消耗大量網(wǎng)絡(luò)資源等問題。文獻(xiàn)［5］中以MAT為基礎(chǔ)，將MAT和AODV結(jié)合，提出了TLMR(two-level mesh routing)路由算法。即，先在MAT中查詢有效路徑，如果不存在有效路由，則采用AODV。該路由算法同樣存在AODV的缺點。文獻(xiàn)［6］中提出了改進(jìn)的基于樹結(jié)構(gòu)的路由算法。其主要思想是在設(shè)備發(fā)現(xiàn)過程中父PNCs節(jié)點將建立到本微微網(wǎng)的子設(shè)備和子PNCs以及子微微網(wǎng)里的設(shè)備的路由信息，同時子PNCs也會建立到本微微網(wǎng)子設(shè)備以及它的子PNCs(如果存在)的路由信息。當(dāng)父PNCs或子PNCs節(jié)點收到數(shù)據(jù)分組時，將根據(jù)路由信息接收或者轉(zhuǎn)發(fā)。但是該路由算法在有橫向節(jié)點通信時所選路徑不是最短或最優(yōu)的路徑。

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

基于服務(wù)器的路由算法［1］是針對高速WPAN Mesh拓?fù)浣Y(jié)構(gòu)特點和網(wǎng)絡(luò)中節(jié)點特性而設(shè)計的樹路由協(xié)議。該算法分為3個階段:鏈路狀態(tài)信息的注冊階段、最優(yōu)路徑的建立階段和數(shù)據(jù)傳輸階段，其主要思想是源節(jié)點通過訪問距離源和目的節(jié)點最近的公共父節(jié)點獲得到達(dá)目的節(jié)點的最優(yōu)路徑(采用Dijkstra或Ford算法計算得到)。

圖1為路由算法(server routing，SR)的路由過程。Src為源節(jié)點，Dest為目的節(jié)點，R為網(wǎng)絡(luò)中的服務(wù)器節(jié)點(根節(jié)點)，即 Src和Dest的公共父節(jié)點。Src到Dest經(jīng)SR算法計算后得到的最優(yōu)路徑為Src-F-E-Dest，而樹路由得到的路徑為Src-A-B-RC-D-Dest。與樹路由相比，SR算法能在橫向路徑上找出最優(yōu)路徑。

SR算法仍然存在冗余的操作過程:每次轉(zhuǎn)發(fā)中繼列表信息，都是將整條最優(yōu)路徑的信息進(jìn)行轉(zhuǎn)發(fā)，這樣存在轉(zhuǎn)發(fā)已經(jīng)達(dá)到的中繼節(jié)點的冗余列表信息。本文針對這個缺點，提出了一種改進(jìn)的路由算法—高效率低時延的路由算法(high-efficiency and low-delay routing algorithm，HLRA)，該算法在解決以上問題的同時，實現(xiàn)了快速創(chuàng)建最優(yōu)路徑。

圖1 SR算法尋路過程示意圖Fig.1 Processes of server routing algorithm

2 HLRA算法

針對原始SR算法的缺點，本文提出了兩種新機(jī)制:廣播鏈路狀態(tài)注冊消息和縮短中繼列表長度，并基于它們提出了新的路由算法HLRA。新機(jī)制的采用使HLRA算法具有減少不必要的控制信息、縮短建路時間，提高路由算法效率等優(yōu)點。

2.1 廣播鏈路狀態(tài)注冊消息

鏈路狀態(tài)注冊消息是鏈路狀態(tài)信息注冊階段由子孫節(jié)點發(fā)給父輩節(jié)點包含鏈路狀態(tài)信息的控制消息。在HLRA算法中，節(jié)點在轉(zhuǎn)發(fā)鏈路狀態(tài)注冊消息時，在媒體訪問控制(media access control，MAC)子層采用廣播的方式，且在該消息的“Destination TREEID”域填入父節(jié)點地址。新機(jī)制的采用不僅能完成鏈路信息的注冊，而且能使所有鄰居節(jié)點獲得該消息中的鏈路信息，有利于后續(xù)更快地建立最優(yōu)路徑。

2.2 縮短中繼列表長度

路徑形成消息是用來在所得最優(yōu)路徑上傳遞路徑信息的控制消息，SR算法中每個路徑形成消息將傳遞整條路徑上的中繼列表信息。而在本新機(jī)制中，路徑形成消息的長度是可變的:在轉(zhuǎn)發(fā)過程中，將該消息經(jīng)歷過的節(jié)點信息刪除后再轉(zhuǎn)發(fā)，如圖2所示。改進(jìn)后的路徑形成消息在不改變原有的功能下，長度縮短還減少了通信開銷。

引理 在相同的網(wǎng)絡(luò)條件下，采用縮短中繼列表信息機(jī)制可以使HLRA算法比SR算法有更少的控制開銷。

證明 假設(shè)網(wǎng)絡(luò)中一共產(chǎn)生m次需要借助服務(wù)器計算最優(yōu)路徑的數(shù)據(jù)傳輸過程，每次過程的中繼列表有ni(i∈(1，m))個中繼節(jié)點信息(2ni字節(jié)的節(jié)點標(biāo)識和2ni字節(jié)的節(jié)點開銷)需要被轉(zhuǎn)發(fā)。

在SR算法中，需要轉(zhuǎn)發(fā)中繼列表信息的平均開銷為

(1)式中，ni+1表示目的節(jié)點需要將中繼列表信息轉(zhuǎn)發(fā)ni+1次才能到達(dá)源節(jié)點。

由于在HLRA算法中，每經(jīng)過一個中繼節(jié)點，都將該節(jié)點對應(yīng)的信息刪除，所以HLRA算法的平均開銷為

圖2 縮短中繼列表長度Fig.2 Reducing the relay list

3 性能評估

本節(jié)通過仿真比較分析網(wǎng)絡(luò)開銷、平均端到端時延和包的投遞率三方面的性能，從而驗證HLRA算法的有效性和優(yōu)越性。

3.1 仿真設(shè)置

采用 OPNET 14.5［7］仿真軟件構(gòu)建高速 WPAN Mesh網(wǎng)絡(luò)5 個仿真場景，分別為:50，100，150，200和250個節(jié)點;網(wǎng)絡(luò)中的所有節(jié)點都有唯一的地址;每個節(jié)點隨機(jī)地選擇其他節(jié)點作為目的節(jié)點;每個節(jié)點按照均值為5的指數(shù)分布發(fā)送長度為116 Byte［1，8］的數(shù)據(jù)分組;鏈路狀態(tài)信息以跳數(shù)為默認(rèn)值。

3.2 性能參數(shù)

1)網(wǎng)絡(luò)開銷:網(wǎng)絡(luò)中發(fā)送的控制分組比特數(shù)和數(shù)據(jù)分組比特數(shù)之和，用于評價算法的效率。網(wǎng)絡(luò)開銷C的計算公式如下

(3)式中，NB，NDi，NN，NF，NReq，NReg分別表示網(wǎng)絡(luò)中信標(biāo)消息、路徑發(fā)現(xiàn)消息、路徑通知消息、路徑形成消息、鏈路狀態(tài)請求消息和鏈路狀態(tài)注冊消息在發(fā)送時的比特數(shù)。

2)平均端到端時延:指所有數(shù)據(jù)分組從源節(jié)點到達(dá)目的節(jié)點的平均時延。平均端到端時延的計算公式如下

(4)式中，Ti和Di分別表示第i個數(shù)據(jù)分組到達(dá)目的節(jié)點所需時間和當(dāng)前網(wǎng)絡(luò)中總的收到的數(shù)據(jù)包個數(shù)。

3)包的投遞率:指成功收到的數(shù)據(jù)包數(shù)比上發(fā)送的數(shù)據(jù)包數(shù)的比值

(5)式中:Ri表示成功收到的數(shù)據(jù)包個數(shù);Sj表示發(fā)送的數(shù)據(jù)包個數(shù)。

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

以原始的SR算法作為比較對象，在相同的仿真條件下分析該算法與HLRA算法的平均端到端時延、網(wǎng)絡(luò)開銷等性能。

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

通過累計發(fā)送的信標(biāo)、鏈路狀態(tài)注冊、路徑通知、路徑形成等控制分組的比特開銷和發(fā)送數(shù)據(jù)分組時比特開銷之和得到網(wǎng)絡(luò)開銷。而在HLRA算法中，路徑形成消息的長度會動態(tài)變化。

圖3為兩種算法在多個場景中分別統(tǒng)計出的網(wǎng)絡(luò)開銷。由圖3可知，在網(wǎng)絡(luò)開銷方面，HLRA算法在各個網(wǎng)絡(luò)仿真場景都比原始的SR算法低。開銷減少的主要原因來自于兩跳鄰居節(jié)點建路過程的省略以及中繼列表信息長度的縮短。

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

3.3.2 平均端到端時延

圖4是兩種算法在5個仿真場景中分別統(tǒng)計出的平均端到端時延。由圖4可知，HLRA算法的數(shù)據(jù)分組平均端到端時延都低于SR算法的時延。HLRA算法的平均端到端時延較小的原因有兩方面:①廣播鏈路狀態(tài)注冊信息新機(jī)制可以縮短建立兩跳鄰居節(jié)點通信的時間，省去了一定建路時間;②中繼列表長度的縮短，減少了節(jié)點對這些控制消息的處理和傳送時間。

圖4 平均端到端時延Fig.4 Average end-to-end delay

3.3.3 包的投遞率

表1為SR算法和HLRA算法在仿真中的包投遞率。由表1可知，SR算法和HLRA算法在各個場景中包的投遞率幾乎一樣，基本能到達(dá)100%的理論值。

表1 包的投遞率Tab.1 Packet delivery ratio

4 結(jié)束語

本文針對IEEE802.15.5標(biāo)準(zhǔn)中高速部分的SR算法存在的轉(zhuǎn)發(fā)冗余的中繼列表信息問題，提出了HLRA路由算法，通過廣播鏈路狀態(tài)注冊消息和縮短中繼列表長度新機(jī)制解決了SR算法存在的上述問題。理論分析和仿真結(jié)果表明HLRA算法相對于SR算法，在網(wǎng)絡(luò)開銷、平均端到端時延等性能上具有更好的表現(xiàn)。未來的工作將在HLRA算法的基礎(chǔ)上，增加節(jié)能功能和對動態(tài)拓?fù)涞倪m應(yīng)，通過設(shè)計綠色的路由算法來構(gòu)建綠色的WPAN Mesh網(wǎng)絡(luò)［9］。

［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］.電信科學(xué)，2002，18(6):5-7.LEI Zhenzhou.The High-rate Wireless Personal Area Networks［J］.Telecommunications Science，2002，18(6):5-7.

［3］楊震，田峰.基于環(huán)境感知的異構(gòu)無線Mesh網(wǎng)絡(luò)體系結(jié)構(gòu)及關(guān)鍵技術(shù)［J］.中興通訊技術(shù)，2010，16(4):81-86.YANG Zheng，TIAN Feng.Research on Architecture and key Techniques of Ambient Heterogeneous wireless Mesh Networks［J］.ZTE，2010，16(4):81-86.

［4］江禹生，何芳.改進(jìn)的WPAN網(wǎng)狀自適應(yīng)樹路由算法［J］.重慶大學(xué)學(xué)報，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.

［5］江禹生，何芳，宋香麗.改進(jìn)的WPAN mesh路由協(xié)議［J］.計算機(jī)工程與應(yīng)用，2011，47(9):109-111.JIANG Yusheng，HE Fang，SONG Xiangli.Improved WPAN Mesh Routing Protocol［J］.Computer Engineering and Applications，2011，47(9):109-111.

［6］SANG Bongjung，HYUN Kikim，SOON Binyim，et al.Channel Time Allocation and Routing Algorithm for Multi-hop Communications in IEEE 802.15.3 High-Rate WPAN Mesh Networks［C］//Yong Shi.The International Conference on Computational Science 2007(ICCS 2007).Beijing:Springer-Verlag，2007:457-465.

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

［8］EUNCHANG Choi，JAEDOO Huh，KWANGSIK Kim，et al.Selection of Serving PNCs Based on Measured FER within IEEE 802.15.5 Wireless Mesh Network［C］//Jungwoo Lee.2007 International Conference on Convergence Information Technology.Gyeongju:IEEE Press，2007:2130-2135.

［9］林闖，田源，姚敏.綠色網(wǎng)絡(luò)和綠色評價:節(jié)能機(jī)制、模型和評價［J］.計算機(jī)學(xué)報，2011，34(4):593-612.LIN Chuang，TIAN Yuan，YAO Min.Green Network and Green Evaluation:Mechanism，Modeling and Evaluation［J］.Chinese Journal of Computer，2011，34(4):593-612.