国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

優(yōu)化目標(biāo)可變的容錯(cuò)三維拓?fù)淇刂扑惴ǎ?/h1>
2014-03-23 06:03:06東,鄧
關(guān)鍵詞:拓?fù)鋱D原圖子圖

王 東,鄧 好

(湖南大學(xué)信息科學(xué)與工程學(xué)院,湖南長(zhǎng)沙410082)

1 引言

Ad Hoc網(wǎng)絡(luò)是指由一組自治無線設(shè)備組成的支持多跳的臨時(shí)性的網(wǎng)絡(luò)系統(tǒng)。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在共享的無線信道上互相通信,無需任何網(wǎng)絡(luò)基礎(chǔ)設(shè)施,且具有易于快速部署的特點(diǎn),使其在應(yīng)急通信、交通管理、現(xiàn)代化生產(chǎn)、醫(yī)療衛(wèi)生、環(huán)境監(jiān)測(cè)等領(lǐng)域中得到廣泛應(yīng)用。因此,Ad Hoc網(wǎng)絡(luò)通信技術(shù)受到了研究人員的廣泛關(guān)注。

無線網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是基于節(jié)點(diǎn)的物理位置和信號(hào)傳輸范圍自治形成的[1]。在Ad Hoc網(wǎng)絡(luò)中,一方面,節(jié)點(diǎn)的物理位置由任務(wù)需求來確定,另一方面,節(jié)點(diǎn)的信號(hào)傳輸半徑可以根據(jù)需求進(jìn)行調(diào)節(jié)。如果所有節(jié)點(diǎn)都以最大傳輸功率工作,節(jié)點(diǎn)有限的能量將被通信部件快速消耗,造成節(jié)點(diǎn)過早死亡,使得網(wǎng)絡(luò)局部斷開,甚至網(wǎng)絡(luò)不連通;另外,節(jié)點(diǎn)以最大功率傳輸會(huì)使得節(jié)點(diǎn)信號(hào)彼此過度重疊,造成無線信號(hào)互相干擾,影響節(jié)點(diǎn)的通信質(zhì)量,降低網(wǎng)絡(luò)的吞吐率。為了有效解決以上問題,在Ad Hoc網(wǎng)絡(luò)中有必要針對(duì)任務(wù)需求,對(duì)節(jié)點(diǎn)的傳輸功率進(jìn)行調(diào)節(jié),從而對(duì)無線網(wǎng)絡(luò)的拓?fù)溥M(jìn)行控制。

由于Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)能量受限,節(jié)點(diǎn)工作一段時(shí)間后將會(huì)死亡,另外,任務(wù)需求也可能使節(jié)點(diǎn)發(fā)生移動(dòng),所以Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)加入和離開網(wǎng)絡(luò)等異動(dòng)情況是經(jīng)常發(fā)生的。節(jié)點(diǎn)的頻繁異動(dòng)使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化,從而對(duì)網(wǎng)絡(luò)的性能(如節(jié)點(diǎn)能耗、網(wǎng)絡(luò)傳輸能力等)產(chǎn)生很大的影響。此外,在實(shí)際應(yīng)用中,網(wǎng)絡(luò)的通信場(chǎng)景會(huì)發(fā)生變化,當(dāng)多個(gè)節(jié)點(diǎn)同時(shí)通信或部分節(jié)點(diǎn)發(fā)送大量數(shù)據(jù)時(shí),其信號(hào)不間斷,會(huì)對(duì)其他節(jié)點(diǎn)造成干擾,造成網(wǎng)絡(luò)通信質(zhì)量下降,此時(shí)降低干擾尤其重要;當(dāng)節(jié)點(diǎn)不同時(shí)通信或節(jié)點(diǎn)發(fā)送數(shù)據(jù)少時(shí),信號(hào)沖突幾率低,干擾對(duì)網(wǎng)絡(luò)影響不大,此時(shí),拓?fù)淇刂苾?yōu)化目標(biāo)應(yīng)該以節(jié)約能量、延長(zhǎng)網(wǎng)絡(luò)生命周期為主。因此,如何研究出一種具有較好拓?fù)淙蒎e(cuò)能力,能適應(yīng)實(shí)際通信場(chǎng)景變化,同時(shí)能兼顧其它網(wǎng)絡(luò)性能要求的拓?fù)淇刂扑惴ǔ蔀锳d Hoc網(wǎng)絡(luò)技術(shù)研究的熱點(diǎn)。

本文提出一種適用于三維立體空間、可以根據(jù)網(wǎng)絡(luò)干擾情況調(diào)整優(yōu)化目標(biāo)并且具有較好容錯(cuò)能力的拓?fù)淇刂扑惴ā狾VFSS(Optimization-Variable Fault-tolerant Spanning Subgraph)。

2 相關(guān)工作

早期的拓?fù)淇刂剖峭ㄟ^調(diào)整節(jié)點(diǎn)發(fā)射功率在保持連通性的同時(shí)達(dá)到節(jié)能的目的,從而延長(zhǎng)網(wǎng)絡(luò)生命周期。Chew L P[2]第一次提出了伸展因子的概念,該因子等于通過拓?fù)淇刂萍夹g(shù)調(diào)整后的生成子圖路徑能耗與原圖路徑能耗之比,來描述拓?fù)淇刂浦缶W(wǎng)絡(luò)的能量伸展性。近期,一些研究工作也把注意力放到如何調(diào)節(jié)功率,使網(wǎng)絡(luò)保證連通的情況下同時(shí)滿足能量伸展性。

Wang Y等人[3]最先開始研究如何通過減小節(jié)點(diǎn)的發(fā)送功率來降低網(wǎng)絡(luò)總能耗,并且使調(diào)整后的通信子圖具有能量伸展性。同時(shí),他們還提出了兩種啟發(fā)式算法,使構(gòu)建的網(wǎng)絡(luò)能耗較低,且滿足能量伸展性等要求。

Shpungin H等人[4]從理論上研究了伸展性問題,他們的目標(biāo)是同時(shí)滿足能量伸展性和距離伸展性。為了能量伸展性,他們提出了一種方法,使調(diào)整后的子網(wǎng)的能量伸展因子為2(即新導(dǎo)出的子圖點(diǎn)對(duì)之間的路徑能耗最多是原圖的2倍),并且得到的子網(wǎng)是強(qiáng)連通的。

Rickenbach P V[5]提出降低網(wǎng)絡(luò)干擾才是無線網(wǎng)絡(luò)拓?fù)淇刂谱钪匾哪繕?biāo)。無線網(wǎng)絡(luò)中的干擾會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞和數(shù)據(jù)包的重傳,對(duì)網(wǎng)絡(luò)的生命周期和網(wǎng)絡(luò)的可用性都有很大的影響。

上述工作主要考慮無線網(wǎng)絡(luò)的能量有效性和如何延長(zhǎng)網(wǎng)絡(luò)的生命周期問題,而網(wǎng)絡(luò)的容錯(cuò)能力也十分重要。無線網(wǎng)絡(luò)的容錯(cuò)拓?fù)淇刂浦饕芯咳绾螛?gòu)建k連通的拓?fù)浣Y(jié)構(gòu)圖,即在k-1個(gè)節(jié)點(diǎn)失效的情況下,網(wǎng)絡(luò)仍然保持連通,相關(guān)的研究有文獻(xiàn)[6~8]。但是,這些研究又缺少對(duì)其他性能的考慮,例如能量有效性等。

在無線網(wǎng)絡(luò)領(lǐng)域,研究的重點(diǎn)集中在節(jié)能、減小干擾、容錯(cuò)等方面。為了簡(jiǎn)化算法研究,方便建模,一般假設(shè)網(wǎng)絡(luò)部署在二維平面上。然而,實(shí)際應(yīng)用時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)一般是分布在三維立體空間里。二維平面圖和三維立體圖在性質(zhì)上有很大的差別,簡(jiǎn)單地將三維網(wǎng)絡(luò)映射到二維會(huì)丟失許多幾何性質(zhì),所以二維場(chǎng)景下設(shè)計(jì)的部分算法無法直接應(yīng)用到三維。為了設(shè)計(jì)出更加真實(shí)、合理有效且可應(yīng)用到實(shí)際網(wǎng)絡(luò)中的拓?fù)淇刂扑惴?,Wang Y等人[9]在三維場(chǎng)景下對(duì)無線網(wǎng)絡(luò)的拓?fù)淇刂七M(jìn)行研究,他們提出了3D k-RNG、3D k-GG和3D k-YG三種算法,并且證明這些算法都具有一定容錯(cuò)能力,同時(shí)還分別滿足部分網(wǎng)絡(luò)性能指標(biāo)。

由于三維場(chǎng)景的特殊性,針對(duì)三維場(chǎng)景所研究的拓?fù)淇刂扑惴ㄟ€不多,面對(duì)Ad Hoc網(wǎng)絡(luò)可能部署的復(fù)雜環(huán)境,追求單一優(yōu)化目標(biāo)或是固定優(yōu)化目標(biāo)的算法的實(shí)用性值得懷疑。為了算法的靈活多變性,本文提出一種優(yōu)化目標(biāo)可改變的容錯(cuò)拓?fù)淇刂扑惴ā?/p>

3 數(shù)學(xué)模型

無線網(wǎng)絡(luò)結(jié)構(gòu)一般將其抽象成圖,拓?fù)淇刂萍夹g(shù)通過調(diào)節(jié)節(jié)點(diǎn)發(fā)射功率使得節(jié)點(diǎn)信號(hào)覆蓋范圍變化,影響節(jié)點(diǎn)之間的連通,可以抽象為圖中邊的增刪。需要滿足的網(wǎng)絡(luò)性能要求,例如連通度、容錯(cuò)能力、干擾較小等,都可以抽象為對(duì)圖的性質(zhì)要求,對(duì)應(yīng)為圖的連通度、k連通、點(diǎn)干擾、邊干擾等。

本文研究針對(duì)的是較為真實(shí)的三維應(yīng)用場(chǎng)景,假設(shè)三維的Ad Hoc網(wǎng)絡(luò)分布在一個(gè)三維空間R3上。網(wǎng)絡(luò)用無向圖G=(V,E)表示,其中,V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)組成的集合,E表示網(wǎng)絡(luò)中所有邊組成的集合。用|V|表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù),|E|表示網(wǎng)絡(luò)中的邊數(shù)。每個(gè)節(jié)點(diǎn)的發(fā)射功率都可以設(shè)置為從0到最大值Tmax之間的任意值。每個(gè)節(jié)點(diǎn)均有一個(gè)id號(hào)(IP或者M(jìn)AC地址)。三維Ad Hoc網(wǎng)絡(luò)的模型是個(gè)單位球UBG(Unit Ball Graph)。當(dāng)且僅當(dāng)u和v之間的歐氏距離dist(u,v)均不大于最大發(fā)射信號(hào)距離r時(shí),u和v之間存在一條邊。

無線信號(hào)在傳播過程中信號(hào)會(huì)衰減,無線信號(hào)傳播模型決定了節(jié)點(diǎn)發(fā)射功率和接收功率的關(guān)系。信號(hào)功率的衰減與發(fā)射天線和接收天線之間的距離的β次方成正比[10],β是一個(gè)常數(shù),取值范圍由環(huán)境所決定,一般為2~5。β的取值與無線傳播模型相關(guān),對(duì)于自由空間模型,認(rèn)為無線電波的損耗只和傳播距離和電波頻率有關(guān)系,在給定信號(hào)頻率的時(shí)候,只和距離有關(guān)系。本文研究時(shí)采用該模型,取值β=2,即給定信號(hào)頻率時(shí),電波損耗與傳播距離的平方成正比。

對(duì)于節(jié)點(diǎn)集合V中的兩個(gè)節(jié)點(diǎn)u和v,給出節(jié)點(diǎn)傳輸能耗、k連通、點(diǎn)干擾、邊干擾的定義。

定義1 點(diǎn)u是圖G中的一點(diǎn),拓?fù)淇刂坪?,u的傳輸能耗為該節(jié)點(diǎn)能達(dá)到的最遠(yuǎn)距離鄰居節(jié)點(diǎn)所需的能耗。

定義2 當(dāng)且僅當(dāng)圖G=(V,E)中的任意兩點(diǎn)u和v之間存在頂點(diǎn)不相交的k條路徑時(shí),圖G=(V,E)是k連通的。也可以理解為,當(dāng)去掉圖G=(V,E)中k-1個(gè)頂點(diǎn),圖仍然連通時(shí),圖G=(V,E)是k連通的。

節(jié)點(diǎn)之間通信造成的干擾是一種概率性事件,為了能量化網(wǎng)絡(luò)中的干擾,借鑒文獻(xiàn)[11]定義干擾模型。節(jié)點(diǎn)u和v通信時(shí),若存在節(jié)點(diǎn)w,且該節(jié)點(diǎn)w的發(fā)射區(qū)域覆蓋了u或者v,則w的信號(hào)會(huì)影響u的發(fā)送或者v的接收,此時(shí)就可以理解為w對(duì)u或v造成了干擾。借鑒二維網(wǎng)絡(luò)中經(jīng)典的干擾模型,本文構(gòu)建一種三維網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)通信干擾模型,定義如下:

定義3 節(jié)點(diǎn)u的干擾值I(u)定義為所有通信范圍覆蓋了節(jié)點(diǎn)u的節(jié)點(diǎn)數(shù)。I(u)={v|v∈V\{u},u∈Z(v,rv)},這里V表示網(wǎng)絡(luò)圖節(jié)點(diǎn)集合,Z(v,rv)代表以節(jié)點(diǎn)v為中心、rv為半徑的球形通信區(qū)域。

定義4 邊e=(u,v)的干擾值可以定義為所有通信范圍覆蓋了邊e中節(jié)點(diǎn)u或v的節(jié)點(diǎn)數(shù)。I(e)={w|u∈Z(w,rw)∪v∈Z(w,rw),e=(u,v),w∈V}。

圖1為三維網(wǎng)絡(luò)邊干擾模型示意圖,每個(gè)節(jié)點(diǎn)均以其發(fā)射功率能達(dá)到的通信距離為半徑形成一個(gè)球狀通信區(qū)域,假設(shè)節(jié)點(diǎn)u和節(jié)點(diǎn)v之間存在一條邊,若節(jié)點(diǎn)u或v處于節(jié)點(diǎn)w的通信區(qū)域內(nèi),認(rèn)為節(jié)點(diǎn)w對(duì)節(jié)點(diǎn)u、v之間的通信邊造成干擾,該邊的邊干擾值加1,以此方法檢查所有鄰居節(jié)點(diǎn),最終得出該邊的邊干擾值。

Figure 1 Edge interference model in three-dimensional network圖1 三維網(wǎng)絡(luò)邊干擾模型

4 優(yōu)化目標(biāo)可變?nèi)蒎e(cuò)拓?fù)淇刂扑惴?/h2>

實(shí)際應(yīng)用的Ad Hoc網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄐ枰C合考慮多個(gè)優(yōu)化因素。以往的算法考慮多個(gè)優(yōu)化目標(biāo)時(shí),由于各個(gè)優(yōu)化目標(biāo)(例如網(wǎng)絡(luò)干擾和能耗)可能是互相矛盾的,一般在各項(xiàng)網(wǎng)絡(luò)性能指標(biāo)中取一個(gè)折衷值,部分優(yōu)化干擾和部分優(yōu)化能耗,是一種非最優(yōu)化的靜態(tài)平衡。實(shí)際情況下,網(wǎng)絡(luò)通信狀態(tài)是變化的,某時(shí)刻可能大量節(jié)點(diǎn)同時(shí)通信或部分節(jié)點(diǎn)發(fā)送大量數(shù)據(jù),其信號(hào)對(duì)其他節(jié)點(diǎn)造成干擾,也可能某時(shí)刻節(jié)點(diǎn)處于監(jiān)聽狀態(tài),偶爾發(fā)送數(shù)據(jù),彼此信號(hào)沖突較小,干擾較小。靜態(tài)優(yōu)化并不能適應(yīng)這種變化情況,無法將優(yōu)化目標(biāo)最大化。針對(duì)應(yīng)用場(chǎng)景通信環(huán)境信號(hào)干擾強(qiáng)烈程度多變的情況,提出一種優(yōu)化目標(biāo)可變的容錯(cuò)拓?fù)淇刂扑惴∣VFSS,在保證網(wǎng)絡(luò)k連通的前提下,根據(jù)節(jié)點(diǎn)通信情況判斷網(wǎng)絡(luò)所處情況,選擇合適的參數(shù),進(jìn)行有針對(duì)性的目標(biāo)優(yōu)化。算法的具體思想是,根據(jù)網(wǎng)絡(luò)通信情況,適當(dāng)選擇重點(diǎn)優(yōu)化的目標(biāo)。在干擾影響較大時(shí)優(yōu)先減小干擾,保證網(wǎng)絡(luò)應(yīng)用能有效實(shí)施;在干擾影響較小時(shí),不考慮干擾,優(yōu)先降低能耗,以便延長(zhǎng)網(wǎng)絡(luò)生命周期。

文獻(xiàn)[11]通過對(duì)干擾進(jìn)行建模,將概率性事件進(jìn)行量化。同樣的路由算法下,當(dāng)節(jié)點(diǎn)同時(shí)通信或部分節(jié)點(diǎn)發(fā)送大量數(shù)據(jù)時(shí),數(shù)據(jù)沖突加劇,丟包、重傳次數(shù)會(huì)上升,此時(shí)干擾對(duì)網(wǎng)絡(luò)影響較大;當(dāng)節(jié)點(diǎn)不同時(shí)通信或節(jié)點(diǎn)發(fā)送數(shù)據(jù)小,彼此信號(hào)沖突概率低時(shí),丟包、重傳次數(shù)會(huì)較小,此時(shí)干擾對(duì)網(wǎng)絡(luò)影響較小。本文假設(shè)節(jié)點(diǎn)設(shè)備硬件和協(xié)議能通過重傳、丟包等數(shù)據(jù)的統(tǒng)計(jì),判斷網(wǎng)絡(luò)的干擾影響程度,干擾影響大時(shí)設(shè)置參數(shù)s=1,干擾影響小時(shí)設(shè)置參數(shù)為s=0。

為了減小網(wǎng)絡(luò)中的干擾,可將邊權(quán)值改為邊干擾值,但同時(shí)也發(fā)現(xiàn)一個(gè)問題,如圖2所示I(A,B)=I(A,C)=3,但此時(shí)鄰居節(jié)點(diǎn)距離不相同,圖2中可見,dist(A,B)>dist(A,C),即單一考慮將邊權(quán)值改為邊干擾值考慮不周全。

Figure 2 The case of same edge interference but different distances圖2 邊干擾相同距離不同情況

為此,OVFSS算法將綜合考慮干擾和距離能耗等因素,定義邊權(quán)值如下:

權(quán)值公式由兩部分組成,第一部分是干擾影響值,第二部分是規(guī)格化后的距離影響值。s=1時(shí),權(quán)值公式主要由邊干擾I(u,v)決定,同時(shí)規(guī)格化距離值能保證在節(jié)點(diǎn)干擾度相同的情況下,距離小的邊權(quán)值較小;s=0時(shí),即干擾較小時(shí),邊干擾不納入考慮,由規(guī)格化距離值決定權(quán)值,最大化地實(shí)現(xiàn)節(jié)能優(yōu)化的目標(biāo)。

要注意的是,尋找最小能耗生成子圖已被證明是NP難問題,本算法考慮容錯(cuò)和多個(gè)優(yōu)化目標(biāo)時(shí)該問題顯然也是NP難問題。

OVFSS算法根據(jù)邊權(quán)值公式對(duì)圖中所有的邊的權(quán)重進(jìn)行計(jì)算,然后按照邊權(quán)值升序排列。根據(jù)得到的邊權(quán)值,基于貪婪算法計(jì)算一個(gè)干擾最小的或能耗最小的k連通圖。為保證貪婪算法是唯一結(jié)果,假設(shè)不相同的節(jié)點(diǎn)對(duì)之間的邊權(quán)值沒有相同的。算法的偽代碼如下:

算法1 OVFSS

輸入:具有N個(gè)節(jié)點(diǎn)的點(diǎn)集和連通度k(k≥1)。

輸出:k連通的干擾最小或能耗最小的子圖。

1:初始化原圖G=(V,E)。

2:計(jì)算G中每條邊的邊權(quán)值W=s×I+dist/r。

3:將所有的邊按照邊權(quán)值升序排列。

4:初始化子圖GOVFSS=(V,EOVFSS=?)。

5:對(duì)于圖中的每條邊e=(u,v)。

6: 如果GOVFSS中u和v之間不是k連通

7: 添加該邊到邊集合中EOVFSS=EOVFSS∪{e};

9: 如果所有節(jié)點(diǎn)之間均是k連通

10: 退出,算法結(jié)束

當(dāng)s=0時(shí),權(quán)值由距離決定,算法等價(jià)于Kruskal算法[12]的一種擴(kuò)展版。該算法在保證容錯(cuò)的前提下,選取距離最短邊以尋求節(jié)能優(yōu)化,其干擾優(yōu)化能力不強(qiáng)(本身就是在干擾較小的情況下才選擇該算法)。

當(dāng)s=1時(shí),邊干擾值起決定作用,算法以干擾優(yōu)化能力為主,同時(shí)兼顧選取距離較短、能耗較低的邊,算法的優(yōu)勢(shì)體現(xiàn)明顯。

下面對(duì)算法的正確性給出證明,即證明算法保證網(wǎng)絡(luò)k連通的情況下優(yōu)化網(wǎng)絡(luò)干擾,使其干擾最小化,并同時(shí)考慮了節(jié)能。為了方便證明,本文采用以下術(shù)語(yǔ):

G代表初始的拓?fù)鋱D,G′代表算法優(yōu)化后最終的拓?fù)鋱D。Path(u,w1,w2,…,wn,v)表示從節(jié)點(diǎn)u到節(jié)點(diǎn)v的路徑,其中w1,w2,…,wn代表路徑經(jīng)過的節(jié)點(diǎn)。Suv(G)代表無向圖G中節(jié)點(diǎn)u到節(jié)點(diǎn)v之間的所有不相交的路徑數(shù)。

引理1 設(shè)u1和u2是k連通無向圖G中兩節(jié)點(diǎn),如果u1和u2間存在邊(u1,u2),并且在圖G中移除邊(u1,u2)后,u1和u2之間仍然是k連通,那么G-(u1,u2)仍然是k連通的。

證明 要證明G-(u1,u2)是k連通的,等價(jià)于證明G′=G-(u1,u2)中移除k-1個(gè)節(jié)點(diǎn)后,圖G′仍然是連通的。不失一般性,假設(shè){u1,u2}∩{v1,v2}=?。如果能夠證明在圖G′中移除k-1個(gè)節(jié)點(diǎn)后,任意兩個(gè)節(jié)點(diǎn)v1、v2仍然連通,那么就可以證明G′是k連通的。

(4) 交通銜接條件:站點(diǎn)周邊地區(qū)的交通可達(dá)性以及車站接駁體系的成熟程度,是制約客流的主要因素。本文主要選取車站周邊道路網(wǎng)密度、人行道面積率、出入口周邊機(jī)動(dòng)車及自行車停放場(chǎng)地面積、公交車站經(jīng)停線路數(shù)等指標(biāo),經(jīng)過同等權(quán)重的無量綱化處理得到交通銜接水平評(píng)價(jià)值。

(1)如果v1、v2兩個(gè)節(jié)點(diǎn)在原圖G中直接相連,因?yàn)樵瓐DG是k連通的,那么很顯然在圖G′中移除k-1個(gè)節(jié)點(diǎn)后,節(jié)點(diǎn)v1、v2仍然是連通的。

(2)如果v1、v2兩個(gè)節(jié)點(diǎn)在原圖G中并沒有邊相連。假設(shè)圖G″為G′-(k-1)個(gè)節(jié)點(diǎn)后的圖。S1表示在G′中移除k-1個(gè)節(jié)點(diǎn)后Sv1v2(G′)中斷開的路徑數(shù)。因?yàn)镾v1v2(G′)是圖G′中v1、v2兩節(jié)點(diǎn)的不相交的路徑數(shù),所以在圖G′中移除k-1個(gè)最多斷開k-1條v1、v2節(jié)點(diǎn)間的路徑,因此S1≤k-1。

①如果Sv1v2(G′)≥k,那么Sv1v2(G″)≥Sv1v2(G′)-S1≥k-(k-1)≥1。所以,在圖G″中,v1、v2兩個(gè)節(jié)點(diǎn)是連通的。

②如果Sv1v2(G′)<k,這種情況只可能是在原圖G中刪除邊(u1,u2)的時(shí)候斷開了節(jié)點(diǎn)v1和v2之間的一條路徑。所以,可以得到Sv1v2(G′)=k-1。現(xiàn)在再考慮在圖G′中刪除k-1個(gè)節(jié)點(diǎn)后的兩種情況。

a如果S1<k-1,那么Sv1v2(G″)≥Sv1v2(G′)-S1≥1,即節(jié)點(diǎn)v1、v2兩個(gè)節(jié)點(diǎn)是連通的。

b如果S1=k-1,因?yàn)楣?jié)點(diǎn)間的路徑都是不相交的,S1=k-1這種情況唯一的出現(xiàn)場(chǎng)景為v1與u1直接相連,v2和u2直接相連。用S2表示在G′中移除k-1個(gè)節(jié)點(diǎn)后Su1u2(G′)中斷開的路徑數(shù),由命題題意可知Su1u2(G′)≥k,并且很容易知道S2≤k-1,這也就證明了在G″中u1和u2是連通的,又因?yàn)関1、v2分別與u1、u2相連,所以v1,v2是連通的。

綜上可得,G′是k連通的,因此G-(u1,u2)是k連通的。證畢?!?/p>

引理2 假設(shè)無向圖H和H′滿足條件V(H)=V(H′)。如果H是k連通的,并且每條邊(u,v)∈E(H)-E(H′)在圖G-{(u0,v0)∈E(H):W(u0,v0)≥W(u,v)}中都是k連通的,那么H′也是k連通的。

證明 用集合E=E(H)-E(H′)={(u1,v1),(u2,v2),…,(um,vm)}表示在圖H中出現(xiàn)且在圖H′沒有出現(xiàn)的邊集,且W(u1,v1)>W(wǎng)(u2,v2)>…>W(wǎng)(um,vm)。同時(shí)定義一系列原圖H的子圖Hi:H0=H,Hi=Hi-1-(ui,vi)。下面用歸納法來證明:

(1)H0=H,所以H0是k連通的。

(2)如果Hi-1是k連通的,那么應(yīng)用引理1可得Hi是k連通的。所以,可以得到Hm是k連通的。

因?yàn)镋(Hm)?E(H′),所以H′也是k連通的。證畢?!?/p>

定理1 G′是k連通的。

證明 在OVFSS算法中,所有的邊都是按非遞減順序排列的,而且沒有加入圖G′中的邊唯一的條件就是這條邊的兩個(gè)節(jié)點(diǎn)間已經(jīng)是k連通的。應(yīng)用引理2可以得到圖G′是k連通的。證畢?!?/p>

定理2 優(yōu)化干擾時(shí),G′是一個(gè)干擾最小的k連通圖。

證明 s=1時(shí),權(quán)值公式主要由邊干擾值確定,邊權(quán)值可以近似為邊干擾值,用Sk(G)代表圖G的所有k連通子圖。如果G是k連通的,根據(jù)定理1,可得G′也是k連通的。假設(shè)邊(u,v)是OVFSS算法中最后加入圖G′的一條邊。那么可以知道I(u,v)=Max(u0,v0∈E(G′){I(u0,v0)<I(u,v)},即I(u,v)的干擾值比已經(jīng)加入到圖G′中的任何一條邊的干擾值都大。設(shè)G2=G′-(u,v),因此在圖G2中節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的不相交路徑數(shù)是小于k的,否則OVFSS算法不會(huì)將邊(u,v)加入到圖G′中。用圖C=(V(C),E(C)),這里V(C)=V(G),E(C)={(u0,v0)∈E(G):I(u0,v0)<I(u,v)}。如果可以證明C并不是k連通,那就可以說在圖G的任何一個(gè)k連通子圖中都存在一條邊的干擾值大于I(u,v),這也證明了G′是干擾最小的k連通子圖。

用反證法證明C不是k連通的。假設(shè)C是k連通的,因此Suv(C)≥k。那么E(C)?E(G2);否則,|Suv(G2)|≥|Suv(C)|≥k,與前段中G2的定義矛盾。因此,E0=E(C)-E(G2)≠?。因?yàn)樗械倪叾际前锤蓴_值非遞減順序加入到圖G′中的,所以有?(u1,v1)∈E0都滿足u1和v1在圖C-{(u0,v0)∈E(C):I(u0,v0)≥I(u1,v1)}中是k連通的。由引理2可得,當(dāng)把E0中的所有邊都刪除后,節(jié)點(diǎn)u和節(jié)點(diǎn)v之間仍然是k連通的,也就是說|Suv(G2)|≥k,而這與G2的定義是矛盾的。所以,由OVFSS算法得到的G′是原圖G的干擾最小k連通子圖。證畢。□

定理2證明了圖G′是干擾最小的k連通圖,在權(quán)值公式里,在干擾相同的情況下,選取邊長(zhǎng)更短的邊,兼顧節(jié)能,以延長(zhǎng)網(wǎng)絡(luò)生命周期。在干擾較小時(shí),權(quán)值公式改為由能耗決定邊權(quán)值,此時(shí)通過類似定理2的證明過程可以得出,優(yōu)化能耗時(shí)G′是一個(gè)能耗最小的k連通圖。

5 仿真實(shí)驗(yàn)

考慮到3D k-GG算法和3D k-YG算法解決的問題與本文研究問題最為接近且是本領(lǐng)域具有代表性的算法,下面對(duì)OVFSS算法、3D k-GG算法和3D k-YG算法在干擾優(yōu)化方面進(jìn)行比較。

實(shí)驗(yàn)場(chǎng)景[8]為20×20×20的三維空間,節(jié)點(diǎn)的最大發(fā)射功率為9,節(jié)點(diǎn)數(shù)從50到175遞增,β值取2。實(shí)驗(yàn)分別比較了干擾較強(qiáng)(s=1)時(shí)不同容錯(cuò)度k=1,k=2和k=3三種情況下,三種拓?fù)淇刂扑惴ǖ母蓴_優(yōu)化效果。當(dāng)容錯(cuò)度k取1、2、3三個(gè)不同值時(shí),仿真結(jié)果都是一致的:OVFSS算法降低網(wǎng)絡(luò)干擾的能力都是優(yōu)于其它兩種拓?fù)淇刂扑惴ā_@里只給出k=3時(shí)(容錯(cuò)能力度量值)三種拓?fù)淇刂扑惴ǖ姆抡娼Y(jié)果。

Figure 3 Comparison of node interference among OVFSS,3D k-GG and 3D k-YG topology subgraph圖3 OVFSS、3D k-GG和3D k-YG生成的拓?fù)鋱D節(jié)點(diǎn)干擾比較

由圖3可知,OVFSS算法生成的拓?fù)鋱D的最大節(jié)點(diǎn)干擾和平均節(jié)點(diǎn)干擾值都是最小的,相對(duì)于原圖UBG來說,OVFSS算法生成的拓?fù)鋱D的點(diǎn)干擾值遠(yuǎn)遠(yuǎn)小于UBG圖中的點(diǎn)干擾值,也同樣小于其它三種拓?fù)鋱D的點(diǎn)干擾值。3D k-GG算法生成的拓?fù)鋱D的點(diǎn)干擾值要小于3D k-YG算法生成的拓?fù)鋱D中的點(diǎn)干擾值。3D k-YG算法生成的拓?fù)鋱D中的點(diǎn)干擾值相對(duì)于原圖UBG來說還是有一定程度的減少。而且隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加,原圖UBG和3D k-YG算法生成的拓?fù)鋱D的點(diǎn)干擾值會(huì)線性增長(zhǎng),而OVFSS算法生成的拓?fù)鋱D的點(diǎn)干擾值維持在一個(gè)較小的定值左右,并不會(huì)隨著節(jié)點(diǎn)數(shù)的增加而增大。

由圖4可知,隨著節(jié)點(diǎn)數(shù)的增加,3D k-GG算法與OVFSS算法都可以有效地調(diào)節(jié)節(jié)點(diǎn)的發(fā)射功率,使得網(wǎng)絡(luò)在保證k容錯(cuò)的同時(shí),最小化網(wǎng)絡(luò)中的干擾。OVFSS算法生成的拓?fù)鋱D的邊干擾值是最低的,遠(yuǎn)低于其它三種算法生成的拓?fù)鋱D中的干擾值。而且隨著節(jié)點(diǎn)數(shù)的增加,這一結(jié)果更加明顯。

以上仿真結(jié)果表明,在三維空間網(wǎng)絡(luò)中OVFSS拓?fù)淇刂扑惴ǖ母蓴_優(yōu)化效果都是較好的。

下面對(duì)OVFSS算法、3D k-GG算法和3D k-YG算法在能耗優(yōu)化方面進(jìn)行比較。

Figure 4 Comparison of edge interference among OVFSS,3D k-GG and 3D k-YG topology subgraph圖4 OVFSS、3D k-GG和3D k-YG生成的拓?fù)鋱D邊干擾比較

實(shí)驗(yàn)場(chǎng)景[8]為20×20×20的三維空間,節(jié)點(diǎn)的最大發(fā)射功率為9,節(jié)點(diǎn)數(shù)從50到175遞增,β值取2。實(shí)驗(yàn)分別比較了干擾較弱(s=0)時(shí)不同容錯(cuò)度k=1,k=2和k=3三種情況下,三種拓?fù)淇刂扑惴ǖ哪芎膬?yōu)化效果。當(dāng)容錯(cuò)度k取1、2、3三個(gè)不同值時(shí),仿真結(jié)果都是一致的:OVFSS算法降低節(jié)點(diǎn)能耗的能力都是優(yōu)于其它兩種拓?fù)淇刂扑惴ā_@里只給出k=3時(shí)三種拓?fù)淇刂扑惴ǖ姆抡娼Y(jié)果。

由圖5可知,在同樣大小的區(qū)域內(nèi),隨著網(wǎng)絡(luò)內(nèi)部署的節(jié)點(diǎn)數(shù)的增加,網(wǎng)絡(luò)節(jié)點(diǎn)密集程度上升,由于采用多跳短距離通信代替長(zhǎng)距離通信,節(jié)點(diǎn)可以使用更小的傳輸功率來發(fā)送信息給鄰居節(jié)點(diǎn),再由鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā),3D k-GG、3D k-YG、OVFSS算法都能有效地調(diào)整節(jié)點(diǎn)傳輸功率,保證網(wǎng)絡(luò)在k連通,并且在節(jié)點(diǎn)數(shù)目相同時(shí),OVFSS算法在減小能耗方面要比其他兩個(gè)拓?fù)淇刂扑惴ㄐЧ谩?/p>

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

Figure 5 Comparison of node transmission power among OVFSS,3D k-GG and 3D k-YG topology subgraph圖5 OVFSS、3D k-GG和3D k-YG生成的拓?fù)鋱D節(jié)點(diǎn)傳輸功率比較

本文針對(duì)Ad Hoc網(wǎng)絡(luò)可能應(yīng)用在通信環(huán)境發(fā)生變化的場(chǎng)景,提出了一種更加真實(shí)的三維場(chǎng)景下優(yōu)化目標(biāo)可變的、保證k連通的容錯(cuò)拓?fù)淇刂扑惴?,在干擾較強(qiáng)時(shí),降低干擾并盡量節(jié)能;干擾較小時(shí),重點(diǎn)考慮節(jié)能。并證明了該算法得到的通信子圖干擾最小,并保證k連通。真實(shí)應(yīng)用場(chǎng)景通信環(huán)境復(fù)雜,優(yōu)化目標(biāo)側(cè)重點(diǎn)應(yīng)該變化,需要綜合考慮干擾優(yōu)化,根據(jù)剩余能耗選擇鏈路、網(wǎng)絡(luò)容錯(cuò)性能、應(yīng)用服務(wù)質(zhì)量QoS(Quality of Service)保證等諸多問題,如何更加全面、合理地設(shè)置各部分影響因素對(duì)算法的影響需要進(jìn)一步研究。

[1] Wang Dong,Chen Wen-bin,Li Xiao-h(huán)ong,et al.Distributed topology control algorithm for ad hoc networks using steered beam directional antennas[J].Journal of Computer Research and Development,2010,47(3):407-415.(in Chinese)

[2] Chew L P.There is a planar graph almost as good as the complete graph[C]∥Proc of the 2nd Annual Symposium on Computational Geometry(SCG’86),1986:169-177.

[3] Wang Y,Li X Y.Minimum power assignment in wireless ad hoc networks with spanner property[J].Journal of Combinatorial Optimization,2006,11(1):99-112.

[4] Shpungin H,Segal M.Near optimal multi-criteria spanner constructions in wireless ad-h(huán)oc networks[C]∥Proc of IEEE INFOCOM’09,2009:163-171.

[5] Rickenbach P V,Wattenhofer R,Zollinger A.Algorithmic models of interference in wireless ad hoc and sensor networks[J].IEEE/ACM Transactions on Networking(TON),2009,17(1):172-185.

[6] Renato E N,Celso C R,Christophe D.Optimal solutions for fault-tolerant topology control in wireless ad hoc networks[J].IEEE Transactions on Wireless Communications,2009,8(12):5970-5981.

[7] Li L,Lian L,Bin H.Algorithms for k-fault tolerant power assignments in wireless sensor networks[J].Science China Information Sciences,2010,53(12):2527-2537.

[8] Indranil S,Lokesh K S,Subhas K G,et al.Distributed faulttolerant topology control in wireless multi-h(huán)op networks[J].Wireless Networks,2010,16(6):1511-1524.

[9] Wang Y,Cao L,Teresa A,et al.Self-organizing fault-tolerant topology control in large-scale three-dimensional wireless networks[J].ACM Transactions on Autonomous and Adaptive Systems(TAAS),2009,4(3):1-21.

[10] Rodoplu V,Meng T H.Minimum energy mobile wireless networks[J].IEEE Journal on Selected Areas in Communications,1999,17(8):1333-1344.

[11] Cardieri P.Modeling interference in wireless ad hoc networks[J].IEEE Communications Surveys &Tutorials,2010,12(4):551-572.

[12] Kruskal J B.On the shortest spanning subtree of a graph and the traveling salesman problem[C]//Proc of the American Mathematical Society,1956:48-50.

[13] Wang D,Long W C,Li X H.Interference-aware fault-tolerant energy spanner in wireless ad hoc networks[J].International Journal of Distributed Sensor Networks 2012,Article ID 235374,doi:10.1155/2012/235374.

附中文參考文獻(xiàn):

[1] 王東,陳文斌,李曉鴻,等.自組網(wǎng)中基于自適應(yīng)波束天線的拓?fù)淇刂扑惴ǎ跩].計(jì)算機(jī)研究與發(fā)展,2010,47(3):407-415.

猜你喜歡
拓?fù)鋱D原圖子圖
低壓配網(wǎng)拓?fù)鋱D自動(dòng)成圖關(guān)鍵技術(shù)的研究與設(shè)計(jì)
簡(jiǎn)單拓?fù)鋱D及幾乎交錯(cuò)鏈環(huán)補(bǔ)中的閉曲面
基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼
完形:打亂的拼圖
孩子(2019年5期)2019-05-20 02:52:44
臨界完全圖Ramsey數(shù)
大家來找茬
基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
出版原圖數(shù)據(jù)庫(kù)遷移與備份恢復(fù)
基于拓?fù)湟?guī)則Pb-S-O體系優(yōu)勢(shì)區(qū)圖的繪制與應(yīng)用

石景山区| 衡山县| 青海省| 白朗县| 昭苏县| 松溪县| 大化| 满洲里市| 彰化县| 刚察县| 壶关县| 巴青县| 老河口市| 丹阳市| 泸州市| 朝阳市| 吴堡县| 汤原县| 漾濞| 敖汉旗| 潍坊市| 永仁县| 大港区| 屯门区| 平遥县| 丹阳市| 东港市| 惠安县| 界首市| 绍兴县| 文登市| 松阳县| 湾仔区| 名山县| 吴川市| 彩票| 双流县| 镇康县| 大丰市| 永城市| 德保县|