依賴連通度的AdHoc自適應(yīng)鏈路補(bǔ)償算法

劉磊　凌翔　張遠(yuǎn)

摘要：利用AdHoc節(jié)點(diǎn)的連通度，設(shè)計(jì)基于位置補(bǔ)償模型，實(shí)現(xiàn)對(duì)邊緣覆蓋的AdHoc節(jié)點(diǎn)自適應(yīng)鏈路補(bǔ)償，協(xié)助完成與其它節(jié)點(diǎn)的網(wǎng)絡(luò)通信。通過仿真實(shí)驗(yàn)得出，依賴于連通度的補(bǔ)償算法比依賴于鏈路衰減的補(bǔ)償算法，在等半徑的覆蓋區(qū)域內(nèi)，鏈路數(shù)據(jù)吞吐量增加16%，鏈路延時(shí)下降了14%。

關(guān)鍵詞：AdHoc；鏈路補(bǔ)償；連通度

中圖分類號(hào)：TP393.07 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）01-0132-02

1 概述

AdHoc是一種無中心的移動(dòng)網(wǎng)絡(luò)，數(shù)據(jù)交換必然通過多個(gè)節(jié)點(diǎn)協(xié)作完成。網(wǎng)絡(luò)拓?fù)涞目焖僮兓⑿盘?hào)的遮擋和衰減、傳輸碰撞以及干擾等不可預(yù)知因素造成了AdHoc網(wǎng)絡(luò)難以維持穩(wěn)定的鏈路。AdHoc的鏈路補(bǔ)償需要實(shí)時(shí)地加入其它節(jié)點(diǎn)協(xié)助通信，但是節(jié)點(diǎn)的數(shù)量是有限的，并考慮能耗、并發(fā)連接度，補(bǔ)償節(jié)點(diǎn)不可能無限制被某個(gè)鏈路持續(xù)占用，因此AdHoc的鏈路補(bǔ)償就轉(zhuǎn)化為全局優(yōu)化問題。

AdHoc鏈路構(gòu)建算法分為先應(yīng)式鏈路和反應(yīng)式鏈路[1]：文獻(xiàn)[2]根據(jù)節(jié)點(diǎn)的拓?fù)洌A(yù)測(cè)自身的移動(dòng)方向，實(shí)時(shí)更新加權(quán)路由表，屬于先應(yīng)式算法，但路由表的刷新率均在秒級(jí)內(nèi)，AdHoc網(wǎng)絡(luò)沒有充足的資源維持。文獻(xiàn)[3]則根據(jù)角度變化，針對(duì)移動(dòng)造成的傳輸盲區(qū)，提出通過鄰近節(jié)點(diǎn)建立臨時(shí)子網(wǎng)，拓展信號(hào)的覆蓋范圍，實(shí)現(xiàn)局部最優(yōu)，保證優(yōu)先級(jí)較高的鏈路通信，屬于反應(yīng)式算法，但容易發(fā)生網(wǎng)絡(luò)擁塞。

本文提出依賴于連通度的AdHoc自適應(yīng)鏈路補(bǔ)償算法，設(shè)計(jì)基于位置的動(dòng)態(tài)補(bǔ)償模型，對(duì)位于覆蓋邊緣的AdHoc節(jié)點(diǎn)實(shí)現(xiàn)自適應(yīng)的鏈路補(bǔ)償，提高鏈路的數(shù)據(jù)吞吐量的同時(shí)，能夠降低傳輸延時(shí)。

2 問題描述

節(jié)點(diǎn)C向節(jié)點(diǎn)A發(fā)出鏈路請(qǐng)求，其中B為中間鏈路節(jié)點(diǎn)。此時(shí)，A、B、C之間的通信在信道存在如下沖突的可能：如果A向前移動(dòng)，導(dǎo)致A、B之間鏈路中斷，由于當(dāng)前鏈路還在維持中，A、B、C仍然占用該鏈路，無法加入其它P2P鏈路中。在此過程中，A、B會(huì)盡可能申請(qǐng)更多的信道資源，再將數(shù)據(jù)包轉(zhuǎn)儲(chǔ)至B節(jié)點(diǎn)，而后轉(zhuǎn)發(fā)。如果，A位于轉(zhuǎn)發(fā)節(jié)點(diǎn)A2的覆蓋范圍內(nèi)，則利用A2轉(zhuǎn)發(fā)。

模型約定初始化時(shí)，AdHoc節(jié)點(diǎn)的覆蓋半徑為R，節(jié)點(diǎn)連通度。在第次鏈路請(qǐng)求中，如果A與B的距離滿足，則連通度和，反之和。A為數(shù)據(jù)發(fā)送的源節(jié)點(diǎn)S，C為數(shù)據(jù)接收的端節(jié)點(diǎn)D，表示鏈路矢量，如果A1和A2在A的覆蓋范圍，則A1和A2為A的下游節(jié)點(diǎn)，如果A1和A2在B的覆蓋范圍，則A1和A2為B的上游節(jié)點(diǎn)。

3 位置補(bǔ)償?shù)淖赃m應(yīng)算法

位置補(bǔ)償是在估計(jì)某個(gè)時(shí)刻以及某個(gè)節(jié)點(diǎn)的鏈路發(fā)生中斷的情況下，同時(shí)未發(fā)現(xiàn)替代鏈路時(shí)進(jìn)行的位置補(bǔ)償[5]。如圖1所示，在原始鏈路中，先由發(fā)送點(diǎn)S請(qǐng)求鏈路路由，而后S向B發(fā)送數(shù)據(jù)，此時(shí)產(chǎn)生的延時(shí)被歸納為等待延時(shí)和傳送延時(shí)，表示當(dāng)前節(jié)點(diǎn)接收數(shù)據(jù)到開始轉(zhuǎn)發(fā)給下游節(jié)點(diǎn)所需等待的時(shí)間，表示一個(gè)數(shù)據(jù)幀由上游節(jié)點(diǎn)成功發(fā)送給下游節(jié)點(diǎn)所產(chǎn)生的時(shí)間。時(shí)間片分配時(shí)間由AdHoc的媒體接入層（MAC）決定，且節(jié)點(diǎn)等待時(shí)間均不同，對(duì)于節(jié)點(diǎn)i而言，假定存在個(gè)數(shù)據(jù)幀，且數(shù)據(jù)幀的大小相同，則存在：

4 仿真實(shí)驗(yàn)及結(jié)果

本文采用OMNet++4.0構(gòu)建了AdHoc節(jié)點(diǎn)通信和移動(dòng)的仿真平臺(tái)，并驗(yàn)證自適應(yīng)鏈路補(bǔ)償算法的有效性。

為了表現(xiàn)節(jié)點(diǎn)的移動(dòng)性，每個(gè)節(jié)點(diǎn)首先選擇上/下通道或者左/右通道，選擇的概率服從二項(xiàng)分布。在已選的通道上對(duì)前后方向的選擇則服從正態(tài)分布。而位置上的移動(dòng)則服從泊松分布，目的是滿足排隊(duì)論模型。

如圖2所示，以節(jié)點(diǎn)的移動(dòng)特征為主要參照可以得出：（1）隨著節(jié)點(diǎn)移動(dòng)速度的增加，本文算法比鏈路衰減算法的平均斷開次數(shù)要小于1；（2）隨著節(jié)點(diǎn)移動(dòng)距離的增加，本文算法比鏈路衰減算法的有效帶寬增加了16%；（3）隨著節(jié)點(diǎn)移動(dòng)距離和速度的增加，平均鏈路延時(shí)均降低了14%左右。

5 結(jié)語

本文利用AdHoc節(jié)點(diǎn)的連通度，設(shè)計(jì)基于位置補(bǔ)償模型，實(shí)現(xiàn)對(duì)邊緣覆蓋的AdHoc節(jié)點(diǎn)自適應(yīng)鏈路補(bǔ)償，通過協(xié)助下載完成與其它節(jié)點(diǎn)的鏈路通信。通過仿真實(shí)驗(yàn)得出，依賴于連通度的補(bǔ)償算法比依賴于鏈路衰減的補(bǔ)償算法，在等半徑的覆蓋區(qū)域內(nèi)，鏈路數(shù)據(jù)吞吐量增加16%，鏈路延時(shí)下降了14%。

參考文獻(xiàn)

[1]毛玉明，楊寧，段景山.移動(dòng)AdHoc網(wǎng)絡(luò)的一種新的自組織組網(wǎng)和路由算法[J].電子學(xué)報(bào)，2004，32（12）：161-164.

[2]任智，郭偉.多跳無線網(wǎng)路由協(xié)議研究進(jìn)展[J].電信科學(xué)，2003，19（8）：10-16.

[3]劉建航，畢經(jīng)平，徐鵬.一種提高系統(tǒng)吞吐量的協(xié)助下載補(bǔ)償模型[J].計(jì)算機(jī)學(xué)報(bào)，2012（7）：1390-1398.

[4]馮永，妖海龍，張亮.基于M/M/1/K排隊(duì)模型的低功耗無線通信網(wǎng)絡(luò)TDMA協(xié)議延遲評(píng)估及仿真[J].計(jì)算機(jī)科學(xué)，2013（40）：262-264.