優(yōu)化目標(biāo)可變的容錯(cuò)三維拓?fù)淇刂扑惴ǎ?/h1>
2014-03-23 06:03:06王東，鄧好
計(jì)算機(jī)工程與科學(xué) 2014年5期
王 東，鄧 好
（湖南大學(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.
猜你喜歡
低壓配網(wǎng)拓?fù)鋱D自動(dòng)成圖關(guān)鍵技術(shù)的研究與設(shè)計(jì)電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12 簡(jiǎn)單拓?fù)鋱D及幾乎交錯(cuò)鏈環(huán)補(bǔ)中的閉曲面數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22 基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55 完形：打亂的拼圖孩子(2019年5期)2019-05-20 02:52:44 臨界完全圖Ramsey數(shù)同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版)(2019年2期)2019-04-02 05:43:48 大家來找茬數(shù)位時(shí)尚(幼兒教育)(2017年12期)2018-01-05 01:23:30 基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦電子科技大學(xué)學(xué)報(bào)(2016年2期)2016-08-31 02:50:00 不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年1期)2014-04-16 02:54:50 出版原圖數(shù)據(jù)庫(kù)遷移與備份恢復(fù)測(cè)繪科學(xué)與工程(2014年6期)2014-02-27 07:06:23 基于拓?fù)湟?guī)則Pb-S-O體系優(yōu)勢(shì)區(qū)圖的繪制與應(yīng)用中國(guó)有色金屬學(xué)報(bào)(2013年3期)2013-12-14 07:44:22
王 東，鄧 好
（湖南大學(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.
猜你喜歡
電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12
數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22
華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55
孩子(2019年5期)2019-05-20 02:52:44
同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版)(2019年2期)2019-04-02 05:43:48
數(shù)位時(shí)尚(幼兒教育)(2017年12期)2018-01-05 01:23:30
電子科技大學(xué)學(xué)報(bào)(2016年2期)2016-08-31 02:50:00
華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年1期)2014-04-16 02:54:50
測(cè)繪科學(xué)與工程(2014年6期)2014-02-27 07:06:23
中國(guó)有色金屬學(xué)報(bào)(2013年3期)2013-12-14 07:44:22
