基于動(dòng)量自?xún)?yōu)機(jī)制的網(wǎng)絡(luò)資源路徑高速遞歸算法研究

田祎

（商洛學(xué)院　陜西商洛726000）

?

基于動(dòng)量自?xún)?yōu)機(jī)制的網(wǎng)絡(luò)資源路徑高速遞歸算法研究

田祎

（商洛學(xué)院陜西商洛726000）

摘要：為解決無(wú)線移動(dòng)自組織網(wǎng)絡(luò)存在的資源路徑遞歸困難，控制開(kāi)銷(xiāo)巨大等實(shí)際部署難題。基于動(dòng)量自?xún)?yōu)機(jī)制，本文提出了一種資源路徑高速遞歸算法。首先通過(guò)分布在網(wǎng)絡(luò)中的節(jié)點(diǎn)動(dòng)量的監(jiān)測(cè)，綜合計(jì)算路徑高速遞歸過(guò)程中的動(dòng)量，以改變因素對(duì)整個(gè)網(wǎng)絡(luò)及輸出能力的影響，根據(jù)這種改變因素實(shí)時(shí)對(duì)網(wǎng)絡(luò)資源路徑進(jìn)行動(dòng)態(tài)遞歸。仿真實(shí)驗(yàn)表明：本文提出的機(jī)制在帶寬受限情況下在，可以較好的提高能量傳輸效率，降低資源遞歸損耗，實(shí)現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化傳輸，對(duì)實(shí)際部署具有一定的借鑒意義。

關(guān)鍵詞：無(wú)線移動(dòng)自組網(wǎng)；資源遞歸；動(dòng)量輸出；分配

隨著移動(dòng)無(wú)線自組織網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，各種基于無(wú)線自組織網(wǎng)的應(yīng)用也日益突出，如廣泛用到的網(wǎng)絡(luò)電視、網(wǎng)絡(luò)電話(huà)等。和有線網(wǎng)絡(luò)特別是基于光纖的骨干網(wǎng)絡(luò)相比，無(wú)線通信過(guò)程中存在頻譜帶寬窄、多徑傳輸造成嚴(yán)重的資源競(jìng)爭(zhēng)與浪費(fèi)等問(wèn)題［1］。因此提高整個(gè)網(wǎng)絡(luò)通信之中的動(dòng)量效率，就成為移動(dòng)無(wú)線自組織網(wǎng)絡(luò)中的一個(gè)重要方面［2］。

Nguyen D等［3］提出可以采用非被動(dòng)式路由搜尋機(jī)制來(lái)對(duì)多徑傳輸中的業(yè)務(wù)數(shù)據(jù)進(jìn)行能量?jī)?yōu)化，在數(shù)據(jù)流量較大時(shí)能夠有效的減少資源的浪費(fèi)。但是由于主動(dòng)路由在節(jié)點(diǎn)稀疏時(shí)的效率不高，因此只有在節(jié)點(diǎn)密度達(dá)到一定水平后才能使用該種機(jī)制。Xjao X等［4］提出了一種分布式資源優(yōu)化機(jī)制，通過(guò)將傳輸資源所耗能量進(jìn)行均勻化處理，不過(guò)由于這種資源優(yōu)化機(jī)制對(duì)動(dòng)態(tài)拓?fù)渥兓蛩乜紤]的不夠，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化較大時(shí)將失去作用。Chj K K等［5］考慮到無(wú)線鏈路的自相關(guān)特性，通過(guò)自相關(guān)傳輸?shù)姆绞浇档湍芰肯模行У奶岣吡速Y源路徑的遞歸效果。但是由于鏈路的自相關(guān)特性并非十分強(qiáng)烈，因此不具有普適性的特性。

本文首先考慮了在不同差錯(cuò)水平上對(duì)無(wú)線鏈路的動(dòng)量及相應(yīng)的能量消耗進(jìn)行了分析，提出了一種基于動(dòng)量自?xún)?yōu)機(jī)制的分配算法，通過(guò)在靜止?fàn)顟B(tài)構(gòu)造最優(yōu)解并同時(shí)采取動(dòng)態(tài)調(diào)整的方式，引入資源多徑調(diào)用和自?xún)?yōu)化，同時(shí)對(duì)資源、能量、路徑等動(dòng)量要素進(jìn)行統(tǒng)籌調(diào)度，從而實(shí)現(xiàn)動(dòng)量及速率的最優(yōu)。

1　無(wú)線自組織網(wǎng)絡(luò)的動(dòng)量分配

無(wú)線信號(hào)在無(wú)線信道里運(yùn)轉(zhuǎn)時(shí)，信源和信道的能量及控制變量按照一定的規(guī)律進(jìn)行變換。這種能量及變量可以用一種動(dòng)量的形式加以表現(xiàn)，這種動(dòng)量反映了無(wú)線信號(hào)在傳播時(shí)候的一些必要的規(guī)律。其動(dòng)量衰落PL（d）按照如下的解析式的規(guī)律變動(dòng)：

其中，d為整個(gè)信道長(zhǎng)度，x和y是相關(guān)常量，與環(huán)境和傳播模型密切相關(guān)［6-8］。

在多路徑耗散的背景下，無(wú)線信號(hào)按照多路徑并發(fā)工作傳輸方式進(jìn)行傳輸［9-10］，一般而言，為了減少信號(hào)的動(dòng)量損失，人們都會(huì)采取多條信道并發(fā)傳輸資源，在并發(fā)傳輸時(shí)，信源信號(hào)的發(fā)射會(huì)按照多路徑分割傳輸?shù)哪Ｊ竭M(jìn)行傳輸，另外會(huì)采取專(zhuān)門(mén)的動(dòng)量控制因素進(jìn)行動(dòng)量的控制工作。設(shè)L為整個(gè)信道中處于激活狀態(tài)的路徑數(shù)量。從第i個(gè)節(jié)點(diǎn)出發(fā)的通信鏈路為L(zhǎng)l，j，該節(jié)點(diǎn)發(fā)送數(shù)據(jù)的動(dòng)量值為Ptli，第i個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)接收的動(dòng)量值為Гtli由下列的解析表達(dá)式構(gòu)成：

其中Kli為常數(shù)，一般取自然對(duì)數(shù)，進(jìn)行相干調(diào)制之后，整個(gè)動(dòng)量分配問(wèn)題可以歸結(jié)為如下的解析表達(dá)式問(wèn)題：

其中Pnm為過(guò)往時(shí)刻網(wǎng)絡(luò)動(dòng)量總和的加權(quán)平均。

由于動(dòng)量的調(diào)整屬于對(duì)增量的動(dòng)量進(jìn)行一定程度的遞歸，一旦某條路徑L因網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生改變而導(dǎo)致開(kāi)銷(xiāo)發(fā)生變化時(shí)，設(shè)動(dòng)量的改變水平為△Pl，根據(jù)式（2）、（3）可以得到整個(gè)網(wǎng)絡(luò)的動(dòng)量解析表達(dá)式如下：

其中△Pl為動(dòng)量改變水平，△P（li）為單條鏈路上的動(dòng)量改變水平。

2　本文資源路徑高速遞歸算法設(shè)計(jì)

由上節(jié)可知?jiǎng)恿康南呐c傳遞是一個(gè)基于連續(xù)過(guò)程的連續(xù)函數(shù)，只要尋找到一種動(dòng)量分配方式，則通信中的總能量消耗即達(dá)到最小。不過(guò)在無(wú)線移動(dòng)自組織網(wǎng)絡(luò)中，集中機(jī)制難以發(fā)揮作用，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生劇烈變動(dòng)時(shí)，整個(gè)網(wǎng)絡(luò)的開(kāi)銷(xiāo)及控制的難度將極大的惡化。因此本文算法設(shè)計(jì)將圍繞動(dòng)量的增量和改變兩者同時(shí)進(jìn)行，整個(gè)算法的步驟如下所示：

Step 1：首先求出某條具體路徑L上的功率變化，得到數(shù)據(jù)后，轉(zhuǎn)Step 2；

Step 2：動(dòng)態(tài)監(jiān)控路徑上的速率變化，當(dāng)速率變化超過(guò)一定值時(shí)，將該信息廣播，轉(zhuǎn)Step 3；

Step 3：均勻劃分變動(dòng)速度，分成n個(gè)部分，每部分取出特征點(diǎn)，將該特征點(diǎn)信息寫(xiě)入路由表；

Step 4：通過(guò)廣播方式將特征對(duì)全網(wǎng)節(jié)點(diǎn)進(jìn)行廣播，并動(dòng)態(tài)更新入路由表；

Step 6：更新路徑并將路徑加入路由表中，若成功，算法結(jié)束；反之，返回第2步繼續(xù)進(jìn)行。

Step 7：本次周期結(jié)束，轉(zhuǎn)入下以周期并重新從Step 1開(kāi)始。

詳細(xì)算法流程圖如圖1所示。

從算法流程中可以看到，資源路徑的高速遞歸過(guò)程也是一個(gè)自治的過(guò)程，網(wǎng)絡(luò)資源會(huì)根據(jù)自身的情況動(dòng)態(tài)的判斷自身的狀態(tài)，根據(jù)狀態(tài)的不同激發(fā)不同的操作。另外，采取多徑檢測(cè)的方式對(duì)功率、資源等動(dòng)量要素進(jìn)行整合，采取數(shù)據(jù)提取、特征劃分、數(shù)據(jù)時(shí)效性檢測(cè)，并引入廣播機(jī)制對(duì)資源進(jìn)行綜合判斷，從而形成一條龍式的綜合解決方案。

圖1　算法流程圖

3　仿真與結(jié)果分析

本節(jié)借助ONE仿真平臺(tái)，在相同的仿真環(huán)境下，對(duì)該路由進(jìn)行了模擬仿真［11］。仿真時(shí)間取21 600 s，采取隨機(jī)路點(diǎn)模型作為仿真模型［12-13］。為了體現(xiàn)本文算法的優(yōu)異網(wǎng)絡(luò)性能，選取DSR的路由策略為對(duì)照組。每個(gè)路由在相同的參數(shù)下?lián)Q取不同節(jié)點(diǎn)速度，仿真30次取平均值。仿真環(huán)境參數(shù)如表1所示。

表1　參數(shù)設(shè)置

圖2顯示了在節(jié)點(diǎn)最大速度在150 m/s的情況下，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量迅速增加時(shí)網(wǎng)絡(luò)路由的歸一化能量對(duì)比情況。從圖中可以看到隨著網(wǎng)絡(luò)規(guī)模的不斷增加，本文算法與傳統(tǒng)的DSP算法相比，能耗水平明顯下降，這是因?yàn)楸疚乃惴ㄒ氲膭?dòng)態(tài)遞歸能夠有效的去除無(wú)效鏈路的能量消耗，避免了動(dòng)量損失，從而降低了歸一化能量水平。

圖2　不同算法的歸一化能量測(cè)試

圖3顯示了在節(jié)點(diǎn)數(shù)據(jù)量不斷增加時(shí)，本文算法與傳統(tǒng)的DSP算法在分組投遞率上的對(duì)比［14-15］。從圖中可以看到，當(dāng)節(jié)點(diǎn)的數(shù)據(jù)發(fā)送量不斷增大時(shí)，本文算法的分組投遞水平明顯高于DSP算法，這是因?yàn)楸疚脑谫Y源路徑高速遞歸時(shí)，可以增加有效路徑對(duì)數(shù)據(jù)包的吸納，另外源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包在網(wǎng)絡(luò)分組調(diào)度時(shí)，無(wú)效數(shù)據(jù)包會(huì)被及時(shí)清除，而且一個(gè)周期內(nèi)未被投遞出去的數(shù)據(jù)包也會(huì)被更新，在下一個(gè)發(fā)送周期到來(lái)之前將從路由表中被清除，從而降低了無(wú)效數(shù)據(jù)包在分組投遞時(shí)候的作用，因此數(shù)據(jù)發(fā)送量迅速增加的情況下，網(wǎng)絡(luò)擁塞水平也有一定的改，因此改善了分組投遞率指標(biāo)。

圖3　不同算法的分組投遞率測(cè)試

圖4顯示了在節(jié)點(diǎn)運(yùn)動(dòng)速度不斷增加的情況下，本文算法與傳統(tǒng)的DSP算法在網(wǎng)絡(luò)傳輸時(shí)延指標(biāo)上的對(duì)比。從圖中可以看到，本文算法的時(shí)延水平明顯低于DSP算法，這是因?yàn)殡S著節(jié)點(diǎn)速度不斷增加，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)更迭頻繁，本文機(jī)制可以有效避免無(wú)效鏈路對(duì)動(dòng)量的負(fù)相關(guān)性影響；此外，在節(jié)點(diǎn)運(yùn)動(dòng)速度增加時(shí)，由于本文算法對(duì)多條路徑上的數(shù)據(jù)進(jìn)行實(shí)時(shí)監(jiān)測(cè)和動(dòng)態(tài)更新，可以有效的去除延時(shí)的信息包，改善整個(gè)網(wǎng)絡(luò)的擁塞效益，整個(gè)網(wǎng)絡(luò)的多徑傳輸效益也得增強(qiáng)，因此改善了時(shí)延指標(biāo)。

圖4　不同算法的網(wǎng)絡(luò)時(shí)延測(cè)試

4　結(jié)束語(yǔ)

隨著無(wú)線自組織網(wǎng)絡(luò)技術(shù)發(fā)展，網(wǎng)絡(luò)中擁塞等現(xiàn)象的發(fā)生也日益頻繁，傳統(tǒng)的網(wǎng)絡(luò)資源路徑遞歸技術(shù)難以適應(yīng)現(xiàn)有的技術(shù)發(fā)展需求［16］。文中為解決無(wú)線移動(dòng)自組織網(wǎng)絡(luò)存在的資源路徑遞歸困難，控制開(kāi)銷(xiāo)巨大等實(shí)際部署難題，通過(guò)分析設(shè)計(jì)了一種基于動(dòng)量自?xún)?yōu)機(jī)制的遞歸算法，采取動(dòng)量遞歸和自?xún)?yōu)方式，動(dòng)態(tài)對(duì)每條拓?fù)渎酚蛇M(jìn)行調(diào)整。仿真實(shí)驗(yàn)表明：本文提出的機(jī)制能夠有效的減少網(wǎng)絡(luò)能量消耗，提高網(wǎng)絡(luò)性能指標(biāo)，對(duì)現(xiàn)有的無(wú)線移動(dòng)自組織網(wǎng)絡(luò)的部署有一定的指導(dǎo)意義。

參考文獻(xiàn)：

［1］楊林，鄭剛.無(wú)線多跳網(wǎng)中具有網(wǎng)絡(luò)編碼意識(shí)的機(jī)會(huì)路由協(xié)議［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，50（10）：1713-1717.

［2］Ah1swede R，Caj N，Lj S Y R，et a1.Network jnformatjon f1ow［J］. IEEE Trans. on Informatjon Theory，2000，46（4）：1204-1216.

［3］Nguyen D，Tran T，Nguyen T.Wjre1ess broadcast usjng network codjng［J］. IEEE Trans.on Vehjcu1ar Techno1ogy，2009，58（2）：914-925.

［4］Xjao X，Yang L M，Wang W P.A wjre1ess broadcastjng retransmjssjon approach based on network codjng［C］//Proc. 4th IEEE Int’1 Conf. Cjrcujts and Systems for Communjcatjons，2008：782-786.

［5］Chj K K，Jjang X H，Ye B L. Effjcjent network codjng-based 1oss recovery for re1jab1e mu1tjcast jn wjre1ess networks［J］. IEICE Trans. on Communjcatjon，2010，93（4）：971-981.

［6］Yan Y，Zhao Z，Zhang B，et a1.Mechanjsm for maxjmjzjng area-centrjc codjng gajns jn wjre1ess mu1tj-hop networks［C］. In Proc. of IEEE Internatjona1 Conference on Communjcatjons，Dresden，IEEE press，2009：14-18.

［7］Lj Y R，Yetmg R W，Caj N.Ljnear network codjng［J］.IEEE Trans.on Informatjon theory，2003，49（2）：371-381.

［8］Ho T，Medard M，Shj J，et a1. On randomjzed network codjng ［C］//In Proc. of the 41th Annua1 A11erton Conference on Communjcatjon Contro1 and Computjng，2003：48-52.

［9］Wang D，Zhang Q，Lju J C.Partja1 network codjng：theory and app1jcatjon for contjnuous sensor data co11ectjon［C］. In Proc. of the 14th IEEE Internatjona1 Workshop on Qua1jty of Servjce，2006：93- 101.

［10］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.北京：清華大學(xué)出版社，2004.

［11］Bettstetter C，Resta G，Santj P. The node djstrjbutjon of the random waypojnt mobj1jty mode1 for wjre1ess Ad Hoc networks［J］.IEEE Transactjons on Mobj1e Computjng，2003，2 （3）：257-269.

［12］Yang Z Zhang Q，Wang R.On storage dynamjcs of space de-1ay/djsruptjon to1erant network node［J］.Wjre1ess Networks，2014，20（8）：2529-2541.

［13］G Djnj，A Lo Duca.Towards a reputatjon -based routjng protoco1 to contrast b1ackho1es jn a de1ay to1erant network ［J］.Ad Hoc Networks，2012，10（7）：1167-1178.

［14］Wang L，Geng X.A Communjty-drjven Hjerarchjca1 Message Transmjssjon Scheme jn Opportunjstjc Networks［J］. Smart Computjng Revjew，2011，1（1）：85-94.

［15］Jo11jffeD，Tran T，Nguyen T. Data mjnjng network codjng［J］. IEEE Trans. on Vehjcu1ar Techno1ogy，2009，58（2）：914-925.

［16］LEE W.A data mjnjng framework for constructjng features and mode1s for jnstrusjon detectjon systems［D］.New York Computer Scjence Department of Co1umbja Unjversjty，2012.

The research on the hlgh sPeed recurslve algorlthm of network resource Path based on momentum self oPtlmlzatlon mechanlsm

TIAN Yj
（
Shangluo University，Shangluo 726000，China）

Abstract:jn order to so1ve the prob1em of resource path recursjon jn wjre1ess mobj1e ad hoc networks，the contro1 overhead js huge and other practjca1 dep1oyment prob1ems. In thjs paper，a hjgh speed recursjve a1gorjthm based on momentum js proposed. Fjrst of a11，through the djstrjbutjon of nodes jn the network，the momentum jn the process of ca1cu1atjng the comprehensjve path hjgh-speed recursjve change factors of the network and output capacjty accordjng to the change of rea1-tjme dynamjc recursjve path to a network resource. The sjmu1atjon resu1ts show that the proposed mechanjsm has obvjous advantages jn the transmjssjon rate and bjt error and energy consumptjon jn the bandwjdth constrajned condjtjons，whjch has certajn reference va1ue for the actua1 dep1oyment.

Key words:wjre1ess mobj1e ad hoc network；resource recursjon；momentum output；djstrjbutjon

中圖分類(lèi)號(hào)：TN711.1

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1674-6236（2016）07-0076-03

收稿日期：2015-11-11稿件編號(hào)：201511111

基金項(xiàng)目：陜西省教育廳專(zhuān)項(xiàng)科研項(xiàng)目（14JK1221）；商洛學(xué)院服務(wù)地方專(zhuān)項(xiàng)（15SKY-FWDF003）；商洛學(xué)院教改項(xiàng)目（15jyjx135）

作者簡(jiǎn)介：田祎（1983—），男，陜西商南人，碩士，講師。研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。