基于原始－對偶內點法的無線傳感網平均數據流最優傳輸研究

譚 力 俞 騰 劉枝辰

（浙江工業大學信息工程學院，浙江杭州310023）

0 引言

無線傳感器網絡[1]是由大量的靜止或移動的傳感器節點以自組織和多跳的方式構成的無線網絡，其目的是協作地感知、采集、處理和傳輸網絡覆蓋地理區域內感知對象的監測信息，并報告給用戶。 無線傳感網在環境、醫療、工業、建筑、空間和海洋探索以及軍事上方面具有廣泛的應用前景[2]。

其中數據路由[3]在無線傳感網中顯得十分重要，關鍵技術之一就是如何能夠在完整傳輸所有數據流的情況下，如何盡可能的平均每一條鏈路上的數據流。

1 數學模型

圖1 模擬的無線節點網絡圖

如圖1 所示， 無線傳感網抽象為有權圖， 節點的數量用n 表示，V＝｛v1，v2，…，vn｝表示網絡中節點所組成的非空集合；節點產生的數據用S 表示，即Sn表示第n 個節點產生的數據流；節點之間的鏈路用節點和節點之間的有向虛線線段表示，鏈路的集合用r 表示，rij表示第i 個節點向第j 個節點傳輸的數據流，r 表示所有數據流的平均，D（r）表示所有數據流的方差。 方差越大，表示數據流越不平均；反之，表示數據流越平均。

所以目標函數為：

為了優化分析的問題，并做如下假設：

a. 假設每一條鏈路所能承受的數據流大小存在一個極限值Rij，即：

b.假設所有的傳感器節點都可以收發數據，同時傳感器也會產生信息量，任意傳感器節點的所收發的數據量等于與之相連的各條鏈路上的數據流之和，即

c.每個節點之間都可以進行雙工通信，所以可以同時存在rij和rji兩條鏈路，定義平均數據流：

將式（3）化成矩陣形式可得A*r≤B（6），其中r＝［r12，r23，…，rij，r］，A 為不等式的系數矩陣，B 為不等式的常數矩陣；由式（4），（5）可得C*r＝D（7），其中r＝［r12，r23，…，rij，r］，C 為等式的系數矩陣，D 為等式的常數矩陣。

綜上所訴， 無線傳感網的均衡路由問題可用以下的數學模型表示：

2 原始-對偶內點法求解平均數據流最優解

由上述可知，平均數據流最優解是一個非線性規劃凸優化[4]問題。而原始-對偶內點法[5]是現代內點算法中最優秀的算法。它從理論上被證明具有多項式時間復雜性[6]。當約束條件和變量數目增加時，該算法的迭代次數隨著系統規模的變化比較小、收斂速度快、精度高，適合求解大規模非線性系統[7]。 原始-對偶內點法求解非線性規劃問題的步驟，可參考文獻[8-9]。 而該問題滿足原始對偶內點法的應用條件，所以可用原始-對偶內點法求解該問題，步驟如下：

Step0：初始化。 在任意取一組數據流數據r，只要滿足f1（x）＜0，…，fm（x）＜0，λ?0，μ＞1，εfeas＞0，ε＞0.，并且確定迭代的精度范圍。 在這里初始化μ＝10，εfeas＝10-8，ε＝10-8；

Step1： 確定解決問題的目標函數的不等式方程和等式方程的系數。 在該問題中目標函數是式（1），不等式方程的系數是A，等式方程的系數是C；

Step3：列出一個矩陣方程，如下：

其中rdual＝Δf0（x）+Df（x）Tλ+ETv，rcent＝-diag（λ）f（x）-（1/t）1，rpri＝E-b；

Step4：計算Δy（Δx，Δλ，Δv）；

Step5：計算線長s＝min（1.0，0.99/max（-dλ/λ）），并滿足s＞0；

Step6：更新y，使得y＝y+s*Δy；

3 仿真結果與討論

3.0 初始化各個數據

內點法初始數據εfeas＝10-8，ε＝10-8，μ＝10，α＝0.01，β＝0.5， 圖1 中各個節點的數據，以向量形式表示：S＝［9，7，-5，6，0，-3，-2，-4，-4，-4］。圖2 所示橫軸是次數，縱軸是迭代的值與最優解的差值；圖3 所示橫軸是次數，縱軸是迭代算出的值。

圖2 迭代次數與目標解差值

圖3 迭代次數與迭代算出的值

3.1 分析圖2 和圖3 得出如下結論

a.由圖2 可知，求出的值與目標的最優解不斷減小，說明該算法在上述初始條件下，是收斂的。且最后的差值在指定的誤差范圍內，驗證了該算法的可行性。

b.由圖3 可知，所求的最優解最后趨近于某一個數值，所以可以用這個值去非常近似的去代替真實的最優解，體現了原始對偶內點法的迭代。

3.2 比較

計算出的各個鏈路數據如圖4 所示：

圖4 仿真后的網絡圖

隨機給出的各個鏈路數據如圖5 所示：

圖5 隨機產生的網絡圖

通過對比最優解下的各個鏈路和隨機解得各個鏈路得到如下現象：

a.最優解下的鏈路的最大值為15.9866，而隨機解下的鏈路的最大值為17.5；同理，最優解最小值為4.4866，而隨機解下的最小值為0.5；

b.最優解下存在的最大值鏈路只有1 條，最小值只有1 條；而隨機解下最大值有3 條，最小值有3 條；

c. 最優解下平均的每條鏈路的信息量為8.9855， 大于隨機解的8.0055。

綜上所論，雖然求出的最優解的無線傳感網的信息量可能大于隨機解的無線傳感網的信息量，即總體耗電量可能偏大；但是隨機解中存在有很多的鏈路信息流很大，而其他鏈路信息流偏小，這樣容易導致部分鏈路上的通信擁塞以及某些節點耗電量的增加，不利于整個無線傳感網的維護。

4 結論

通過對上述10 個節點的拓撲圖的仿真計算， 驗證了用原始對偶內點法的可行性，所求出的解是收斂于真實的最優解。 并且證明了該算法可以求出在滿足整個無線傳感網數據流需求的情況下的平均數據流最優解。

而如果整個無線網絡如果能盡可能的滿足用該解法算出的結果，不僅能避免數據流在整個網絡上的擁堵；同時也能夠避免某幾個節點由于傳輸大量數據而導致電量消耗過快而引起整個無線傳感網無法正常工作的問題，提高了整個無線傳感網的穩定性。

［1］崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展，2005，42(1)：763-774.

［2］杜磊，詹曉，劉曼.無線傳感網應用現狀[J].工會博覽：理論研究，2011(11).

［3］樊凱，李令雄，龍冬陽.無線mesh 網中網絡編碼感知的按需無線路由協議的研究[J].通信學報，2009，30(1).

［4］范宏，韋化.基于擾動KKT 條件的原始一對偶內點法和分支定界法的最優潮流研究[J].電力自動化設備，May.2004 Vol.24 No.5:5-6.

［5］劉小蘭，周密，何詣然.廣義凸優化問題的Fenchel-Lagrange 對偶[J].四川師范大學學報(自然科學版)，Jan，2008 V01.31.No.1：31-32.

［6］李勁波，周理.基于仿射變換內點算法的大電網無功優化[J].電網技術，1997，21(3)：22-24.LI Jin.bo.Zhou Li.An affine transformation based interior point algorithm for bulk power System var optimization [J].Power System Technology，1997，21(3)：22-24.

［7］WEI H，SASAKH，KUBOKAWA J，et al.Large scale hydro—thermal optimal power flow problems based on interior point nonlinear pr0gramming [J].IEEE Transactions on Power Systems，2000，15(1)：396-403.

［8］WEI H，SASAKI H，KUBOKAWA J，et a1.An interior point nonllinear programming for optimal power flow problems with a novel data strutcture[J].IEEE Transactions on Power Systems，1998，13(3)：870-877.

［9］郭靖，陳青.電力系統無功優化的原對偶內點剪法及其應用[J].電力自動化設備，2004，24(5)：41-43.