無線傳感器網絡中基于魯棒優化的功率控制

喬俊峰,劉三陽,齊小剛

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.南陽理工學院數理學院,河南南陽 473004)

無線傳感器網絡中基于魯棒優化的功率控制

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

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.南陽理工學院數理學院,河南南陽 473004)

基于魯棒離散優化理論與方法,設計了一種對距離不確定性具有免疫力的功率控制方法.首先,介紹了魯棒優化的相關知識;然后,建立了魯棒最小生成樹模型進行距離不確定情形下的功率控制,并設計了基于Prim算法的求解方法.計算機仿真研究了模型中調節參數對網絡性能的影響,結果表明,魯棒解在距離不確定時得到的目標值優于確定解,而在標稱距離下與最優值相差不多.因此,隨著不確定性的增加,魯棒解僅以較小的最優性損失改善了最壞情形下網絡的拓撲性能.

無線傳感器網絡;功率控制;魯棒優化;最小生成樹

作為組網和通信的基礎,無線傳感器網絡的拓撲控制能夠直接影響網絡性能的各個方面[1].功率控制是拓撲控制的一種方式,在滿足網絡連通的前提下,它為每個節點選擇最優的發射功率,以延長網絡的生存時間或增加網絡容量.

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

在信息傳輸的過程中,節點間距是一個很重要的參數,以上算法的最優性均取決于節點間距離的精度.遺憾的是,由于測量誤差、環境干擾和人為攻擊等因素的影響,導致距離測量存在多種不確定因素,而會進一步影響到與距離密切相關的功率控制.現有功率控制方法大多對不確定性因素忽略或進行簡化處理,使其在實際應用中最優性無法保證甚至不可行.因此,在不確定環境下設計具有魯棒性的功率控制技術成為目前迫切需要解決的問題.

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

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

1　魯棒組合優化方法

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

假設c為n維向量,考慮包含n個變量的0-1組合優化問題,即

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

為控制解的魯棒性與保守性,引入調節參數Γ∈{0,1,2,…,n},表示可能產生偏離的目標系數的最大個數.特別地,如果Γ=0,則意味著可完全忽略目標系數偏離所產生的影響;而當Γ=n時,則考慮所有可能的系數偏離,此時解的魯棒性最強,但同時也最保守.Γ的取值取決于決策者對于魯棒性和目標最優性的偏好,一般來講,如果決策者要求解對不確定環境免疫力強,則增加Γ的值.

當至多有Γ個目標系數發生變動時,為找出此時最壞情況下的最優值,需要求解問題式(1)的魯棒對應問題[14],即

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

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

由定理1可以看出,對于含n個變量的組合優化問題,如果僅目標參數存在不確定性,其魯棒解只需通過求解至多n+1個標稱問題就可得到.因此,多項式時間可求解的組合優化問題其魯棒對應問題仍然用多項式時間可求解.

2　問題描述與求解

2.1問題模型的建立

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

功率控制通常可簡化為通信半徑分配問題(Range Assignment,RA)[2],即對于給定的節點集V={1,2,…,N},如何為V中每個節點i分配通信半徑Rc(i),在保證網絡連通的前提下,使網絡中各節點的發射功率之和最小,即

其中,α為路徑衰減指數,取決于網絡的環境因素.當節點部署在二維或三維空間時,功率控制是一個非確定多項式(Non-deterministic Polynomial,NP)難問題,因此,一般采用近似算法來解決,基本思想都是通過降低發射功率來延長網絡生命.

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

其中,用ET表示最大功率圖的某個生成樹T=(V,ET)所包含的邊集,N為節點總數.

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

2.2問題模型的求解

最小生成樹可以用Prim算法或Kruskal算法求出,二者均為多項式時間算法.以最大功率圖Gmax= (V,Emax)為例,Prim算法的時間復雜度為O(N2),僅與節點個數有關,適合于稠密圖.而Kruskal算法的時間復雜度為,僅與邊的數目有關,適合于稀疏圖.結合無線傳感器網絡的大規模特點,這里采用Prim算法求解.

將問題式(7)中的目標函數進行整理,可以得到

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

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

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

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

Step 5 根據得到的最優解所對應的最小生成樹T=(V,ET),為每個節點i∈V分配傳輸半徑,即Rc(i) =

3　仿真實驗

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

為比較魯棒解和確定解在確定和不確定距離參數下的性能,給出以下兩個指標[13]:

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

為考察魯棒解在確定和不確定距離參數下的性能,隨機產生100個網絡,讓權值的偏離系數γ從0.1變化至3.0,對應于每個γ統計出功率控制后的指標Rac和Rwc.圖1為魯棒調節參數Γ分別取10和20時指標Rac和Rwc的變化情況,每個指標均為100個網絡的平均值.可以看出,無論Γ取何值,魯棒解在最壞情形下的性能始終優于確定解,而在確定情況下僅損失了少量最優性.隨著權值不確定性的增加,魯棒解的這種優勢表現得更為明顯.進一步觀察不同魯棒調節參數下兩指標的對比,隨著調節參數的增加,對應于同一權值偏離系數,魯棒解在標稱情況下的最優性損失變化極其微小;而在最壞情況下,Γ=20時的Rwc值略低于Γ=10時的Rwc值,這主要是由于增加魯棒調節參數Γ的值相應地增加了魯棒解的最優值,而此時確定解在最壞情形下的目標值并未改變,從而導致Rwc的降低.

為進一步觀察不確定距離參數下魯棒解的穩定性,對應于同一網絡的每個權值偏離系數,隨機產生1 000個干擾樣本,統計出式(10)中各目標的均值及標準差,如圖2所示,這里魯棒調節參數Γ取值為10.可以看出,隨著不確定性的增加,與最壞情況下的確定解相比,魯棒解的最優值及其在標稱距離下的目標均值變化較為緩慢,且標準差變化的較為均衡.這說明魯棒解能夠應對距離參數的不確定性,所提供的解決方案在實際應用中能夠平穩執行.

圖1　不同權值偏離系數下Rac和Rwc的變化

圖2　不同權值偏離系數下各目標均值及標準差的變化(Γ=10)

4　結束語

簡要介紹了魯棒離散優化的基本理論與方法,基于0-1魯棒離散優化方法,解決了無線傳感器網絡中不確定距離下的功率控制問題.文中首先將功率控制問題歸結為求解最小生成樹模型,然后將模型轉化為包含魯棒調節參數的魯棒對應問題,并設計了基于Prim算法的求解方法.仿真結果表明,魯棒解在距離不確定性時能夠有效避免網絡拓撲性能惡化,而且所提供的這種保護只需付出較少的目標值代價,而且隨著實際應用中距離不確定性的增加,魯棒解為網絡提供了性能穩定的功率控制方案.

[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]張學,陸桑璐,陳貴海,等.無線傳感器網絡的拓撲控制[J].軟件學報,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]劉逵,劉三陽.利用簇收縮策略的傳感器節點重要性評估算法[J].西安電子科技大學學報,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 網絡出版時間:2015-12-10

國家自然科學基金資助項目(61373174);廣東省高等學校高層次人才資助項目(粵財教[2013]246號)

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

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.030.html