基于混沌映射組播技術(shù)的無線移動自組織網(wǎng)絡(luò)路由研究

郝 平

(陜西工業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院，陜西 咸陽 712000)

0 引言

隨著我國信息化社會的逐步推進，越來越多的社會經(jīng)濟活動采用無線終端部署形式［1］，如在線實時指揮、視頻遠程管理系統(tǒng)。這些系統(tǒng)主要采取無線移動自組織網(wǎng)的形式進行部署［2］。作為一種組網(wǎng)靈活、抗毀性強的網(wǎng)絡(luò)體系，無線移動自組織網(wǎng)絡(luò)能夠優(yōu)化利用資源，充分保障在帶寬受限情況下的網(wǎng)絡(luò)部署于數(shù)據(jù)分發(fā)。另外無線移動自組織網(wǎng)絡(luò)由于不存在明顯的控制中心，因此抗干擾性極強，一旦某個具體的節(jié)點因為具體原因而導(dǎo)致不能正常工作時，可以有效地進行節(jié)點替換工作［3］。但是，由于節(jié)點自由度高，組網(wǎng)過程中的組播協(xié)議往往存在巨大的局限性，難以適應(yīng)實際需求。對此，Zhang Minglong 等人［4］通過引入地址分配機制來改善組播協(xié)議，采用動態(tài)尋址理念，在小規(guī)模無線移動自組織網(wǎng)的實踐中取得了成功。不過由于沒有引入隨機機制，導(dǎo)致大規(guī)模部署時組播協(xié)議尋址難以有效進行尋址工作;Bettstetter C.等人［5］通過改善組播路由節(jié)點的超球體流動機制，采取基于位置的路由算法，使得網(wǎng)絡(luò)的擴展性大大提高。但是在節(jié)點流動性增加的情況下，會導(dǎo)致網(wǎng)絡(luò)控制開銷急速地增加;呂政等人［6］采取虛擬機制，建立了節(jié)點/路由的一一對應(yīng)關(guān)系，有效地控制了網(wǎng)絡(luò)開銷。但是由于未能在擴展性上有突破，導(dǎo)致節(jié)點的分組投遞情況不容樂觀。

為了克服上述不足，本文通過引入超球面優(yōu)良的拓撲特性，采用群論中的直積方法作為組播信號的依據(jù)，通過積極映射坐標，實現(xiàn)數(shù)據(jù)的有效組播，降低了網(wǎng)絡(luò)的控制開銷與能量開銷。

1 無線移動自組織網(wǎng)絡(luò)組播問題與超球面拓撲

在實現(xiàn)無線移動自組織網(wǎng)的分組通信中，任何節(jié)點都可以寫成是某組的組成部分，可以在一定時間內(nèi)隸屬于這個分組，同時一旦超過了生命周期，就可以離開這個分組［7-9］。為了實現(xiàn)網(wǎng)絡(luò)拓撲結(jié)構(gòu)的慣例，源節(jié)點需要讓鄰居節(jié)點知曉其在網(wǎng)絡(luò)中的地位，然后某個分組需要周期性地知道該節(jié)點詳細的拓撲信息，而分組中其他節(jié)點將會全部保留該節(jié)點的分組信息。因此可以采用超球面拓撲結(jié)構(gòu)［10］來具體描述和表示。

對于一個n 維的超球面而言，其組成節(jié)點至少有2n 個［11］。每個節(jié)點的具體坐標可以用一串長度為n的向量表示:x=［x1，x2，...，xn］。如果2 個節(jié)點x，y處于鄰接狀態(tài)，則它們的組成向量［x1，x2，...，xn］和［y1，y2，...，yn］的有效距離為1。因此采用超球面可以方便地表現(xiàn)源節(jié)點的n 種不同的狀態(tài)，由于超球面的維度是可以無限增加的，因此源節(jié)點攜帶的信息的可擴展性也會大大提高。

網(wǎng)絡(luò)節(jié)點組播信息的超球面拓撲由群Zn×Zn2表示，其中Zn為質(zhì)數(shù)n 的循環(huán)群，Zn2 為n 的無限維交換直積。因此元素的組成集合S 由式(1)構(gòu)成:

其中，s1，s-1，s2，s-2為0，1 組成的二進制隨機數(shù)。則組播信息發(fā)送節(jié)點的坐標X 由式(2)決定:

其中，Zn由網(wǎng)絡(luò)初始狀態(tài)的n 個節(jié)點的狀態(tài)所決定。

依據(jù)模型(2)，定義組播信息生成結(jié)構(gòu):

根據(jù)式(3)～式(6)的超球面的基本解析式，無線移動自組織網(wǎng)絡(luò)中的任意節(jié)點都至少有4 個鄰接成員，通過與元素的組成集合S 進行計算，可以得到這4 個鄰接成員的解析表達式。而S 中的元素一共可以組成n×2n的排列組合，其中每種組合都有n ×2n+1條鄰接向量。顯然這些向量對應(yīng)的頂點和邊可以組成哈密爾頓回路。則節(jié)點對應(yīng)的哈密爾頓環(huán)的邊的解析式f 為:

而任意節(jié)點的逆節(jié)點的解析表達式f 為:

由于f 和f-正交，且兩者之間的元素也是正交關(guān)系，因此任意節(jié)點與其逆節(jié)點同屬于哈密爾頓環(huán)。

顯然，對于任意的n 維長度的源節(jié)點而言，與其哈密爾頓環(huán)fn都可以通過正交的辦法得到與相鄰的n×2n個節(jié)點的全部消息，而自身的消息也可以有n×2n+1種方式與周圍的n×2n個節(jié)點相交換。

2 基于混沌映射組播技術(shù)的組播算法

由于整個超球面處于同一無線移動自組織網(wǎng)內(nèi)，因此對于任意節(jié)點而言，其狀態(tài)都是混沌狀態(tài)，可以將源節(jié)點映射為超球面上的幾何點，其攜帶的分組信息由幾何點對應(yīng)的哈密爾頓環(huán)及其逆環(huán)所決定。每個節(jié)點對應(yīng)的鄰接節(jié)點至少是4 個，因此整個分組信息由4 層結(jié)構(gòu)所構(gòu)成:第1 層由根節(jié)點構(gòu)成，主要用來維護分簇信息;第2 層由活動節(jié)點構(gòu)成，主要用來維持網(wǎng)絡(luò)拓撲結(jié)構(gòu)穩(wěn)定的開銷;第3 層由網(wǎng)絡(luò)中一般節(jié)點所構(gòu)成，它們和根節(jié)點是正交關(guān)系;第4 層由鄰接節(jié)點構(gòu)成，主要用來進行信息的存儲。

由上述群論規(guī)則可知:當(dāng)一個節(jié)點發(fā)送分組信息時，消息首先在第1 層構(gòu)成的樹中進行分發(fā)，依次被2 層、3 層、4 層的節(jié)點所感知。當(dāng)整個消息隨著哈密爾頓環(huán)返回自身時，整個路由維護過程結(jié)束，此時網(wǎng)絡(luò)拓撲結(jié)構(gòu)處于最穩(wěn)定的狀態(tài)。整個算法步驟如下:

Step1 源節(jié)點初始化，啟動4 層樹的構(gòu)造過程，構(gòu)造完成轉(zhuǎn)Step2;

Step2 在一層樹中，接收到源節(jié)點分發(fā)信息的節(jié)點首先映射為超球面節(jié)點，當(dāng)全部節(jié)點接收到信息時，轉(zhuǎn)入Step3;反之，經(jīng)過一個周期以后，丟棄信息;

Step3 二層樹接收到一層樹轉(zhuǎn)發(fā)的源節(jié)點信息后，按照逆環(huán)方式將分組信息告知該層次的節(jié)點，轉(zhuǎn)Step4;

Step4 當(dāng)一般節(jié)點收到分組信息時，檢測自身是否和源節(jié)點處于正交狀態(tài)，當(dāng)且僅當(dāng)處于正交狀態(tài)時，通過環(huán)反饋給源節(jié)點并轉(zhuǎn)Step5，否則算法結(jié)束;

Step5 鄰接節(jié)點通過收到的信息，將存儲有源節(jié)點信息的節(jié)點進行更新，算法結(jié)束。

整個流程如圖1 所示。

圖1 算法流程圖

3 算法仿真

利用OPNET 仿真工具來測試本文路由性能。為了體現(xiàn)所提技術(shù)的優(yōu)異性，將當(dāng)前性能較好的路由視為對照組:文獻［13］中的AODV 算法，并引入平均端到端時延、網(wǎng)絡(luò)平均負載與分組投遞率作為量化質(zhì)量。具體仿真參數(shù)如表1 所示。

表1 仿真參數(shù)表

圖2 是在網(wǎng)絡(luò)節(jié)點規(guī)模大幅度增加的情況下，無線自組織網(wǎng)絡(luò)中任意2 個節(jié)點的平均端到端時延的情況。從圖中可以看到，隨著網(wǎng)絡(luò)規(guī)模的不斷增大，整體上看AODV 算法和本算法的平均端到端時延都會隨之提高。但是由于本算法引入了混沌映射機制，通過逆環(huán)投遞的方式，減少了分組投遞中經(jīng)過的節(jié)點數(shù)量。因此本算法的平均端到端時延要好于AODV算法。

圖2 不同算法的端到端時延

圖3 顯示了網(wǎng)絡(luò)節(jié)點規(guī)模增加的情況下，整個網(wǎng)絡(luò)開銷情況。從圖中可以看到，雖然本算法和AODV算法隨著網(wǎng)絡(luò)規(guī)模增大，網(wǎng)絡(luò)控制開銷都會隨之增大;但是本算法由于節(jié)點采用正交方式與周圍節(jié)點建立聯(lián)系，大大降低了單次聯(lián)系過程中的能量開銷。因此隨著加入網(wǎng)絡(luò)的自組織節(jié)點數(shù)量的遞增，本算法的優(yōu)勢愈發(fā)明顯。

圖3 網(wǎng)絡(luò)控制開銷測試

圖4 顯示了隨著網(wǎng)絡(luò)節(jié)點移動速度的加快，網(wǎng)絡(luò)中整體的分組投遞率的情況。依圖可知，隨著網(wǎng)絡(luò)移動性能的不斷提高，網(wǎng)絡(luò)的拓撲變化速度也隨之提高。但是采用本算法網(wǎng)絡(luò)中的網(wǎng)絡(luò)投遞率始終優(yōu)于AODV 算法。這是因為由于采用超球面映射的方式，提高了網(wǎng)絡(luò)節(jié)點的混沌度。因此網(wǎng)絡(luò)節(jié)點之間的聯(lián)系也更加密切，用于控制網(wǎng)絡(luò)拓撲結(jié)構(gòu)的信息分組數(shù)量將大大降低，整個網(wǎng)絡(luò)分組投遞水平也隨之提高。

圖4 分組投遞率對比

4 結(jié)束語

隨著網(wǎng)絡(luò)數(shù)據(jù)及控制難度水平的不斷增加，帶來了越來越多的網(wǎng)絡(luò)組播問題。本文基于混沌映射組播技術(shù)，采用映射的方式不斷對源節(jié)點進行正交優(yōu)化處理，然后通過樹狀結(jié)構(gòu)實現(xiàn)對全網(wǎng)組播信息的維護，大大降低了平均端到端時延，提高了分組投遞率，也降低了終端的網(wǎng)絡(luò)控制開銷水平，對移動互聯(lián)網(wǎng)的部署具有較強的實際指導(dǎo)意義。

［1］楊林，鄭剛.無線多跳網(wǎng)中具有網(wǎng)絡(luò)編碼意識的機會路由協(xié)議［J］.清華大學(xué)學(xué)報(自然科學(xué)版)，2010，50(10):1713-1717.

［2］Chi Kaikai，Jiang Xiaohong，Ye Baoliu，et al.Efficient network coding-based loss recovery for reliable multicast in wireless networks［J］.IEICE Transactions on Communication，2014，93(4):971-981.

［3］Kamal A E，Mohandespour M.Network coding-basedprotection［J］.Optical Switching and Networking，2014，11:189-201.

［4］Zhang Minglong，Lu Lu，Liew Soung-Chang.An optimal decoding strategy for physical-layer network coding over multipath fading channels［J］.IEEE Transactions on Vehicular Technology，2015，64(9):4365-4372.

［5］Bettstetter C，Resta G，Santi P.The node distribution of the random waypoint mobility model for wireless Ad Hoc networks［J］.IEEE Transactions on Mobile Computing，2013，2(3):257-269.

［6］呂政，余志軍，劉海濤.協(xié)作通信中聯(lián)合信道-網(wǎng)絡(luò)組播的性能分析與資源分配［J］.西安交通大學(xué)學(xué)報，2012，46(4):83-87.

［7］Ahlswede R，Cai N，Li S Y R，et al.Network informationflow［J］.IEEE Transactions on Information Theory，2014，46(4):1204-1216.

［8］Zhao Wenrui，Ammar M，Zegura E.Controlling the mobility of multiple data transport ferries in a delay tolerant network［C］// Proc.of IEEE INFOCOM.2005，2:1407-1418.

［9］Altman E，Prakash A，Basar T，et al.Optimal activation and transmission control in delay tolerant networks［C］//Proc.of IEEE INFOCOM.2010:1-5.

［10］El-Azouzi R，Pellegrini F D，Habib B A Sidi，et al.Evolutionary forwarding games in delay tolerant networks［J］.Computer Networks，2013，57(4):1003-1018.

［11］Demmer M，Brewer E，F(xiàn)all K，et al.Implementing Delay Tolerant Networking［R］.Technical Report，IRB-TR-04-020，Intel Corporation，2014.

［12］Vahdat A，Becker D.EpidemicRouting for Partially Connected Ad Hoc Networks［R］.Technical Report CS-200006，Duke University，2010.

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