無線傳感器網(wǎng)絡(luò)中基于魯棒優(yōu)化的功率控制

喬俊峰,劉三陽,齊小剛

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.南陽理工學(xué)院數(shù)理學(xué)院,河南南陽 473004)

無線傳感器網(wǎng)絡(luò)中基于魯棒優(yōu)化的功率控制

喬俊峰1,2,劉三陽1,齊小剛1

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.南陽理工學(xué)院數(shù)理學(xué)院,河南南陽 473004)

基于魯棒離散優(yōu)化理論與方法,設(shè)計(jì)了一種對(duì)距離不確定性具有免疫力的功率控制方法.首先,介紹了魯棒優(yōu)化的相關(guān)知識(shí);然后,建立了魯棒最小生成樹模型進(jìn)行距離不確定情形下的功率控制,并設(shè)計(jì)了基于Prim算法的求解方法.計(jì)算機(jī)仿真研究了模型中調(diào)節(jié)參數(shù)對(duì)網(wǎng)絡(luò)性能的影響,結(jié)果表明,魯棒解在距離不確定時(shí)得到的目標(biāo)值優(yōu)于確定解,而在標(biāo)稱距離下與最優(yōu)值相差不多.因此,隨著不確定性的增加,魯棒解僅以較小的最優(yōu)性損失改善了最壞情形下網(wǎng)絡(luò)的拓?fù)湫阅?

無線傳感器網(wǎng)絡(luò);功率控制;魯棒優(yōu)化;最小生成樹

作為組網(wǎng)和通信的基礎(chǔ),無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂颇軌蛑苯佑绊懢W(wǎng)絡(luò)性能的各個(gè)方面[1].功率控制是拓?fù)淇刂频囊环N方式,在滿足網(wǎng)絡(luò)連通的前提下,它為每個(gè)節(jié)點(diǎn)選擇最優(yōu)的發(fā)射功率,以延長網(wǎng)絡(luò)的生存時(shí)間或增加網(wǎng)絡(luò)容量.

功率控制與圖論之間的關(guān)系密不可分,其基本方法是借助圖論來建立網(wǎng)絡(luò)的數(shù)學(xué)模型,且求解方法也大多源于圖論中的基本算法[2-3].按照構(gòu)造拓?fù)鋾r(shí)所使用的信息類型進(jìn)行劃分,功率控制可分為基于位置、基于方向和基于鄰居3類[4].基于位置的功率控制利用節(jié)點(diǎn)位置以中心式或分布式的方式為每個(gè)節(jié)點(diǎn)分配傳輸功率,適用于規(guī)模較小、對(duì)感知數(shù)據(jù)準(zhǔn)確性和敏感度要求較高的網(wǎng)絡(luò)環(huán)境,如算法最小生成樹(Minimum Spanning Tree,MST)算法、Rodoplu和Meng共同提出的R&M算法[4]、局部最小生成樹(Local Minimum Spanning Tree,LMST)算法[5]等均屬于這一類.基于位置的功率控制需要精確的位置信息,可通過為每個(gè)節(jié)點(diǎn)或部分節(jié)點(diǎn)配備GPS裝置來實(shí)現(xiàn).雖然這會(huì)增加節(jié)點(diǎn)成本,但同時(shí)減少了因信息交換所產(chǎn)生的開銷.基于方向的功率控制無需節(jié)點(diǎn)的位置信息,但是要求節(jié)點(diǎn)能夠估計(jì)出自身與鄰節(jié)點(diǎn)間的相對(duì)方向,代表性的算法有錐形拓?fù)淇刂芠2]和分布式相對(duì)鄰近圖[5]等.基于鄰居的功率控制,如算法k鄰圖[6]和典型拓?fù)淇刂芠2]等,要求節(jié)點(diǎn)能夠獲取其鄰節(jié)點(diǎn)的ID,并且能夠根據(jù)距離或鏈路質(zhì)量等指標(biāo)對(duì)鄰節(jié)點(diǎn)進(jìn)行排序,尤其適用于移動(dòng)網(wǎng)絡(luò).由于無線傳感器網(wǎng)絡(luò)是與應(yīng)用相關(guān)的網(wǎng)絡(luò),因此,可根據(jù)不同的應(yīng)用環(huán)境和設(shè)計(jì)目標(biāo),選擇合適的功率控制算法.

在信息傳輸?shù)倪^程中,節(jié)點(diǎn)間距是一個(gè)很重要的參數(shù),以上算法的最優(yōu)性均取決于節(jié)點(diǎn)間距離的精度.遺憾的是,由于測量誤差、環(huán)境干擾和人為攻擊等因素的影響,導(dǎo)致距離測量存在多種不確定因素,而會(huì)進(jìn)一步影響到與距離密切相關(guān)的功率控制.現(xiàn)有功率控制方法大多對(duì)不確定性因素忽略或進(jìn)行簡化處理,使其在實(shí)際應(yīng)用中最優(yōu)性無法保證甚至不可行.因此,在不確定環(huán)境下設(shè)計(jì)具有魯棒性的功率控制技術(shù)成為目前迫切需要解決的問題.

處理模型中數(shù)據(jù)不確定性的方法主要有隨機(jī)規(guī)劃和魯棒優(yōu)化.隨機(jī)規(guī)劃一方面需要精確的數(shù)據(jù)分布,而這在很多實(shí)際問題中無法獲取;另一方面隨著樣本數(shù)的增加,所產(chǎn)生的新問題的規(guī)模會(huì)急劇增加,從而帶來“海量”計(jì)算.魯棒優(yōu)化是近年來發(fā)展起來的一種處理不確定參數(shù)優(yōu)化問題的重要方法[7],它無需數(shù)據(jù)的概率分布,只是假設(shè)數(shù)據(jù)屬于所謂的不確定集中,然后將不確定優(yōu)化模型轉(zhuǎn)化為魯棒對(duì)應(yīng)的確定模型,研究當(dāng)數(shù)據(jù)在不確定集中變化時(shí)確定模型的最優(yōu)解,即魯棒解.魯棒優(yōu)化以其對(duì)數(shù)據(jù)特征要求低及計(jì)算可操作性而廣受關(guān)注,其理論和應(yīng)用都取得了長足發(fā)展[8-12].

文獻(xiàn)[13]將魯棒優(yōu)化引入到無線傳感器網(wǎng)絡(luò)中,用于解決最大網(wǎng)絡(luò)生命等模型中的距離不確定性.筆者借助魯棒離散優(yōu)化的理論和方法,建立了距離不確定情況下功率控制的魯棒最小生成樹模型,并設(shè)計(jì)了基于Prim算法的方法進(jìn)行求解.仿真表明,隨著不確定性的增加,與固定情況下的最優(yōu)解相比,魯棒解僅以較小的最優(yōu)性代價(jià)改善了最壞情形下的網(wǎng)絡(luò)性能.

1　魯棒組合優(yōu)化方法

魯棒優(yōu)化的關(guān)鍵在于通過合理選取不確定集,并利用對(duì)偶理論將原問題轉(zhuǎn)化為與之等價(jià)或近似且容易計(jì)算的魯棒對(duì)應(yīng)問題.文獻(xiàn)[14]為不確定離散優(yōu)化建立了新的魯棒優(yōu)化方法,能夠通過保護(hù)度參數(shù)控制魯棒解的保守度,且在理論和實(shí)踐中也是計(jì)算可行的.文中主要利用Bertsimas的方法解決距離不確定情況下的功率控制問題,下面具體給出該方法.

假設(shè)c為n維向量,考慮包含n個(gè)變量的0-1組合優(yōu)化問題,即

其中,x表示由n個(gè)決策變量所構(gòu)成的向量.假設(shè)僅目標(biāo)函數(shù)中的參數(shù)c=(c1,c2,…,cn)不確定.在許多典型應(yīng)用中,雖然無法獲知不確定參數(shù)的精確分布,但能夠合理估計(jì)出它的均值和變化幅度.對(duì)于不確定系數(shù)cj,j∈I={1,2,…,n},將其視為獨(dú)立有界的隨機(jī)變量,假設(shè)其取值區(qū)間為[j,j+dj],其中j,為標(biāo)稱值; dj≥0,表示標(biāo)稱值的偏離值.因此,參數(shù)的不確定集U={c|cj∈[j,j+dj],j∈I}.顯然,當(dāng)dj=0時(shí),系數(shù)cj未發(fā)生偏離.

為控制解的魯棒性與保守性,引入調(diào)節(jié)參數(shù)?！蕒0,1,2,…,n},表示可能產(chǎn)生偏離的目標(biāo)系數(shù)的最大個(gè)數(shù).特別地,如果Γ=0,則意味著可完全忽略目標(biāo)系數(shù)偏離所產(chǎn)生的影響;而當(dāng)Γ=n時(shí),則考慮所有可能的系數(shù)偏離,此時(shí)解的魯棒性最強(qiáng),但同時(shí)也最保守.Γ的取值取決于決策者對(duì)于魯棒性和目標(biāo)最優(yōu)性的偏好,一般來講,如果決策者要求解對(duì)不確定環(huán)境免疫力強(qiáng),則增加Γ的值.

當(dāng)至多有Γ個(gè)目標(biāo)系數(shù)發(fā)生變動(dòng)時(shí),為找出此時(shí)最壞情況下的最優(yōu)值,需要求解問題式(1)的魯棒對(duì)應(yīng)問題[14],即

問題式(2)為非線性優(yōu)化問題,難于求解.不失一般性,假設(shè)d1≥d2≥…≥dn,為表示方便,定義dn+1=0.

定理1 問題式(2)可以通過求解下面n+1個(gè)標(biāo)稱問題得到[14]:

由定理1可以看出,對(duì)于含n個(gè)變量的組合優(yōu)化問題,如果僅目標(biāo)參數(shù)存在不確定性,其魯棒解只需通過求解至多n+1個(gè)標(biāo)稱問題就可得到.因此,多項(xiàng)式時(shí)間可求解的組合優(yōu)化問題其魯棒對(duì)應(yīng)問題仍然用多項(xiàng)式時(shí)間可求解.

2　問題描述與求解

2.1問題模型的建立

假設(shè)無線傳感器網(wǎng)絡(luò)中N個(gè)節(jié)點(diǎn)分布在二維歐氏感知區(qū)域內(nèi),節(jié)點(diǎn)集V={1,2,…,N}.對(duì)于每個(gè)節(jié)點(diǎn)i∈V,其通信半徑用Rc(i)表示.網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最大通信半徑為Rmax,節(jié)點(diǎn)i可在區(qū)間(0,Rmax]上動(dòng)態(tài)改變其通信半徑Rc(i).假設(shè)無線信道傳播服從對(duì)數(shù)路徑損耗模型[4],此時(shí)通信半徑與傳輸功率間一一對(duì)應(yīng),因此對(duì)這兩個(gè)概念可不加區(qū)分.當(dāng)所有節(jié)點(diǎn)都以最大通信半徑Rmax通信時(shí),所生成的通信圖Gmax=(V,Emax),稱為最大功率圖,其中,Emax={(i,j)|d(i,j)≤Rmax,i,j∈V},d(i,j)表示節(jié)點(diǎn)i與j間的距離.

功率控制通?？珊喕癁橥ㄐ虐霃椒峙鋯栴}(Range Assignment,RA)[2],即對(duì)于給定的節(jié)點(diǎn)集V={1,2,…,N},如何為V中每個(gè)節(jié)點(diǎn)i分配通信半徑Rc(i),在保證網(wǎng)絡(luò)連通的前提下,使網(wǎng)絡(luò)中各節(jié)點(diǎn)的發(fā)射功率之和最小,即

其中,α為路徑衰減指數(shù),取決于網(wǎng)絡(luò)的環(huán)境因素.當(dāng)節(jié)點(diǎn)部署在二維或三維空間時(shí),功率控制是一個(gè)非確定多項(xiàng)式(Non-deterministic Polynomial,NP)難問題,因此,一般采用近似算法來解決,基本思想都是通過降低發(fā)射功率來延長網(wǎng)絡(luò)生命.

一個(gè)無向連通圖的MST也是連通的,包含了原圖中的所有節(jié)點(diǎn),且所有邊的權(quán)重之和最小.MST的特點(diǎn)與功率控制的要求相符,故采用MST算法對(duì)節(jié)點(diǎn)進(jìn)行功率分配.根據(jù)式(4),以節(jié)點(diǎn)間距的指數(shù)作為邊的權(quán)值cij=d(i,j)α,則最大功率圖Gmax=(V,Emax)MST的0-1組合優(yōu)化模型為

其中,用ET表示最大功率圖的某個(gè)生成樹T=(V,ET)所包含的邊集,N為節(jié)點(diǎn)總數(shù).

在構(gòu)造MST的過程中,節(jié)點(diǎn)間距起著很重要的作用,它一般通過測量算法得到.受各種不確定因素影響,節(jié)點(diǎn)間距是帶誤差的數(shù)據(jù).如果測量值比真實(shí)值大,則節(jié)點(diǎn)會(huì)依據(jù)這個(gè)測量值增大發(fā)射功率,從而使能耗增加且競爭加劇,導(dǎo)致網(wǎng)絡(luò)能量快速消耗;如果測量值比真實(shí)值小,則節(jié)點(diǎn)會(huì)依據(jù)這個(gè)測量值減小發(fā)射功率,從而部分節(jié)點(diǎn)無法連通,造成網(wǎng)絡(luò)斷裂.因此,在尋找MST時(shí),有必要將不確定因素考慮進(jìn)來,使生成的MST對(duì)距離不確定性具有免疫力.利用文中第1部分的知識(shí),假設(shè)問題式(5)中目標(biāo)函數(shù)的權(quán)值所屬的不確定集U={c|cij∈[ij,ij+dij],(i,j)∈Emax},其中,ij表示權(quán)值的標(biāo)稱值,dij表示權(quán)值的偏離值,并引入魯棒調(diào)節(jié)參數(shù),則模型式(5)的魯棒對(duì)應(yīng)為

2.2問題模型的求解

最小生成樹可以用Prim算法或Kruskal算法求出,二者均為多項(xiàng)式時(shí)間算法.以最大功率圖Gmax= (V,Emax)為例,Prim算法的時(shí)間復(fù)雜度為O(N2),僅與節(jié)點(diǎn)個(gè)數(shù)有關(guān),適合于稠密圖.而Kruskal算法的時(shí)間復(fù)雜度為,僅與邊的數(shù)目有關(guān),適合于稀疏圖.結(jié)合無線傳感器網(wǎng)絡(luò)的大規(guī)模特點(diǎn),這里采用Prim算法求解.

將問題式(7)中的目標(biāo)函數(shù)進(jìn)行整理,可以得到

基于Prim算法求解問題式(8)和式(9),可得到不確定環(huán)境下功率控制的魯棒解.算法的具體步驟如下:

Step 1 令網(wǎng)絡(luò)的最大功率圖Gmax=(V,Emax),其中,.任取邊(i,j)∈Emax,賦權(quán)值cij=d(i,j)α,這里α為路徑衰減指數(shù).估計(jì)出權(quán)值所屬的不確定集U={c|cij∈[ij,ij+dij],(i,j)∈Emax},根據(jù)決策者需求選擇魯棒調(diào)節(jié)參數(shù)Γ.

Step 2 問題式(8)的求解:更新最大功率圖Gmax的權(quán)值cij=ij+dij,在更新后的圖上運(yùn)行Prim算法.假設(shè)此時(shí)最優(yōu)解為,得到的最小生成樹的權(quán)值之和為

Step 4 比較問題式(8)和式(9)的最優(yōu)值.

Step 5 根據(jù)得到的最優(yōu)解所對(duì)應(yīng)的最小生成樹T=(V,ET),為每個(gè)節(jié)點(diǎn)i∈V分配傳輸半徑,即Rc(i) =

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

為測試文中所建立的魯棒MST模型及其求解算法的性能,通過計(jì)算機(jī)仿真研究了距離不確定情況下的功率控制問題.將30個(gè)節(jié)點(diǎn)隨機(jī)散布在100×100的感知區(qū)域內(nèi),假設(shè)每個(gè)節(jié)點(diǎn)的最大通信半徑Rmax= 50.在仿真中,令權(quán)值的標(biāo)稱值ij=d(i,j)α,d(i,j)為距離的測量值,路徑衰減指數(shù)α=2.將權(quán)值的偏離值設(shè)置為dij=γij(γ≥0),顯然系數(shù)γ越大,權(quán)值的不確定性越強(qiáng).

為比較魯棒解和確定解在確定和不確定距離參數(shù)下的性能,給出以下兩個(gè)指標(biāo)[13]:

其中,d0為標(biāo)稱距離,一般取值為測量值,d為在不確定集中變化的距離;D(d0)為確定解的最優(yōu)值,D(dwc)為確定解在不確定數(shù)據(jù)最壞情況下的目標(biāo)值;R(d)為魯棒解的最優(yōu)值,R(d0)為魯棒解在確定數(shù)據(jù)(或稱為標(biāo)稱數(shù)據(jù))下的目標(biāo)值.第1個(gè)指標(biāo)Rac量化了魯棒解在確定情況下最優(yōu)性的相對(duì)損失,反映了魯棒解處理不確定性所付出的代價(jià);而第2個(gè)指標(biāo)Rwc則衡量了確定解在最壞情況下目標(biāo)值的相對(duì)增加,體現(xiàn)了魯棒解在最壞情況下能夠提供的最大保護(hù).

為考察魯棒解在確定和不確定距離參數(shù)下的性能,隨機(jī)產(chǎn)生100個(gè)網(wǎng)絡(luò),讓權(quán)值的偏離系數(shù)γ從0.1變化至3.0,對(duì)應(yīng)于每個(gè)γ統(tǒng)計(jì)出功率控制后的指標(biāo)Rac和Rwc.圖1為魯棒調(diào)節(jié)參數(shù)Γ分別取10和20時(shí)指標(biāo)Rac和Rwc的變化情況,每個(gè)指標(biāo)均為100個(gè)網(wǎng)絡(luò)的平均值.可以看出,無論Γ取何值,魯棒解在最壞情形下的性能始終優(yōu)于確定解,而在確定情況下僅損失了少量最優(yōu)性.隨著權(quán)值不確定性的增加,魯棒解的這種優(yōu)勢(shì)表現(xiàn)得更為明顯.進(jìn)一步觀察不同魯棒調(diào)節(jié)參數(shù)下兩指標(biāo)的對(duì)比,隨著調(diào)節(jié)參數(shù)的增加,對(duì)應(yīng)于同一權(quán)值偏離系數(shù),魯棒解在標(biāo)稱情況下的最優(yōu)性損失變化極其微小;而在最壞情況下,Γ=20時(shí)的Rwc值略低于Γ=10時(shí)的Rwc值,這主要是由于增加魯棒調(diào)節(jié)參數(shù)Γ的值相應(yīng)地增加了魯棒解的最優(yōu)值,而此時(shí)確定解在最壞情形下的目標(biāo)值并未改變,從而導(dǎo)致Rwc的降低.

為進(jìn)一步觀察不確定距離參數(shù)下魯棒解的穩(wěn)定性,對(duì)應(yīng)于同一網(wǎng)絡(luò)的每個(gè)權(quán)值偏離系數(shù),隨機(jī)產(chǎn)生1 000個(gè)干擾樣本,統(tǒng)計(jì)出式(10)中各目標(biāo)的均值及標(biāo)準(zhǔn)差,如圖2所示,這里魯棒調(diào)節(jié)參數(shù)Γ取值為10.可以看出,隨著不確定性的增加,與最壞情況下的確定解相比,魯棒解的最優(yōu)值及其在標(biāo)稱距離下的目標(biāo)均值變化較為緩慢,且標(biāo)準(zhǔn)差變化的較為均衡.這說明魯棒解能夠應(yīng)對(duì)距離參數(shù)的不確定性,所提供的解決方案在實(shí)際應(yīng)用中能夠平穩(wěn)執(zhí)行.

圖1　不同權(quán)值偏離系數(shù)下Rac和Rwc的變化

圖2　不同權(quán)值偏離系數(shù)下各目標(biāo)均值及標(biāo)準(zhǔn)差的變化(Γ=10)

4　結(jié)束語

簡要介紹了魯棒離散優(yōu)化的基本理論與方法,基于0-1魯棒離散優(yōu)化方法,解決了無線傳感器網(wǎng)絡(luò)中不確定距離下的功率控制問題.文中首先將功率控制問題歸結(jié)為求解最小生成樹模型,然后將模型轉(zhuǎn)化為包含魯棒調(diào)節(jié)參數(shù)的魯棒對(duì)應(yīng)問題,并設(shè)計(jì)了基于Prim算法的求解方法.仿真結(jié)果表明,魯棒解在距離不確定性時(shí)能夠有效避免網(wǎng)絡(luò)拓?fù)湫阅軔夯?而且所提供的這種保護(hù)只需付出較少的目標(biāo)值代價(jià),而且隨著實(shí)際應(yīng)用中距離不確定性的增加,魯棒解為網(wǎng)絡(luò)提供了性能穩(wěn)定的功率控制方案.

[1]LI M,LI Z J,VASILAKOS A V.A Survey on Topology Control in Wireless Sensor Networks:Taxonomy,Comparative Study,and Open Issues[J].Proceedings of the IEEE,2013,101(12):2538-2557.

[2]張學(xué),陸桑璐,陳貴海,等.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].軟件學(xué)報(bào),2007,18(4):943-954. ZHANG Xue,LU Sanglu,CHENG Guihai,et al.Topology Control for Wireless Sensor Networks[J].Journal of Software,2007,18(4):943-954.

[3]劉逵,劉三陽.利用簇收縮策略的傳感器節(jié)點(diǎn)重要性評(píng)估算法[J].西安電子科技大學(xué)學(xué)報(bào),2015,42(3):90-96. LIU Kui,LIU Sanyang.Novel Sensor Node Importance Evaluation Method Based on the Agglomeration Contraction Principle[J].Journal of Xidian University,2015,42(3):90-96.

[4]SANTI P.Topology Control in Wireless Ad Hoc and Sensor Networks[M].West Sussex:John Wiley&Sons Ltd,2005.

[5]LI N,HOU J C.Topology Control in Heterogeneous Wireless Networks:Problems and Solutions[C]//Proceedings of the IEEE Conference on Computer Communications.Piscataway:IEEE,2004:232-243.

[6]BLOUGH D M,LEONCINI M,RESTA G.The k-neighbors Protocol for Symmetric Topology Control in Ad Hoc Networks[C]//Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York:ACM,2003:141-152.

[7]BERTSIMAS D,BROWN D B,CARAMANIS C.Theory and Applications of Robust Optimization[J].SIAM Review,2011,53(3):464-501.

[8]BEN-TAL A,GHAOUI L E,NEMIROVSKI A.Robust Optimization[M].Princeton:Princeton University Press,2009.

[9]BEN-TAL A,HERTOG D D,WAEGENAERE D,et al.Robust Solutions of Optimization Problems Affected by Uncertain Probabilities[J].Management Science,2013,59(2):341-357.

[10]GABREL V,MURAT C,THIELE A.Recent Advances in Robust Optimization:an Overview[J].European Journal of Operational Research,2014,235(3):471-483.

[11]GORISSEN B L,YANIKOGLU I,HERTOG D.A Practical Guide to Robust Optimization[J].Omega,2015,53: 124-137.

[12]BEN-TAL A,HERTOG D D,VIAL J P.Deriving Robust Counterparts of Nonlinear Uncertain Inequalities[J].Mathematical Programming,2015,149(1):265-299.

[13]YE W,ORDONEZ F.Robust Optimization Models for Energy-limited Wireless Sensor Networks under Distance Uncertainty[J].IEEE Transactions on Wireless Communications,2008,7(6):2161-2169.

[14]BERTSIMAS D,SIM M.Robust Discrete Optimization and Networks Flows[J].Mathematical Programming,2003,98(1-3):49-71.

(編輯:齊淑娟)

Power control in wireless sensor networks based on robust optimization

QIAO Junfeng1,2,LIU Sanyang1,QI Xiaogang1
(1.School of Mathematics and Statistics,Xidian Univ.,Xi’an 710071,China; 2.School of Mathematics and Science,Nanyang Institute of Technology,Nanyang 473004,China)

Topology control is a critical issue for energy efficient wireless sensor networks.Distance between sensors plays an important role in the problem of topology control in that it directly determines the accuracy of the node position.However,distance is generally affected by uncertain external factors,such as measurement error and actual interference.The actual performance of a topology control strategy can be severely influenced by distance uncertainty.Based on the robust discrete optimization theory and methodology,a power control algorithm is proposed to deal with distance uncertainty.First,related works on robust optimization is introduced.Then the problem of power control is formulated as a robust minimum spanning tree model under distance uncertainty,which is solved by Prim’s algorithm.In computational experiments,the influence of the adjusting parameter on network performance is studied.Simulation results show that a robust solution can provide an improvement when the distance is uncertain at the expense of the less optimal value compared with a deterministic solution.

wireless sensor networks;power control;robust optimization;minimum spanning tree

TP393

A

1001-2400(2016)05-0081-07

10.3969/j.issn.1001-2400.2016.05.015

2015-07-28 網(wǎng)絡(luò)出版時(shí)間:2015-12-10

國家自然科學(xué)基金資助項(xiàng)目(61373174);廣東省高等學(xué)校高層次人才資助項(xiàng)目(粵財(cái)教[2013]246號(hào))

喬俊峰(1979-),女,副教授,西安電子科技大學(xué)博士研究生,E-mail:jfqiao@mail.xidian.edu.cn.

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.030.html