譚 力 俞 騰 劉枝辰

（浙江工業(yè)大學(xué)信息工程學(xué)院，浙江杭州310023）

0 引言

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

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

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

圖1 模擬的無線節(jié)點網(wǎng)絡(luò)圖

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

所以目標(biāo)函數(shù)為：

為了優(yōu)化分析的問題，并做如下假設(shè)：

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

b.假設(shè)所有的傳感器節(jié)點都可以收發(fā)數(shù)據(jù)，同時傳感器也會產(chǎn)生信息量，任意傳感器節(jié)點的所收發(fā)的數(shù)據(jù)量等于與之相連的各條鏈路上的數(shù)據(jù)流之和，即

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

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

綜上所訴， 無線傳感網(wǎng)的均衡路由問題可用以下的數(shù)學(xué)模型表示：

2 原始-對偶內(nèi)點法求解平均數(shù)據(jù)流最優(yōu)解

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

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

Step1： 確定解決問題的目標(biāo)函數(shù)的不等式方程和等式方程的系數(shù)。 在該問題中目標(biāo)函數(shù)是式（1），不等式方程的系數(shù)是A，等式方程的系數(shù)是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(tǒng)+s*Δy；

3 仿真結(jié)果與討論

3.0 初始化各個數(shù)據(jù)

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

圖2 迭代次數(shù)與目標(biāo)解差值

圖3 迭代次數(shù)與迭代算出的值

3.1 分析圖2 和圖3 得出如下結(jié)論

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

b.由圖3 可知，所求的最優(yōu)解最后趨近于某一個數(shù)值，所以可以用這個值去非常近似的去代替真實的最優(yōu)解，體現(xiàn)了原始對偶內(nèi)點法的迭代。

3.2 比較

計算出的各個鏈路數(shù)據(jù)如圖4 所示：

圖4 仿真后的網(wǎng)絡(luò)圖

隨機給出的各個鏈路數(shù)據(jù)如圖5 所示：

圖5 隨機產(chǎn)生的網(wǎng)絡(luò)圖

通過對比最優(yōu)解下的各個鏈路和隨機解得各個鏈路得到如下現(xiàn)象：

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

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

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

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

4 結(jié)論

通過對上述10 個節(jié)點的拓?fù)鋱D的仿真計算， 驗證了用原始對偶內(nèi)點法的可行性，所求出的解是收斂于真實的最優(yōu)解。 并且證明了該算法可以求出在滿足整個無線傳感網(wǎng)數(shù)據(jù)流需求的情況下的平均數(shù)據(jù)流最優(yōu)解。

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

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

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

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

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

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

［6］李勁波，周理.基于仿射變換內(nèi)點算法的大電網(wǎng)無功優(yōu)化[J].電網(wǎng)技術(shù)，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］郭靖，陳青.電力系統(tǒng)無功優(yōu)化的原對偶內(nèi)點剪法及其應(yīng)用[J].電力自動化設(shè)備，2004，24(5)：41-43.