支持網(wǎng)絡(luò)編碼的認(rèn)知無(wú)線自組網(wǎng)拓?fù)淇刂扑惴?/h1>
2013-01-06 10:56:28劉軍孫茜王英梅葉寧沙明博
通信學(xué)報(bào) 2013年5期
劉軍，孫茜，王英梅，葉寧，沙明博
（1.東北大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110819；2.北方交大計(jì)算所，北京 100029；3.奧維通信股份有限公司，遼寧 沈陽(yáng)110179）
1 引言
Ad hoc網(wǎng)絡(luò)[1]是由一組具有無(wú)線收發(fā)裝置的移動(dòng)終端組成的多跳臨時(shí)性自治系統(tǒng)。該網(wǎng)絡(luò)具有無(wú)中心和自組織性、節(jié)點(diǎn)功能不同、傳輸帶寬受限、拓?fù)鋭?dòng)態(tài)變化等特點(diǎn)。近年來(lái)，隨著認(rèn)知網(wǎng)絡(luò)[2,3]的迅速發(fā)展，很多研究者將網(wǎng)絡(luò)認(rèn)知技術(shù)融入無(wú)線自組網(wǎng)中，使其可以根據(jù)條件變化和發(fā)生的事件（如端到端的業(yè)務(wù)量）按照推理和先驗(yàn)知識(shí)進(jìn)行自適應(yīng)，從而實(shí)現(xiàn)對(duì)拓?fù)浣Y(jié)構(gòu)的自管理、自優(yōu)化、自監(jiān)控、自修理、自保護(hù)和自治愈等。
隨著無(wú)線通信技術(shù)的日益發(fā)展，認(rèn)知無(wú)線自組網(wǎng)中的業(yè)務(wù)逐漸增多，有限的帶寬成為限制其通信的主要因素。Ahlswede于2000年提出了網(wǎng)絡(luò)編碼技術(shù)[4]，其核心思想是節(jié)點(diǎn)將來(lái)自不同鏈路的數(shù)據(jù)分組進(jìn)行編碼組合，在實(shí)現(xiàn)路由功能的同時(shí)實(shí)現(xiàn)編碼功能。網(wǎng)絡(luò)編碼技術(shù)[5,6]可以提高網(wǎng)絡(luò)吞吐量，增加多播容量，節(jié)省節(jié)點(diǎn)能耗，增加網(wǎng)絡(luò)安全性。因此，網(wǎng)絡(luò)編碼技術(shù)可以解決網(wǎng)絡(luò)中帶寬受限的問題，提高無(wú)線資源復(fù)用率。
由于網(wǎng)絡(luò)編碼是一種新興的技術(shù)，目前絕大多數(shù)拓?fù)淇刂扑惴╗7,8]都不能支持網(wǎng)絡(luò)編碼的應(yīng)用。直到2007年，Chi等人針對(duì)有線網(wǎng)絡(luò)提出一種支持網(wǎng)絡(luò)編碼的多播網(wǎng)絡(luò)拓?fù)錁?gòu)建方案[9]。論文中將該問題作為非線性規(guī)劃問題，證明其是NP問題，提出了2個(gè)啟發(fā)式算法LDE(link deletion and exchange)和LAE(link addition and exchange)。在2011年，Li在其基礎(chǔ)上，將該問題制定為特殊的K連通問題，利用遺傳算法提出一種支持網(wǎng)絡(luò)編碼的拓?fù)湓O(shè)計(jì)方案[10]，但是，其優(yōu)化目標(biāo)較為簡(jiǎn)單，需要更加深入的研究。因此，構(gòu)建支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴ㄈ匀痪哂袕V闊的研究空間。
2 支持網(wǎng)絡(luò)編碼的無(wú)線自組網(wǎng)拓?fù)淇刂扑惴?/h2>
網(wǎng)絡(luò)編碼能夠順利進(jìn)行的前提條件之一是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)存在冗余性，Ahlswede所用的著名蝶形網(wǎng)絡(luò)很好地說(shuō)明了這個(gè)問題。針對(duì)每個(gè)多播業(yè)務(wù)，若源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)都存在K條邊分離路徑，那么采用網(wǎng)絡(luò)編碼技術(shù)可以實(shí)現(xiàn)多播傳輸?shù)臉O限傳輸速率。如圖1所示的2冗余網(wǎng)絡(luò)（源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)都存在2條邊分離路徑），s是源節(jié)點(diǎn)，t1、t2、t3是目的節(jié)點(diǎn)，a和b是要傳輸?shù)臄?shù)據(jù)分組，鏈路具有單位帶寬。若源節(jié)點(diǎn)s對(duì)數(shù)據(jù)分組a和b進(jìn)行網(wǎng)絡(luò)編碼后再傳輸，在鏈路s-u2、u2-t1、u2-t3上可以實(shí)現(xiàn)傳輸速率2bit/s。
基于以上思想，為采用網(wǎng)絡(luò)編碼技術(shù)解決無(wú)線自組網(wǎng)中帶寬受限的問題，提出了支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴?TCBNC, topology control algorithm backing for network coding)。算法主要分為3個(gè)階段：初始拓?fù)錁?gòu)建、拓?fù)鋬?yōu)化和拓?fù)浠謴?fù)。
圖1 2冗余網(wǎng)絡(luò)
2.1 初始拓?fù)錁?gòu)建
無(wú)線自組網(wǎng)中的通信類型多種多樣，在拓?fù)錁?gòu)建過程中，需要在面向業(yè)務(wù)的框架下設(shè)計(jì)滿足多業(yè)務(wù)需求的網(wǎng)絡(luò)拓?fù)?，適應(yīng)其多元化的特點(diǎn)。針對(duì)網(wǎng)絡(luò)中的單播業(yè)務(wù)，利用最短路徑算法選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑，構(gòu)建網(wǎng)絡(luò)拓?fù)洌会槍?duì)網(wǎng)絡(luò)中的多播業(yè)務(wù)，利用基于網(wǎng)絡(luò)編碼的最短路徑算法選擇源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的K（K值不同，最大傳輸速率不同）條邊分離路徑，構(gòu)建K冗余網(wǎng)絡(luò)。
針對(duì)無(wú)線自組網(wǎng)中的多播業(yè)務(wù)（假設(shè)都為單源多播業(yè)務(wù)），如圖2所示，設(shè)K=2，源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)集為D，其余為中間節(jié)點(diǎn)集M?；诰W(wǎng)絡(luò)編碼的最短路徑算法步驟如下。
圖2 基于網(wǎng)絡(luò)編碼的最短路徑算法
Step1在初始拓?fù)鋱DG（如圖2(a)）中，使用最短路徑算法搜索源節(jié)點(diǎn)s到每個(gè)中間節(jié)點(diǎn)的最短路徑，得到最短路拓?fù)鋱DG′。如圖2(b)所示，源節(jié)點(diǎn)到中間節(jié)點(diǎn)的最短路徑分別為sm1、sm2、sm3、sm2m4、sm5。目的節(jié)點(diǎn)的輸入鏈路為m1d1、m3d1、m4d1、m3d2、m4d2、m5d2、m4d3、m5d3。
定義1（最短路拓?fù)鋱D）：在單源多播網(wǎng)絡(luò)初始拓?fù)鋱DG中，s為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)集，采用最短路徑算法搜索源節(jié)點(diǎn)到每個(gè)中間節(jié)點(diǎn)的最短路徑，再加上G中所有目的節(jié)點(diǎn)的輸入鏈路構(gòu)成的拓?fù)錇樽疃搪吠負(fù)鋱DG′。
Step 2計(jì)算最短路拓?fù)鋱DG′中源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di（di∈D，i=1,2,···,|D|）的邊分離路徑數(shù)及最小值m。在圖2(b)中，計(jì)算得m=2。
定義2（邊分離路徑）：由目的節(jié)點(diǎn)的輸入鏈路及輸入鏈路另一端點(diǎn)到源節(jié)點(diǎn)的最短路徑構(gòu)成的彼此之間沒有重合鏈路的路徑。在圖2(b)中，對(duì)于目的節(jié)點(diǎn)d1，邊分離路徑為sm1d1、sm3d1、sm2m4d1。
Step 3如果K≤m，轉(zhuǎn)到Step4；否則，轉(zhuǎn)到Step5。
Step 4在最短路拓?fù)鋱DG′中，對(duì)每個(gè)目的節(jié)點(diǎn)重復(fù)采用最短路算法，搜索從源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的K條最短邊分離路徑，構(gòu)建拓?fù)鋱DG0，如圖2(c)所示，可以找到源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的2條邊分離路徑，算法結(jié)束。
Step 5在最短路拓?fù)鋱DG′中，對(duì)每個(gè)目的節(jié)點(diǎn)重復(fù)采用最短路算法，搜索從源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的m條最短邊分離路徑。
Step 6對(duì)于每個(gè)目的節(jié)點(diǎn)di，將Step5中搜索到的m條最短邊分離路徑中的鏈路在初始拓?fù)鋱DG中刪除得新初始拓?fù)鋱DG′′，在G′′中重復(fù)使用以上算法，搜索源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的K-m條最短邊分離路徑，算法結(jié)束。
綜上所述，利用不同的算法可以為不同的業(yè)務(wù)選擇合適的路徑或路徑簇，構(gòu)建初始拓?fù)鋱DG0。不同路徑或路徑簇之間可能存在重合鏈路，增加了網(wǎng)絡(luò)編碼的應(yīng)用機(jī)會(huì)。如果在重合鏈路的端節(jié)點(diǎn)采用網(wǎng)絡(luò)編碼技術(shù)，可以提高網(wǎng)絡(luò)吞吐量。注意，算法中的“路徑”可能代表時(shí)延、帶寬、能耗等。
2.2 拓?fù)鋬?yōu)化
在初始拓?fù)錁?gòu)建階段，構(gòu)建的拓?fù)浣Y(jié)構(gòu)具有很大的冗余性。因此，需要在保證網(wǎng)絡(luò)編碼應(yīng)用的前提下，對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行優(yōu)化，節(jié)省網(wǎng)絡(luò)能量消耗。如圖3(a)所示的拓?fù)鋱DG0，K=2，網(wǎng)絡(luò)中包括多播業(yè)務(wù)Q1（源節(jié)點(diǎn)s1，目的節(jié)點(diǎn)d11、d12、d13，邊分離路徑簇為s1m1d11、s1m3d11、s1m3d12、s1m2m4d12、s1m2m4d13、s1s3d21d13）、Q2（源節(jié)點(diǎn)s2，目的節(jié)點(diǎn)d21、d22，邊分離路徑簇為s2d21、s2s3d21、s2m2m4d22、s2s3d22）和單播業(yè)務(wù) Q3（源節(jié)點(diǎn)s3、目的節(jié)點(diǎn)d3、最短路徑為s3d3）。拓?fù)鋬?yōu)化階段的步驟如下。
圖3 拓?fù)鋬?yōu)化
1) 構(gòu)建臨時(shí)拓?fù)?/p>
在拓?fù)鋱DG0中，選擇效率指標(biāo)最大的鏈路lmax。從 G0中刪除鏈路lmax，獲得臨時(shí)拓?fù)鋱D GT，如圖3(b)所示。
定義3 (效率指標(biāo))：鏈路上單位流量的能量消耗。
2) 探測(cè)臨時(shí)拓?fù)鋱D
①探測(cè)臨時(shí)拓?fù)鋱DGT中的多播業(yè)務(wù)是否滿足K冗余。若滿足，轉(zhuǎn)到②；否則，說(shuō)明鏈路lmax不能被刪除，在剩余網(wǎng)絡(luò)拓?fù)洌ú话ㄦ溌穕max）中重復(fù)1)。從圖3(b)可以看出，GT滿足2冗余條件。
②為鏈路lmax上的業(yè)務(wù)重新選擇合適的路徑，判斷網(wǎng)絡(luò)總能耗是否減小。若減小，將臨時(shí)拓?fù)鋱D GT作為新初始拓?fù)鋱D G0；否則，說(shuō)明鏈路lmax不能被刪除，在剩余網(wǎng)絡(luò)拓?fù)渲兄貜?fù)1）。在圖3中，鏈路lmax被刪除后，其上的單播業(yè)務(wù)Q3可以選擇新的路徑s3d21d3，假設(shè)計(jì)算后，網(wǎng)絡(luò)的總能耗減小，因此，將臨時(shí)拓?fù)鋱DGT作為新初始拓?fù)鋱DG0。
上面的過程重復(fù)進(jìn)行，直到拓?fù)鋱D G0中不存在能被刪除的鏈路，算法結(jié)束。
2.3 拓?fù)浠謴?fù)
Ad hoc網(wǎng)絡(luò)中存在一些拓?fù)潢P(guān)鍵點(diǎn)，一旦網(wǎng)絡(luò)認(rèn)知到某個(gè)關(guān)鍵點(diǎn)發(fā)生故障或受到安全威脅，與關(guān)鍵點(diǎn)相連的鏈路會(huì)失效，網(wǎng)絡(luò)很容易被分割成不連通的子網(wǎng)。為了保證網(wǎng)絡(luò)可靠、安全運(yùn)行，提出基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法，主要思想是采用與失效鏈路不在同一路徑簇中且開銷最小的鏈路恢復(fù)網(wǎng)絡(luò)的連通性，以保證源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)間的路徑是邊分離的，繼續(xù)支持網(wǎng)絡(luò)編碼的應(yīng)用。
定義4(關(guān)鍵點(diǎn))：網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)失效可能導(dǎo)致網(wǎng)絡(luò)被分割成多個(gè)部分，這樣的節(jié)點(diǎn)稱為網(wǎng)絡(luò)拓?fù)潢P(guān)鍵點(diǎn)，如圖4(a)所示，節(jié)點(diǎn)a是關(guān)鍵點(diǎn)。
以圖 4為例說(shuō)明基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法。
1) 收集局部網(wǎng)絡(luò)拓?fù)湫畔?/p>
收集關(guān)鍵點(diǎn)a周圍的兩跳網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑢儆谕宦窂酱刂械逆溌穭潪橐唤M，得到3個(gè)不同的鏈路組L1、L2、L3，如圖4(a)所示。
2) 恢復(fù)鏈路組的連通性
隨機(jī)選取鏈路組L1，當(dāng)關(guān)鍵點(diǎn)a失效時(shí)，路徑b1ab6的連通性遭到破壞，將鏈路組L1中的鏈路開銷置為無(wú)窮大，利用最短路徑算法搜索節(jié)點(diǎn)b1到b6的新路徑b1b4b3b6，添加到局部網(wǎng)絡(luò)中，如圖 4(b)所示。然后，探測(cè)此時(shí)L2中路徑連通性是否遭到破壞，從圖4(b)中看出，可以找到新路徑b4b1b2b5，連通性不再受影響；否則，采用最短路徑算法恢復(fù)連通性。對(duì)于剩余鏈路組重復(fù)使用以上算法。注意，鏈路組L3的連通性暫時(shí)不能恢復(fù)。
3) 恢復(fù)局部網(wǎng)絡(luò)連通性
計(jì)算此時(shí)關(guān)鍵點(diǎn)a失效時(shí)局部網(wǎng)絡(luò)中簇的個(gè)數(shù)N。若N不為1，添加能使簇個(gè)數(shù)減小的最小開銷鏈路li（i=1，2，3，···），直到N=1，如圖 4(c)中鏈路l1；否則，算法結(jié)束。網(wǎng)絡(luò)進(jìn)行拓?fù)浠謴?fù)后如圖4(c)所示。
2.4 算法支持網(wǎng)絡(luò)編碼的實(shí)例
以拓?fù)鋱D3（b）中多播業(yè)務(wù)Q1為例，說(shuō)明網(wǎng)絡(luò)編碼在拓?fù)浣Y(jié)構(gòu)中的具體體現(xiàn)。設(shè)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送信息a、b，目的節(jié)點(diǎn)d11的邊分離路徑簇為s1m1d11、s1m3d11，目的節(jié)點(diǎn)d12的邊分離路徑簇為s1m3d12、s1m2m4d12，這 2個(gè)路徑簇構(gòu)成了網(wǎng)絡(luò)編碼的典型應(yīng)用環(huán)境——蝶形網(wǎng)絡(luò)。在源節(jié)點(diǎn)處對(duì)a、b進(jìn)行網(wǎng)絡(luò)編碼，將編碼后的信息在重合鏈路s1m3、m3d11、m3d12上傳輸，在其他鏈路上傳輸a或b，可保證目的節(jié)點(diǎn)d11、d12成功解碼出信息a、b。同樣方法，可保證目的節(jié)點(diǎn)d13成功收到a、b。不論編碼方法如何，構(gòu)建的拓?fù)浣Y(jié)構(gòu)都能夠支持網(wǎng)絡(luò)編碼的應(yīng)用，并確保成功解碼。
3 仿真分析
3.1 有效性
采用NS2網(wǎng)絡(luò)模擬軟件進(jìn)行測(cè)試，設(shè)置網(wǎng)絡(luò)中同時(shí)存在單播和多播業(yè)務(wù)，對(duì)比在TCBNC和基于多播樹的拓?fù)淇刂扑惴?TCBMT，topology control algorithm based on multicast tree)的控制下，網(wǎng)絡(luò)分組投遞率、吞吐量、節(jié)點(diǎn)平均能耗隨信宿節(jié)點(diǎn)數(shù)增加時(shí)的變化情況，仿真參數(shù)如表1所示。
圖4 基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法
表1 仿真參數(shù)
定義5(網(wǎng)絡(luò)吞吐量)：指一組特定數(shù)據(jù)在特定時(shí)間段經(jīng)過特定路徑所傳輸?shù)男畔⒘康膶?shí)際測(cè)量值。
定義6(節(jié)點(diǎn)平均能耗)：指網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在運(yùn)行過程中所消耗的能量的平均值。在計(jì)算過程中，考慮了網(wǎng)絡(luò)運(yùn)行過程中影響節(jié)點(diǎn)能量的所有因素，其計(jì)算公式為
從圖5～圖7可以看出，TCBNC能夠提高網(wǎng)絡(luò)的分組投遞率和網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)的節(jié)點(diǎn)平均能耗。這是因?yàn)門CBNC能夠構(gòu)建出支持網(wǎng)絡(luò)編碼的拓?fù)浣Y(jié)構(gòu)，增加了節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼的機(jī)會(huì)，因此提高了網(wǎng)絡(luò)分組投遞率和吞吐量，節(jié)省了節(jié)點(diǎn)平均能耗。隨著網(wǎng)絡(luò)中信宿節(jié)點(diǎn)數(shù)的增加，TCBNC控制的網(wǎng)絡(luò)中更多的節(jié)點(diǎn)參與網(wǎng)絡(luò)編碼，增大編碼機(jī)會(huì)的同時(shí)提高了解碼成功概率，大量數(shù)據(jù)分組能夠成功到達(dá)目的節(jié)點(diǎn)，網(wǎng)絡(luò)的分組投遞率幾乎不變，吞吐量逐漸增大，節(jié)點(diǎn)平均能耗逐漸增大；而TCBMT控制的網(wǎng)絡(luò)中由于數(shù)據(jù)分組的逐漸增多，網(wǎng)絡(luò)阻塞、數(shù)據(jù)分組丟失和重傳現(xiàn)象十分嚴(yán)重，網(wǎng)絡(luò)性能逐漸下降。
圖5 分組投遞率隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
圖6 網(wǎng)絡(luò)吞吐量隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
圖7 節(jié)點(diǎn)平均能耗隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
3.2 抗毀性
仿真環(huán)境與探測(cè)有效性時(shí)一致，信宿節(jié)點(diǎn)數(shù)設(shè)為10個(gè)。對(duì)比在TCBNC拓?fù)淇刂魄昂?，網(wǎng)絡(luò)性能指標(biāo)隨失效關(guān)鍵點(diǎn)數(shù)增加時(shí)的變化情況。
圖8 分組投遞率隨失效關(guān)鍵點(diǎn)數(shù)變化的對(duì)比
從圖8和圖9可以看出，隨著網(wǎng)絡(luò)中失效關(guān)鍵點(diǎn)數(shù)的增加，支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴軌蝻@著提高網(wǎng)絡(luò)的分組投遞率和吞吐量，改善網(wǎng)絡(luò)的性能。一方面，TCBNC通過建立新鏈路，保證了網(wǎng)絡(luò)的連通性，數(shù)據(jù)分組能夠順利到達(dá)目的節(jié)點(diǎn)；另一方面，修復(fù)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能夠繼續(xù)支持網(wǎng)絡(luò)編碼的應(yīng)用，減少了數(shù)據(jù)分組的傳輸次數(shù)，提高網(wǎng)絡(luò)吞吐量。因此，TCBNC使網(wǎng)絡(luò)性能得到了有效的恢復(fù)，增強(qiáng)了網(wǎng)絡(luò)的抗毀性。
圖9 網(wǎng)絡(luò)吞吐量隨失效關(guān)鍵點(diǎn)數(shù)變化的對(duì)比
4 復(fù)雜度分析
TCBNC的復(fù)雜度小于對(duì)比TCBMT的復(fù)雜度，主要體現(xiàn)在多播業(yè)務(wù)的拓?fù)錁?gòu)建過程中利用了最短路網(wǎng)絡(luò)。圖 10所示為初始網(wǎng)絡(luò)拓?fù)鋱D，源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)為d，K=2，利用TCBMT搜索兩條最短路徑需要的計(jì)算次數(shù)為 2×(15+14+···+2)= 238；利用 TCBNC構(gòu)建最短路網(wǎng)絡(luò)的計(jì)算次數(shù)為14+13+···+2=104，如圖 11 所示，在其基礎(chǔ)上搜索一條最短路徑的計(jì)算次數(shù)為 15，總計(jì)算次數(shù)為104+2×15=134，節(jié)約了 43.7%的計(jì)算量。并且，隨著目的節(jié)點(diǎn)數(shù)、K值的增加，算法具有更低的復(fù)雜度。
圖10 初始網(wǎng)絡(luò)拓?fù)鋱D
圖11 最短路網(wǎng)絡(luò)拓?fù)鋱D
5 結(jié)束語(yǔ)
本文提出一種支持網(wǎng)絡(luò)編碼的認(rèn)知無(wú)線自組網(wǎng)拓?fù)淇刂扑惴?TCBNC，針對(duì)不同的業(yè)務(wù)類型采用不同算法構(gòu)建支持網(wǎng)絡(luò)編碼的初始拓?fù)鋱D，然后通過逐個(gè)刪除冗余鏈路進(jìn)行拓?fù)鋬?yōu)化，最后提出解決關(guān)鍵點(diǎn)失效問題的拓?fù)浠謴?fù)算法。算法支持網(wǎng)絡(luò)編碼的應(yīng)用，增強(qiáng)了通信的有效性和抗毀性。另外，算法復(fù)雜度不大，在節(jié)點(diǎn)移動(dòng)或信道環(huán)境變化時(shí)仍能適用。在未來(lái)的工作中，將考慮鏈路失效的情況，重構(gòu)支持網(wǎng)絡(luò)編碼的拓?fù)洹?/p>
[1] DE MORAIS CORDEIRO C, GOSSAIN H, AGRAWAL D P.Multicast over wireless mobile ad hoc network： present and future directions[J].IEEE Communications Society, 2003, 17(1)： 52-59.
[2] RABBACHIN A, QUEK T Q S, HYUNDONG S.Cognitive network interference[J].IEEE Journal on Communications, 2011, 29(2)：480-493.
[3] WANG Z D, WANG H Q, FENG G S.Cognitive networks and its layered cognitive architecture[A].2010 Fifth International Conference on Internet Computing for Science and Engineering(ICICSE)[C].Heilongjiang, China, 2012.145-148.
[4] LI B C, NIU D.Random network coding in peer-to-peer petworks：from theory to practice[J].Proceedings of the IEEE, 2010, 99(3)：513-523.
[5] AHN M H, KIM Y Y.Network coding-based multicast scheduling for throughput enhancement in wireless ad hoc network[A].2011 International Conference on Information Networking[C].Barcelona, Spain,2011.188-193.
[6] 胡金秀.多播網(wǎng)絡(luò)編碼算法研究[D].西安： 西安電子科技大學(xué),2010.HU J X.Study on Multicast Network Coding Algorithm[D].Xian： Xidian University, 2010.
[7] ZHANG T, YANG K, CHEN H H.Topology control for service-oriented wireless mesh networks[J].IEEE Wireless Communications, 2009, 16(4)： 64-71.
[8] YADU K K, KAKDE O G.Optimization based topology control for wireless ad hoc networks to meet QoS requirements[A].2010 29th IEEE Symposium on Reliable Distributed System[C].New Delhi, India, 2010.30-36.
[9] CHI K K, JIANG X H, HORIGUCHI S.Topology design of network-noding-based multicast networks[J].IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5)： 627-640.
[10] LI J K, PAN Y.Network coding driented topology design based on parallel genetic algorithm[A].2011 Fourth International Joint Conference on Computational Sciences and Optimization[C].Yunnan, China,2011.838-841.
猜你喜歡
低壓配網(wǎng)拓?fù)鋱D自動(dòng)成圖關(guān)鍵技術(shù)的研究與設(shè)計(jì)電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12 胖樹拓?fù)渲懈咝?shí)用的定制多播路由算法計(jì)算機(jī)研究與發(fā)展(2022年12期)2022-12-15 13:18:44 簡(jiǎn)單拓?fù)鋱D及幾乎交錯(cuò)鏈環(huán)補(bǔ)中的閉曲面數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22 用于超大Infiniband網(wǎng)絡(luò)的負(fù)載均衡多播路由計(jì)算機(jī)工程與應(yīng)用(2022年5期)2022-04-09 07:03:42 InfiniBand中面向有限多播表?xiàng)l目數(shù)的多播路由算法計(jì)算機(jī)研究與發(fā)展(2022年4期)2022-04-06 06:58:32 聚焦金屬關(guān)鍵點(diǎn)中學(xué)生數(shù)理化·中考版(2022年12期)2022-02-16 07:36:56 肉兔育肥抓好七個(gè)關(guān)鍵點(diǎn)今日農(nóng)業(yè)(2021年8期)2021-11-28 05:07:50 基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55 醫(yī)聯(lián)體要把握三個(gè)關(guān)鍵點(diǎn)中國(guó)衛(wèi)生(2014年2期)2014-11-12 13:00:16 鎖定兩個(gè)關(guān)鍵點(diǎn)——我這樣教《送考》語(yǔ)文知識(shí)(2014年7期)2014-02-28 22:00:26
劉軍，孫茜，王英梅，葉寧，沙明博
（1.東北大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110819；2.北方交大計(jì)算所，北京 100029；3.奧維通信股份有限公司，遼寧 沈陽(yáng)110179）
1 引言
Ad hoc網(wǎng)絡(luò)[1]是由一組具有無(wú)線收發(fā)裝置的移動(dòng)終端組成的多跳臨時(shí)性自治系統(tǒng)。該網(wǎng)絡(luò)具有無(wú)中心和自組織性、節(jié)點(diǎn)功能不同、傳輸帶寬受限、拓?fù)鋭?dòng)態(tài)變化等特點(diǎn)。近年來(lái)，隨著認(rèn)知網(wǎng)絡(luò)[2,3]的迅速發(fā)展，很多研究者將網(wǎng)絡(luò)認(rèn)知技術(shù)融入無(wú)線自組網(wǎng)中，使其可以根據(jù)條件變化和發(fā)生的事件（如端到端的業(yè)務(wù)量）按照推理和先驗(yàn)知識(shí)進(jìn)行自適應(yīng)，從而實(shí)現(xiàn)對(duì)拓?fù)浣Y(jié)構(gòu)的自管理、自優(yōu)化、自監(jiān)控、自修理、自保護(hù)和自治愈等。
隨著無(wú)線通信技術(shù)的日益發(fā)展，認(rèn)知無(wú)線自組網(wǎng)中的業(yè)務(wù)逐漸增多，有限的帶寬成為限制其通信的主要因素。Ahlswede于2000年提出了網(wǎng)絡(luò)編碼技術(shù)[4]，其核心思想是節(jié)點(diǎn)將來(lái)自不同鏈路的數(shù)據(jù)分組進(jìn)行編碼組合，在實(shí)現(xiàn)路由功能的同時(shí)實(shí)現(xiàn)編碼功能。網(wǎng)絡(luò)編碼技術(shù)[5,6]可以提高網(wǎng)絡(luò)吞吐量，增加多播容量，節(jié)省節(jié)點(diǎn)能耗，增加網(wǎng)絡(luò)安全性。因此，網(wǎng)絡(luò)編碼技術(shù)可以解決網(wǎng)絡(luò)中帶寬受限的問題，提高無(wú)線資源復(fù)用率。
由于網(wǎng)絡(luò)編碼是一種新興的技術(shù)，目前絕大多數(shù)拓?fù)淇刂扑惴╗7,8]都不能支持網(wǎng)絡(luò)編碼的應(yīng)用。直到2007年，Chi等人針對(duì)有線網(wǎng)絡(luò)提出一種支持網(wǎng)絡(luò)編碼的多播網(wǎng)絡(luò)拓?fù)錁?gòu)建方案[9]。論文中將該問題作為非線性規(guī)劃問題，證明其是NP問題，提出了2個(gè)啟發(fā)式算法LDE(link deletion and exchange)和LAE(link addition and exchange)。在2011年，Li在其基礎(chǔ)上，將該問題制定為特殊的K連通問題，利用遺傳算法提出一種支持網(wǎng)絡(luò)編碼的拓?fù)湓O(shè)計(jì)方案[10]，但是，其優(yōu)化目標(biāo)較為簡(jiǎn)單，需要更加深入的研究。因此，構(gòu)建支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴ㄈ匀痪哂袕V闊的研究空間。
2 支持網(wǎng)絡(luò)編碼的無(wú)線自組網(wǎng)拓?fù)淇刂扑惴?/h2>
網(wǎng)絡(luò)編碼能夠順利進(jìn)行的前提條件之一是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)存在冗余性，Ahlswede所用的著名蝶形網(wǎng)絡(luò)很好地說(shuō)明了這個(gè)問題。針對(duì)每個(gè)多播業(yè)務(wù)，若源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)都存在K條邊分離路徑，那么采用網(wǎng)絡(luò)編碼技術(shù)可以實(shí)現(xiàn)多播傳輸?shù)臉O限傳輸速率。如圖1所示的2冗余網(wǎng)絡(luò)（源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)都存在2條邊分離路徑），s是源節(jié)點(diǎn)，t1、t2、t3是目的節(jié)點(diǎn)，a和b是要傳輸?shù)臄?shù)據(jù)分組，鏈路具有單位帶寬。若源節(jié)點(diǎn)s對(duì)數(shù)據(jù)分組a和b進(jìn)行網(wǎng)絡(luò)編碼后再傳輸，在鏈路s-u2、u2-t1、u2-t3上可以實(shí)現(xiàn)傳輸速率2bit/s。
基于以上思想，為采用網(wǎng)絡(luò)編碼技術(shù)解決無(wú)線自組網(wǎng)中帶寬受限的問題，提出了支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴?TCBNC, topology control algorithm backing for network coding)。算法主要分為3個(gè)階段：初始拓?fù)錁?gòu)建、拓?fù)鋬?yōu)化和拓?fù)浠謴?fù)。
圖1 2冗余網(wǎng)絡(luò)
2.1 初始拓?fù)錁?gòu)建
無(wú)線自組網(wǎng)中的通信類型多種多樣，在拓?fù)錁?gòu)建過程中，需要在面向業(yè)務(wù)的框架下設(shè)計(jì)滿足多業(yè)務(wù)需求的網(wǎng)絡(luò)拓?fù)?，適應(yīng)其多元化的特點(diǎn)。針對(duì)網(wǎng)絡(luò)中的單播業(yè)務(wù)，利用最短路徑算法選擇源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑，構(gòu)建網(wǎng)絡(luò)拓?fù)洌会槍?duì)網(wǎng)絡(luò)中的多播業(yè)務(wù)，利用基于網(wǎng)絡(luò)編碼的最短路徑算法選擇源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的K（K值不同，最大傳輸速率不同）條邊分離路徑，構(gòu)建K冗余網(wǎng)絡(luò)。
針對(duì)無(wú)線自組網(wǎng)中的多播業(yè)務(wù)（假設(shè)都為單源多播業(yè)務(wù)），如圖2所示，設(shè)K=2，源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)集為D，其余為中間節(jié)點(diǎn)集M?；诰W(wǎng)絡(luò)編碼的最短路徑算法步驟如下。
圖2 基于網(wǎng)絡(luò)編碼的最短路徑算法
Step1在初始拓?fù)鋱DG（如圖2(a)）中，使用最短路徑算法搜索源節(jié)點(diǎn)s到每個(gè)中間節(jié)點(diǎn)的最短路徑，得到最短路拓?fù)鋱DG′。如圖2(b)所示，源節(jié)點(diǎn)到中間節(jié)點(diǎn)的最短路徑分別為sm1、sm2、sm3、sm2m4、sm5。目的節(jié)點(diǎn)的輸入鏈路為m1d1、m3d1、m4d1、m3d2、m4d2、m5d2、m4d3、m5d3。
定義1（最短路拓?fù)鋱D）：在單源多播網(wǎng)絡(luò)初始拓?fù)鋱DG中，s為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)集，采用最短路徑算法搜索源節(jié)點(diǎn)到每個(gè)中間節(jié)點(diǎn)的最短路徑，再加上G中所有目的節(jié)點(diǎn)的輸入鏈路構(gòu)成的拓?fù)錇樽疃搪吠負(fù)鋱DG′。
Step 2計(jì)算最短路拓?fù)鋱DG′中源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di（di∈D，i=1,2,···,|D|）的邊分離路徑數(shù)及最小值m。在圖2(b)中，計(jì)算得m=2。
定義2（邊分離路徑）：由目的節(jié)點(diǎn)的輸入鏈路及輸入鏈路另一端點(diǎn)到源節(jié)點(diǎn)的最短路徑構(gòu)成的彼此之間沒有重合鏈路的路徑。在圖2(b)中，對(duì)于目的節(jié)點(diǎn)d1，邊分離路徑為sm1d1、sm3d1、sm2m4d1。
Step 3如果K≤m，轉(zhuǎn)到Step4；否則，轉(zhuǎn)到Step5。
Step 4在最短路拓?fù)鋱DG′中，對(duì)每個(gè)目的節(jié)點(diǎn)重復(fù)采用最短路算法，搜索從源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的K條最短邊分離路徑，構(gòu)建拓?fù)鋱DG0，如圖2(c)所示，可以找到源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的2條邊分離路徑，算法結(jié)束。
Step 5在最短路拓?fù)鋱DG′中，對(duì)每個(gè)目的節(jié)點(diǎn)重復(fù)采用最短路算法，搜索從源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的m條最短邊分離路徑。
Step 6對(duì)于每個(gè)目的節(jié)點(diǎn)di，將Step5中搜索到的m條最短邊分離路徑中的鏈路在初始拓?fù)鋱DG中刪除得新初始拓?fù)鋱DG′′，在G′′中重復(fù)使用以上算法，搜索源節(jié)點(diǎn)s到每個(gè)目的節(jié)點(diǎn)di的K-m條最短邊分離路徑，算法結(jié)束。
綜上所述，利用不同的算法可以為不同的業(yè)務(wù)選擇合適的路徑或路徑簇，構(gòu)建初始拓?fù)鋱DG0。不同路徑或路徑簇之間可能存在重合鏈路，增加了網(wǎng)絡(luò)編碼的應(yīng)用機(jī)會(huì)。如果在重合鏈路的端節(jié)點(diǎn)采用網(wǎng)絡(luò)編碼技術(shù)，可以提高網(wǎng)絡(luò)吞吐量。注意，算法中的“路徑”可能代表時(shí)延、帶寬、能耗等。
2.2 拓?fù)鋬?yōu)化
在初始拓?fù)錁?gòu)建階段，構(gòu)建的拓?fù)浣Y(jié)構(gòu)具有很大的冗余性。因此，需要在保證網(wǎng)絡(luò)編碼應(yīng)用的前提下，對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行優(yōu)化，節(jié)省網(wǎng)絡(luò)能量消耗。如圖3(a)所示的拓?fù)鋱DG0，K=2，網(wǎng)絡(luò)中包括多播業(yè)務(wù)Q1（源節(jié)點(diǎn)s1，目的節(jié)點(diǎn)d11、d12、d13，邊分離路徑簇為s1m1d11、s1m3d11、s1m3d12、s1m2m4d12、s1m2m4d13、s1s3d21d13）、Q2（源節(jié)點(diǎn)s2，目的節(jié)點(diǎn)d21、d22，邊分離路徑簇為s2d21、s2s3d21、s2m2m4d22、s2s3d22）和單播業(yè)務(wù) Q3（源節(jié)點(diǎn)s3、目的節(jié)點(diǎn)d3、最短路徑為s3d3）。拓?fù)鋬?yōu)化階段的步驟如下。
圖3 拓?fù)鋬?yōu)化
1) 構(gòu)建臨時(shí)拓?fù)?/p>
在拓?fù)鋱DG0中，選擇效率指標(biāo)最大的鏈路lmax。從 G0中刪除鏈路lmax，獲得臨時(shí)拓?fù)鋱D GT，如圖3(b)所示。
定義3 (效率指標(biāo))：鏈路上單位流量的能量消耗。
2) 探測(cè)臨時(shí)拓?fù)鋱D
①探測(cè)臨時(shí)拓?fù)鋱DGT中的多播業(yè)務(wù)是否滿足K冗余。若滿足，轉(zhuǎn)到②；否則，說(shuō)明鏈路lmax不能被刪除，在剩余網(wǎng)絡(luò)拓?fù)洌ú话ㄦ溌穕max）中重復(fù)1)。從圖3(b)可以看出，GT滿足2冗余條件。
②為鏈路lmax上的業(yè)務(wù)重新選擇合適的路徑，判斷網(wǎng)絡(luò)總能耗是否減小。若減小，將臨時(shí)拓?fù)鋱D GT作為新初始拓?fù)鋱D G0；否則，說(shuō)明鏈路lmax不能被刪除，在剩余網(wǎng)絡(luò)拓?fù)渲兄貜?fù)1）。在圖3中，鏈路lmax被刪除后，其上的單播業(yè)務(wù)Q3可以選擇新的路徑s3d21d3，假設(shè)計(jì)算后，網(wǎng)絡(luò)的總能耗減小，因此，將臨時(shí)拓?fù)鋱DGT作為新初始拓?fù)鋱DG0。
上面的過程重復(fù)進(jìn)行，直到拓?fù)鋱D G0中不存在能被刪除的鏈路，算法結(jié)束。
2.3 拓?fù)浠謴?fù)
Ad hoc網(wǎng)絡(luò)中存在一些拓?fù)潢P(guān)鍵點(diǎn)，一旦網(wǎng)絡(luò)認(rèn)知到某個(gè)關(guān)鍵點(diǎn)發(fā)生故障或受到安全威脅，與關(guān)鍵點(diǎn)相連的鏈路會(huì)失效，網(wǎng)絡(luò)很容易被分割成不連通的子網(wǎng)。為了保證網(wǎng)絡(luò)可靠、安全運(yùn)行，提出基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法，主要思想是采用與失效鏈路不在同一路徑簇中且開銷最小的鏈路恢復(fù)網(wǎng)絡(luò)的連通性，以保證源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)間的路徑是邊分離的，繼續(xù)支持網(wǎng)絡(luò)編碼的應(yīng)用。
定義4(關(guān)鍵點(diǎn))：網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)失效可能導(dǎo)致網(wǎng)絡(luò)被分割成多個(gè)部分，這樣的節(jié)點(diǎn)稱為網(wǎng)絡(luò)拓?fù)潢P(guān)鍵點(diǎn)，如圖4(a)所示，節(jié)點(diǎn)a是關(guān)鍵點(diǎn)。
以圖 4為例說(shuō)明基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法。
1) 收集局部網(wǎng)絡(luò)拓?fù)湫畔?/p>
收集關(guān)鍵點(diǎn)a周圍的兩跳網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑢儆谕宦窂酱刂械逆溌穭潪橐唤M，得到3個(gè)不同的鏈路組L1、L2、L3，如圖4(a)所示。
2) 恢復(fù)鏈路組的連通性
隨機(jī)選取鏈路組L1，當(dāng)關(guān)鍵點(diǎn)a失效時(shí)，路徑b1ab6的連通性遭到破壞，將鏈路組L1中的鏈路開銷置為無(wú)窮大，利用最短路徑算法搜索節(jié)點(diǎn)b1到b6的新路徑b1b4b3b6，添加到局部網(wǎng)絡(luò)中，如圖 4(b)所示。然后，探測(cè)此時(shí)L2中路徑連通性是否遭到破壞，從圖4(b)中看出，可以找到新路徑b4b1b2b5，連通性不再受影響；否則，采用最短路徑算法恢復(fù)連通性。對(duì)于剩余鏈路組重復(fù)使用以上算法。注意，鏈路組L3的連通性暫時(shí)不能恢復(fù)。
3) 恢復(fù)局部網(wǎng)絡(luò)連通性
計(jì)算此時(shí)關(guān)鍵點(diǎn)a失效時(shí)局部網(wǎng)絡(luò)中簇的個(gè)數(shù)N。若N不為1，添加能使簇個(gè)數(shù)減小的最小開銷鏈路li（i=1，2，3，···），直到N=1，如圖 4(c)中鏈路l1；否則，算法結(jié)束。網(wǎng)絡(luò)進(jìn)行拓?fù)浠謴?fù)后如圖4(c)所示。
2.4 算法支持網(wǎng)絡(luò)編碼的實(shí)例
以拓?fù)鋱D3（b）中多播業(yè)務(wù)Q1為例，說(shuō)明網(wǎng)絡(luò)編碼在拓?fù)浣Y(jié)構(gòu)中的具體體現(xiàn)。設(shè)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送信息a、b，目的節(jié)點(diǎn)d11的邊分離路徑簇為s1m1d11、s1m3d11，目的節(jié)點(diǎn)d12的邊分離路徑簇為s1m3d12、s1m2m4d12，這 2個(gè)路徑簇構(gòu)成了網(wǎng)絡(luò)編碼的典型應(yīng)用環(huán)境——蝶形網(wǎng)絡(luò)。在源節(jié)點(diǎn)處對(duì)a、b進(jìn)行網(wǎng)絡(luò)編碼，將編碼后的信息在重合鏈路s1m3、m3d11、m3d12上傳輸，在其他鏈路上傳輸a或b，可保證目的節(jié)點(diǎn)d11、d12成功解碼出信息a、b。同樣方法，可保證目的節(jié)點(diǎn)d13成功收到a、b。不論編碼方法如何，構(gòu)建的拓?fù)浣Y(jié)構(gòu)都能夠支持網(wǎng)絡(luò)編碼的應(yīng)用，并確保成功解碼。
3 仿真分析
3.1 有效性
采用NS2網(wǎng)絡(luò)模擬軟件進(jìn)行測(cè)試，設(shè)置網(wǎng)絡(luò)中同時(shí)存在單播和多播業(yè)務(wù)，對(duì)比在TCBNC和基于多播樹的拓?fù)淇刂扑惴?TCBMT，topology control algorithm based on multicast tree)的控制下，網(wǎng)絡(luò)分組投遞率、吞吐量、節(jié)點(diǎn)平均能耗隨信宿節(jié)點(diǎn)數(shù)增加時(shí)的變化情況，仿真參數(shù)如表1所示。
圖4 基于關(guān)鍵點(diǎn)失效的拓?fù)浠謴?fù)算法
表1 仿真參數(shù)
定義5(網(wǎng)絡(luò)吞吐量)：指一組特定數(shù)據(jù)在特定時(shí)間段經(jīng)過特定路徑所傳輸?shù)男畔⒘康膶?shí)際測(cè)量值。
定義6(節(jié)點(diǎn)平均能耗)：指網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在運(yùn)行過程中所消耗的能量的平均值。在計(jì)算過程中，考慮了網(wǎng)絡(luò)運(yùn)行過程中影響節(jié)點(diǎn)能量的所有因素，其計(jì)算公式為
從圖5～圖7可以看出，TCBNC能夠提高網(wǎng)絡(luò)的分組投遞率和網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)的節(jié)點(diǎn)平均能耗。這是因?yàn)門CBNC能夠構(gòu)建出支持網(wǎng)絡(luò)編碼的拓?fù)浣Y(jié)構(gòu)，增加了節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼的機(jī)會(huì)，因此提高了網(wǎng)絡(luò)分組投遞率和吞吐量，節(jié)省了節(jié)點(diǎn)平均能耗。隨著網(wǎng)絡(luò)中信宿節(jié)點(diǎn)數(shù)的增加，TCBNC控制的網(wǎng)絡(luò)中更多的節(jié)點(diǎn)參與網(wǎng)絡(luò)編碼，增大編碼機(jī)會(huì)的同時(shí)提高了解碼成功概率，大量數(shù)據(jù)分組能夠成功到達(dá)目的節(jié)點(diǎn)，網(wǎng)絡(luò)的分組投遞率幾乎不變，吞吐量逐漸增大，節(jié)點(diǎn)平均能耗逐漸增大；而TCBMT控制的網(wǎng)絡(luò)中由于數(shù)據(jù)分組的逐漸增多，網(wǎng)絡(luò)阻塞、數(shù)據(jù)分組丟失和重傳現(xiàn)象十分嚴(yán)重，網(wǎng)絡(luò)性能逐漸下降。
圖5 分組投遞率隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
圖6 網(wǎng)絡(luò)吞吐量隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
圖7 節(jié)點(diǎn)平均能耗隨信宿節(jié)點(diǎn)數(shù)變化的對(duì)比
3.2 抗毀性
仿真環(huán)境與探測(cè)有效性時(shí)一致，信宿節(jié)點(diǎn)數(shù)設(shè)為10個(gè)。對(duì)比在TCBNC拓?fù)淇刂魄昂?，網(wǎng)絡(luò)性能指標(biāo)隨失效關(guān)鍵點(diǎn)數(shù)增加時(shí)的變化情況。
圖8 分組投遞率隨失效關(guān)鍵點(diǎn)數(shù)變化的對(duì)比
從圖8和圖9可以看出，隨著網(wǎng)絡(luò)中失效關(guān)鍵點(diǎn)數(shù)的增加，支持網(wǎng)絡(luò)編碼的拓?fù)淇刂扑惴軌蝻@著提高網(wǎng)絡(luò)的分組投遞率和吞吐量，改善網(wǎng)絡(luò)的性能。一方面，TCBNC通過建立新鏈路，保證了網(wǎng)絡(luò)的連通性，數(shù)據(jù)分組能夠順利到達(dá)目的節(jié)點(diǎn)；另一方面，修復(fù)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能夠繼續(xù)支持網(wǎng)絡(luò)編碼的應(yīng)用，減少了數(shù)據(jù)分組的傳輸次數(shù)，提高網(wǎng)絡(luò)吞吐量。因此，TCBNC使網(wǎng)絡(luò)性能得到了有效的恢復(fù)，增強(qiáng)了網(wǎng)絡(luò)的抗毀性。
圖9 網(wǎng)絡(luò)吞吐量隨失效關(guān)鍵點(diǎn)數(shù)變化的對(duì)比
4 復(fù)雜度分析
TCBNC的復(fù)雜度小于對(duì)比TCBMT的復(fù)雜度，主要體現(xiàn)在多播業(yè)務(wù)的拓?fù)錁?gòu)建過程中利用了最短路網(wǎng)絡(luò)。圖 10所示為初始網(wǎng)絡(luò)拓?fù)鋱D，源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)為d，K=2，利用TCBMT搜索兩條最短路徑需要的計(jì)算次數(shù)為 2×(15+14+···+2)= 238；利用 TCBNC構(gòu)建最短路網(wǎng)絡(luò)的計(jì)算次數(shù)為14+13+···+2=104，如圖 11 所示，在其基礎(chǔ)上搜索一條最短路徑的計(jì)算次數(shù)為 15，總計(jì)算次數(shù)為104+2×15=134，節(jié)約了 43.7%的計(jì)算量。并且，隨著目的節(jié)點(diǎn)數(shù)、K值的增加，算法具有更低的復(fù)雜度。
圖10 初始網(wǎng)絡(luò)拓?fù)鋱D
圖11 最短路網(wǎng)絡(luò)拓?fù)鋱D
5 結(jié)束語(yǔ)
本文提出一種支持網(wǎng)絡(luò)編碼的認(rèn)知無(wú)線自組網(wǎng)拓?fù)淇刂扑惴?TCBNC，針對(duì)不同的業(yè)務(wù)類型采用不同算法構(gòu)建支持網(wǎng)絡(luò)編碼的初始拓?fù)鋱D，然后通過逐個(gè)刪除冗余鏈路進(jìn)行拓?fù)鋬?yōu)化，最后提出解決關(guān)鍵點(diǎn)失效問題的拓?fù)浠謴?fù)算法。算法支持網(wǎng)絡(luò)編碼的應(yīng)用，增強(qiáng)了通信的有效性和抗毀性。另外，算法復(fù)雜度不大，在節(jié)點(diǎn)移動(dòng)或信道環(huán)境變化時(shí)仍能適用。在未來(lái)的工作中，將考慮鏈路失效的情況，重構(gòu)支持網(wǎng)絡(luò)編碼的拓?fù)洹?/p>
[1] DE MORAIS CORDEIRO C, GOSSAIN H, AGRAWAL D P.Multicast over wireless mobile ad hoc network： present and future directions[J].IEEE Communications Society, 2003, 17(1)： 52-59.
[2] RABBACHIN A, QUEK T Q S, HYUNDONG S.Cognitive network interference[J].IEEE Journal on Communications, 2011, 29(2)：480-493.
[3] WANG Z D, WANG H Q, FENG G S.Cognitive networks and its layered cognitive architecture[A].2010 Fifth International Conference on Internet Computing for Science and Engineering(ICICSE)[C].Heilongjiang, China, 2012.145-148.
[4] LI B C, NIU D.Random network coding in peer-to-peer petworks：from theory to practice[J].Proceedings of the IEEE, 2010, 99(3)：513-523.
[5] AHN M H, KIM Y Y.Network coding-based multicast scheduling for throughput enhancement in wireless ad hoc network[A].2011 International Conference on Information Networking[C].Barcelona, Spain,2011.188-193.
[6] 胡金秀.多播網(wǎng)絡(luò)編碼算法研究[D].西安： 西安電子科技大學(xué),2010.HU J X.Study on Multicast Network Coding Algorithm[D].Xian： Xidian University, 2010.
[7] ZHANG T, YANG K, CHEN H H.Topology control for service-oriented wireless mesh networks[J].IEEE Wireless Communications, 2009, 16(4)： 64-71.
[8] YADU K K, KAKDE O G.Optimization based topology control for wireless ad hoc networks to meet QoS requirements[A].2010 29th IEEE Symposium on Reliable Distributed System[C].New Delhi, India, 2010.30-36.
[9] CHI K K, JIANG X H, HORIGUCHI S.Topology design of network-noding-based multicast networks[J].IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5)： 627-640.
[10] LI J K, PAN Y.Network coding driented topology design based on parallel genetic algorithm[A].2011 Fourth International Joint Conference on Computational Sciences and Optimization[C].Yunnan, China,2011.838-841.
猜你喜歡
電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12
計(jì)算機(jī)研究與發(fā)展(2022年12期)2022-12-15 13:18:44
數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22
計(jì)算機(jī)工程與應(yīng)用(2022年5期)2022-04-09 07:03:42
計(jì)算機(jī)研究與發(fā)展(2022年4期)2022-04-06 06:58:32
中學(xué)生數(shù)理化·中考版(2022年12期)2022-02-16 07:36:56
今日農(nóng)業(yè)(2021年8期)2021-11-28 05:07:50
華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55
中國(guó)衛(wèi)生(2014年2期)2014-11-12 13:00:16
語(yǔ)文知識(shí)(2014年7期)2014-02-28 22:00:26
