無線Mesh網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇算法

張旭平 夏景明

摘 ?要： 穩(wěn)定路由是無線Mesh網(wǎng)絡(luò)（WMNs）的重要性能指標(biāo)，不穩(wěn)定路由會(huì)引起數(shù)據(jù)包丟失率和高的傳輸時(shí)延。為此，提出基于熵函數(shù)的節(jié)點(diǎn)穩(wěn)定路由（ESR）協(xié)議。ESR利用熵函數(shù)估計(jì)節(jié)點(diǎn)穩(wěn)定度。具體而言，ESR協(xié)議收集鏈路質(zhì)量，并計(jì)算鏈路穩(wěn)定值，再依據(jù)穩(wěn)定值估計(jì)節(jié)點(diǎn)熵。同時(shí)，將熵信息載入路由表，并與鄰居節(jié)點(diǎn)交互。一旦接收此消息，節(jié)點(diǎn)就存儲(chǔ)于路由表，然后選擇具有最大熵的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明，與基于干擾和信道切換（MIC）、基于期望傳輸次數(shù)（ETX）和基于加強(qiáng)學(xué)習(xí)的連通網(wǎng)關(guān)的最佳路徑（RLBDR）路由協(xié)議相比，提出的ESR協(xié)議在吞吐量、時(shí)延和數(shù)據(jù)包丟失率方面均具有較好的性能。

關(guān)鍵詞： 無線Mesh網(wǎng)絡(luò); ESR; 路由協(xié)議; 鏈路質(zhì)量指標(biāo); 節(jié)點(diǎn)選擇; 熵信息載入

中圖分類號(hào)： TN915.05?34; TP393 ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）13?0023?05

Forwarding node selection algorithm in wireless Mesh networks

ZHANG Xuping， XIA Jingming

（School of Electronic and Information Engineering， Nanjing University of Information Science &Technology， Nanjing 210044， China）

Abstract： The stability route is a key performance index in wireless mesh networks （WMNs）， but the instability route may cause the high packet loss rate and transmission delay. Therefore， the entropy?node stability?based routing （ESR） protocol is proposed， which can estimate the node stability by using entropy function. More specifically， the ESR protocol collects the link quality， then computes the stable value of the link， and estimate the node entropy according to stable value. At the same time， the entropy information is loaded into routing table， and interacted with neighbor nodes. Once this information is received， the node is stored into the routing table， and then the node with maximum entropy is selected as the next hop node. The experimental data shows that， in comparison with the protocols based on interference and channel switching， and expected transmission count （ETX）， as well as reinforcement learning?based best path to best gateway （RLBDR） protocol， the ESR protocol has higher performances in the aspects of throughput capacity， delay and packet loss rate.

Keywords： wireless mesh network; ESR; routing protocol; link quality metric; node selection; entropy information loading

0 ?引 ?言

無線網(wǎng)狀網(wǎng)絡(luò)（Wireless Mesh Networks，WMNs）被認(rèn)為是下一代無線網(wǎng)絡(luò)最有前景的技術(shù)[1]。與多跳移動(dòng)自組織網(wǎng)絡(luò)（Multi?hop Mobile Ad?Hoc Network，MANET）不同，WMNs具有相對(duì)靜止結(jié)構(gòu)、低移動(dòng)特點(diǎn)。WMNs是有線和無線網(wǎng)絡(luò)的結(jié)合體，且以無線Mesh路由（MRs）作為主干網(wǎng)，移動(dòng)點(diǎn)為用戶。MRs扮演著消息轉(zhuǎn)發(fā)角色。通常MRs向網(wǎng)關(guān)（GWs）傳輸流量，其中GWs用于連通Internet，如圖1所示。

圖1 ?典型的無線網(wǎng)狀網(wǎng)絡(luò)WMNs結(jié)構(gòu)

在WMN中干擾和GWs擁塞會(huì)提高數(shù)據(jù)包丟失，并增加時(shí)延。為了提高WMNs性能，研究人員提出了不同的方案，如文獻(xiàn)[1]提出基于方向和智能天線策略，文獻(xiàn)[2]提出了多輸入多輸出系統(tǒng)（Multiple Input Multiple Output，MIMO）策略，文獻(xiàn)[3]提出多信道多頻率技術(shù)，文獻(xiàn)[4]提出了合作通信技術(shù)。

實(shí)際上，路由策略對(duì)網(wǎng)絡(luò)性能有重要的影響。路由的目的就是依據(jù)具體路由指標(biāo)選擇最優(yōu)路由。為了獲取好的路由性能，路由指標(biāo)應(yīng)當(dāng)：不降低網(wǎng)絡(luò)穩(wěn)定性;隱含Mesh網(wǎng)絡(luò)的特性;避免轉(zhuǎn)發(fā)循環(huán)[5]。

網(wǎng)絡(luò)穩(wěn)定是多數(shù)網(wǎng)絡(luò)的主要性能指標(biāo)。當(dāng)網(wǎng)絡(luò)不穩(wěn)定，重建路由的頻率就會(huì)增加。這個(gè)增加是由于多條鏈路質(zhì)量過低導(dǎo)致的。即低質(zhì)量的鏈路導(dǎo)致路由翻轉(zhuǎn)，最終降低網(wǎng)絡(luò)性能。

現(xiàn)存WMNs的路由[6?10]可分為反應(yīng)式、先應(yīng)式和混合式。文獻(xiàn)[6?7]分別提出了按需距離矢量路由、動(dòng)態(tài)源路由，它們均屬于反應(yīng)式路由。而文獻(xiàn)[8?9]分別提出的優(yōu)化鏈路狀態(tài)路由、移動(dòng)Mesh路由均屬于先應(yīng)式路由。這些路由中的每個(gè)節(jié)點(diǎn)維持隱含網(wǎng)絡(luò)拓?fù)湫畔⒌穆酚杀怼４送?，文獻(xiàn)[10]提出TORA的混合路由。在路由發(fā)現(xiàn)時(shí)，TORA先從已存的部分路由表中搜索路由表，如果沒有可選路由，就利用反應(yīng)式方式再搜索路由。

然而，這些路由并沒有充分考慮WMNs的網(wǎng)絡(luò)特性、節(jié)點(diǎn)間的相互干擾以及導(dǎo)致長時(shí)延和高的數(shù)據(jù)包丟失率的原因。為此，提出基于熵函數(shù)的節(jié)點(diǎn)穩(wěn)定路由（Entropy?node Stability?based Routing，ESR）協(xié)議。ESR協(xié)議先估計(jì)鏈路質(zhì)量指標(biāo)，再計(jì)算節(jié)點(diǎn)的穩(wěn)定度，并計(jì)算節(jié)點(diǎn)的熵，然后選擇具有最大熵的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明，提出的ESR協(xié)議能夠有效地控制傳輸時(shí)延，降低數(shù)據(jù)包丟失率。

1 ?網(wǎng)絡(luò)模型

考慮多跳WMNs將節(jié)點(diǎn)分為MRs和GWs兩類。MRs形成多跳無線主干網(wǎng)，完成用戶與Internet間的流量傳輸。為了將流量傳輸至Internet，引用網(wǎng)關(guān)作中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。每個(gè)MR配備了多個(gè)無線接口，且每個(gè)接口上具有多個(gè)信道。假定MR的接口有多個(gè)不同的信道。

將主干WMN模擬為一個(gè)圖論[G=V，E]，其中，[V]為節(jié)點(diǎn)集（MRs和GWs），[E]為鏈路集。令[?ij]表示兩個(gè)MRs（[υi]，[υj]）間的鏈路，且[υi]，[υj∈V]。此外，通過GWs連通Internet。

2 ?ESR協(xié)議

2.1 ?鏈路質(zhì)量指標(biāo)和節(jié)點(diǎn)穩(wěn)定度

2.1.1 ?鏈路質(zhì)量指標(biāo)

鏈路質(zhì)量指標(biāo)（Link Quality Metric，LQM）是反映鏈路特性的參數(shù)。LQM定義為兩個(gè)參數(shù)的權(quán)重函數(shù)：干擾率（Interference Ratio，IR）和擁塞等級(jí)（Congestion Level，CL）。IR包含了信噪比（Signal to Noise Ratio，SNR）和信干擾比（Signal to Interference plus Noise Ratio，SINR）。假定從節(jié)點(diǎn)[υ]至節(jié)點(diǎn)[u]的鏈路[?]的IR定義為：

2.2 ?基于節(jié)點(diǎn)穩(wěn)定的路由

通常是利用鏈路的歷史信息和當(dāng)前信息估計(jì)鏈路的穩(wěn)定指標(biāo)。如果鏈路的LQM低于預(yù)定門限值，則該鏈路認(rèn)為是可接受的，否則認(rèn)為不可接受。顯然，如果鏈路在可接受和不可接受間波動(dòng)也是不可接受的。因?yàn)檫@種波動(dòng)會(huì)導(dǎo)致網(wǎng)絡(luò)性能振動(dòng)，進(jìn)而導(dǎo)致鏈路的不穩(wěn)定。

本文提出基于穩(wěn)定指標(biāo)算法SIA，并利用接受與不可接受間的鏈路波動(dòng)、鏈路持續(xù)力估算鏈路穩(wěn)定性。計(jì)算鏈路穩(wěn)定性過程，如下所示。假定鏈路[?]在時(shí)刻[t+1]的穩(wěn)定值為[St+1?]。每個(gè)節(jié)點(diǎn)執(zhí)行SIA算法估計(jì)鏈路穩(wěn)定值。再利用穩(wěn)定值選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，進(jìn)而實(shí)現(xiàn)ESR，即ESR是利用SIA算法計(jì)算鏈路的穩(wěn)定值。

如果鏈路[?]不是新鏈路，即[?∈RTti]，則判斷鏈路[?]在時(shí)刻[t]至[t+1]間的鏈路是否變化。如果[LQM?t+1-LQM?t≤η]，則表明鏈路沒有發(fā)生變化，其中[η]為控制參數(shù)，且[η∈0，1]。在這種情況下，[St+1?=St?+1]。

如果[LQM?t+1-LQM?t>η]，說明鏈路發(fā)生變化。在這種情況下，判斷鏈路是朝好的方向（優(yōu)化），還是下降（惡化）。如果[LQM?t+1

2.3 ?下一跳節(jié)點(diǎn)的選擇

式中[Ni=RTt+1i]表示節(jié)點(diǎn)[υi]的路由表的節(jié)點(diǎn)數(shù)。熵值越高，表明節(jié)點(diǎn)越穩(wěn)定。在選擇下一跳節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)先依據(jù)式（11）計(jì)算自己的熵，然后向自己的一跳鄰居節(jié)點(diǎn)廣播。節(jié)點(diǎn)一旦接收到此信息，就將此信息存入路由表，然后選擇最穩(wěn)定的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。

綜上所述，轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇過程如圖2所示。先計(jì)算LQM，然后利用SIA算法計(jì)算鏈路穩(wěn)定值，然后，再計(jì)算自己的熵，并將熵信息存于路由表。通過交互路由表信息，鄰居節(jié)點(diǎn)就能獲取一跳鄰居節(jié)點(diǎn)的熵信息，并選擇具有最大熵的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

圖2 ?選擇下一跳節(jié)點(diǎn)框圖

2.4 ?路由更新及維護(hù)

每個(gè)節(jié)點(diǎn)周期地廣播自己的熵，且周期[T]設(shè)定為1 min，即節(jié)點(diǎn)每隔[T]更新熵信息。若發(fā)現(xiàn)鄰居節(jié)點(diǎn)存在具有更大熵的節(jié)點(diǎn)，就將此節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。此外，當(dāng)已選擇的下一跳節(jié)點(diǎn)離開鄰居范圍，就必須在鄰居節(jié)點(diǎn)集內(nèi)重新選擇一個(gè)節(jié)點(diǎn)作為自己的轉(zhuǎn)發(fā)節(jié)點(diǎn)，重新構(gòu)建路由，進(jìn)而實(shí)現(xiàn)路由維護(hù)的目的。

3 ?仿真及分析

利用NS2軟件建立仿真平臺(tái)，具體的仿真參數(shù)如表1所示?？紤]16個(gè)MRs隨機(jī)分布于[1 ?000×1 ?000]區(qū)域，且區(qū)域內(nèi)有三個(gè)網(wǎng)關(guān)（即節(jié)點(diǎn)1，2，3）。以IEEE 802.11作為MAC層協(xié)議。

表1 ?仿真參數(shù)設(shè)置

為了更好地分析ESR，選擇基于加強(qiáng)學(xué)習(xí)的連通網(wǎng)關(guān)的最佳路徑RLBDR（Reinforcement Learning?based Best Path To Best Gateway）[11]，干擾和信道切換MIC（Metric of Interference and Channel）[12]、期望傳輸次數(shù)ETX（Expected Transmission Count）[13]路由協(xié)議作為參照。同時(shí)，分析它們的網(wǎng)絡(luò)平均吞吐量、數(shù)據(jù)包丟失率以及端到端傳輸時(shí)延。其中，平均吞吐量是指在給定時(shí)間內(nèi)成功接收的數(shù)據(jù)字節(jié)數(shù);數(shù)據(jù)包丟失率是指丟失的數(shù)據(jù)包數(shù)與已發(fā)送的數(shù)據(jù)包數(shù)之比。而端到端傳輸時(shí)延是指將CBR數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至網(wǎng)關(guān)所需的平均時(shí)延。

首先分析平均吞吐量隨數(shù)據(jù)率的變化情況，且數(shù)據(jù)率從1 000～3 000 Kb/s變化，實(shí)驗(yàn)數(shù)據(jù)如圖3所示。

圖3 ?平均吞吐量隨數(shù)據(jù)率的變化情況

從圖3可知，隨著數(shù)據(jù)率的增加，平均吞吐量也呈增加趨勢。原因在于數(shù)據(jù)率的增加，加大了網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，必然增加了平均吞吐量。與RLBDR，MIC，ETX相比，提出的ESR吞吐量得到有效地提高，且分別比RLBDR，MIC，ETX的吞吐量提高了近7%，17%，36%。

然后，分析數(shù)據(jù)包丟失率隨數(shù)據(jù)率的變化情況，實(shí)驗(yàn)數(shù)據(jù)如圖4所示。

圖4 ?數(shù)據(jù)包丟失率隨數(shù)據(jù)率的變化曲線

從圖4可知，數(shù)據(jù)率的增加提高了數(shù)據(jù)包丟失率。原因在于：當(dāng)數(shù)據(jù)率增加到一定程度，會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞，這必然增加了數(shù)據(jù)包丟失率。然而，與RLBDR，MIC和ETX相比，提出的ESR的數(shù)據(jù)包丟失率得到有效地控制，并且隨數(shù)據(jù)率的增加，控制效果越好。

最后，分析了端到端傳輸時(shí)延隨數(shù)據(jù)率的變化曲線，實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

圖5 ?端到端傳輸時(shí)延隨數(shù)據(jù)率的變化

從圖5可知，提出的ESR的傳輸時(shí)延低于RLBDR，MIC和ETX。在數(shù)據(jù)率為1 000 Kb/s時(shí)，ESR比MIC，ETX的時(shí)延下降了31%，29%。然而，當(dāng)數(shù)據(jù)率在1 000～2 000 Kb/s區(qū)間時(shí)，RLBDR的端到端傳輸時(shí)延低于ESR，且下降了約25%。原因在于：ESR不是從傳輸跳數(shù)角度選擇路由，而是從穩(wěn)定角度選擇路由。因此，在低速區(qū)時(shí)，RLBDR的傳輸時(shí)延較低。然而，對(duì)于高速時(shí)區(qū)（數(shù)據(jù)率大于2 500 Kb/s），ESR的傳輸時(shí)延優(yōu)于RLBDR。例如，在數(shù)據(jù)率為2 500 Kb/s時(shí)，ESR的時(shí)延降低了49%;當(dāng)數(shù)據(jù)率為3 000 Kb/s時(shí)，時(shí)延降低為25%。

4 ?結(jié) ?語

針對(duì)WMNs網(wǎng)絡(luò)的路由問題，提出基于熵函數(shù)的節(jié)點(diǎn)穩(wěn)定路由ESR。ESR路由先構(gòu)建鏈路質(zhì)量指標(biāo)LQM，再計(jì)算節(jié)點(diǎn)的熵。熵越大，節(jié)點(diǎn)越穩(wěn)定。因此，選擇具有最大熵的節(jié)點(diǎn)傳輸數(shù)據(jù)包，從而建立穩(wěn)定的路由。實(shí)驗(yàn)數(shù)據(jù)表明，提出的ESR有效地提高了數(shù)據(jù)包傳輸率，降低了傳輸時(shí)延。

參考文獻(xiàn)

[1] STINE J A. Exploiting smart antennas in wireless mesh networks using contention access [J]. IEEE wireless communications magazine， 2016， 13（2）： 38?49.

[2] SHIN J， LEE H， NA J， et al. Load balancing among internet gateways in Ad Hoc networks [C]// Proceedings of the 62nd Vehicular Technology Conference. Dallas： IEEE， 2015： 1677?1680.

[3] KYASANUR P， VAIDYA N H. Capacity of multi?channel wireless networks： impact of number of channels and interfaces [EB/OL]. [2005?11?21]. https：//www.ics.forth.gr/mobile/Bibliography/LoadBalancing/LB/Capacity_MChannel_WLANs.pdf.

[4] CAO B， FENG G LLI Y， et al. Cooperative media access control with optimal relay selection in error?prone wireless networks [J]. IEEE transactions on vehicular technology， 2014， 63（1）： 252?265.

[5] YANG Y， WANG J. Designing routing metrics for Mesh networks [J]. IEEE wireless Mesh networks， 2015， 6（8）： 35?61.

[6] PAN X， ZENG H Y. Improved Ad Hoc on?demand distance vector routing based on bandwidth [C]// 2010 International Conference on Computational Problem?Solving. Lijiang： IEEE， ?2016： 238?245.

[7] JOHNSON D B， MALTZ D A， BROCH J. DSR： the dynamic source routing protocol for multi?hop wireless Ad Hoc networks [M]// Anon. Ad Hoc Networking. Boston： Addison?Wesley， 2016： 56?67.

[8] CLAUSEN T， JACQUET P. Optimized link state routing protocol （OLSR） [M]. US： RFC， 2016： 23?32.

[9] LIAO G L， CHEN C Y， HSU S W， et al. Adaptive situation?aware load balance scheme for mobile wireless mesh networks [C]// 2011 IEEE Conference on Computer Communications Workshops. Shanghai： IEEE， 2016： 391?396.

[10] ATER F J， VINAGRE J J， MORGADO E. A low energy and adaptive architecture for efficient routing and robust mobility management in wireless sensor networks [C]// Proceedings of the 2011 31st International Conference on Distributed Computing Systems Workshops. Minneapolis： IEEE， 2011： 172?181.

[11] BOUSHABA M， HAFID A， BELBEKKOUCHE A. Reinforcement learning based routing in wireless mesh networks [J]. Wireless networks， 2015， 19（8）： 2079?2091.

[12] LI D， LIU H. Comparative analysis of protocols in wireless Ad networks [J]. Ambient intelligent wireless networks， 2014， 4（7）： 23?31.

[13] DE COUTO D S， AGUAYO D， CHAMBERS B A， et al. Performance of multihop wireless networks： shortest path is not enough [J]. ACM SIGCOMM computer communication review， 2014， 33（1）： 83?88.