無線傳感器網絡中能量高效的基站位置優(yōu)選算法

唐偉，郭偉

（電子科技大學 通信抗干擾技術國家級重點實驗室，四川 成都 611731）

1 引言

無線傳感器網絡（WSN, wireless sensor networks）具有廣泛的應用范圍，例如目標跟蹤、環(huán)境監(jiān)測、工業(yè)控制等[1]。該類網絡通常由一組傳感器節(jié)點和基站構成，且具有數(shù)據(jù)中心性質，即傳感器節(jié)點所收集的數(shù)據(jù)通過多跳方式匯集至基站，基站負責處理數(shù)據(jù)，并將數(shù)據(jù)傳遞至外網進行分析決策。節(jié)能路由算法一直都是該類網絡研究中的重點之一，目前已經有了不少相關研究[2～7]。然而，現(xiàn)有的研究中往往都假定基站位于網絡場景的幾何中心或者隨機分布于網絡中。本文假設傳感器節(jié)點的位置已經由應用需求所確定，而基站可以在一定空間范圍內布設。從路由的角度上看，最小網絡總能耗路由結構是一棵以基站為根的最短路徑樹（SPT, shortest path tree），其中各鏈路長度是在該鏈路上傳遞單位比特數(shù)據(jù)的能耗。基站位置的優(yōu)選問題可以被歸結為一類非線性規(guī)劃問題，且問題的目標函數(shù)非光滑且非凸。對于此類問題，數(shù)學上通常采用的方法包括迭代下降算法以及啟發(fā)式搜索算法尋找問題的近似解。典型的迭代下降算法包括內點法、有效集法、依賴域法等[8]，對于非凸規(guī)劃問題，算法只能收斂到局部最優(yōu)解，且解的性能受初始點選擇影響很大。啟發(fā)式搜索算法包括基因算法、粒子群優(yōu)化（PSO, partical swarm optimization）算法等[9,10]，該類算法的計算復雜度較高，算法解的穩(wěn)定度也難以保證。由于沒有考慮問題自身的特點，直接采用這些通用算法往往導致算法效率低、精度差、不穩(wěn)定等問題。本文的研究從問題自身的特點入手，為問題設計簡單有效的算法。首先對目標函數(shù)分段光滑凸性質進行研究，提出并分析了最短路徑樹剖分的概念；然后，設計了3種啟發(fā)式算法（單點迭代下降、節(jié)點深度搜索以及多點迭代下降算法）。最后，通過仿真實驗驗證了所提算法的性能，并與PSO算法的結果作了對比分析，表明所提算法能夠有效地接近或收斂于問題的最優(yōu)解，且具有較好的穩(wěn)定性。

本文組織如下。第2節(jié)介紹系統(tǒng)模型，并提出能量高效的基站位置優(yōu)選問題；第3節(jié)分析目標函數(shù)分段光滑凸性質，并定義最短路徑樹剖分；第 4節(jié)研究二維空間中最短路徑樹剖分單元的結構；第5節(jié)提出3種啟發(fā)式算法；第6節(jié)通過仿真驗證了所提算法性能；第7節(jié)是結束語。

2 能量高效的基站位置優(yōu)選問題

2.1 系統(tǒng)模型

設無線傳感器網絡位于一個凸區(qū)域 A ??n中，基站位于區(qū)域A中的某點 ps。當節(jié)點i與節(jié)點j通信時，發(fā)送單位比特所需的最小發(fā)射能耗與鏈路距離的平方成正比[11]。

其中，εamp是發(fā)射功率增益（單位為J/bit/m2）， dij是節(jié)點i與 j之間的距離（單位為m）。為分析方便，假設每個傳感器節(jié)點都有足夠的最大發(fā)射功率能夠將區(qū)域A覆蓋。網絡可以被建模為一個有向連通圖G(?, E)，其中，表示傳感器節(jié)點集合V與基站集合{s}的并集，E表示鏈路的集合令節(jié)點i的鄰居集合為傳感器節(jié)點i的數(shù)據(jù)收集速率為Ri（單位為bit/s）。

2.2 能量高效的基站位置優(yōu)選問題

令鏈路(i,j)∈E上的網絡數(shù)據(jù)流為fij（單位為bit/s），對于任意傳感器節(jié)點iV∈，網絡中出入該節(jié)點的數(shù)據(jù)流守恒，于是有約束

節(jié)點i的能耗可以被表示為

故而，網絡總能耗可以被表示為

稱網絡流fij的系數(shù)為鏈路(i,j)的能耗系數(shù)。

本文提出能量高效的基站位置優(yōu)選問題：求解基站位置點 ps及網絡流 f={ fij}，使得網絡總能耗Cnet最小，可以被表示為如下非線性規(guī)劃[12]問題：

問題(4)的約束域是由網絡流 f所屬的多面體與基站位置ps所屬的凸區(qū)域A的笛卡爾乘積空間，因而是一個凸區(qū)域。然而，問題的目標函數(shù)是非光滑的非凸，這為問題的求解帶來了很大困難。

3 最短路徑樹剖分

3.1 系統(tǒng)模型

為了簡便起見，將問題(4)的目標函數(shù)表示為基站位置 ps與網絡流 f的函數(shù) C ( ps,f ) =Cnet。根據(jù)式(1)和式(3)，問題的目標函數(shù)隨著節(jié)點間距的增加而增大。于是，本文給出如下定理以簡化問題。

定理1 基站的最優(yōu)位置 ps必然在傳感器節(jié)點集合的凸包上。

其中， gk(x)是仿射函數(shù)。對于位于凸包之外的點 s1，必然存在至少一個 k0(1 ≤ k0≤ K )，使得gk0(s1) ＞ 0 。于是，令超平面則點 s1位于超平面?的一側，而所有傳感器節(jié)點位于該超平面的另一側或其上。

如圖1所示，點a是任意一個傳感器節(jié)點，點 s2是點s1在超平面?上的垂足。在Δas2s1中，∠as2s1≥π/4，因而得到as1＞as2。將基站選擇在凸包外的點 s1時，總存在凸包上的一個點 s2，使得當基站位于該點時，基站與任意傳感器節(jié)點之間的距離都更小。

圖1 基站不同位置與傳感器節(jié)點間距的關系

根據(jù)式(1)和式(3)，網絡總能耗隨著基站與傳感器節(jié)點間距的增加而增加。于是，基站在點 s2時網絡總能耗更小。由點 s1選擇的任意性知，使得網絡總能耗最小的基站必然在凸包上。

3.2 目標函數(shù)的分段光滑凸性質

從問題(4)的形式上看，將基站位置sp固定，問題就化為一個帶約束的線性規(guī)劃問題；而將網絡流f固定，問題就化為一個無約束的二次規(guī)劃問題。基于這樣的觀察，本文提出如下定理。

定理2 問題(4)的目標函數(shù)是一個分段函數(shù)，且每個分段是定義在多面體上的二次函數(shù)。

證明 當基站位于點 ps時，使網絡總能耗最小的網絡流 f對應于以基站為根的最短路徑樹T。令Hi={hi}表示所有從節(jié)點i到基站s的路徑集合，?(hi)表示該路徑中各段鏈路能耗系數(shù)之和，即注意到

于是， ? (hi)是 ps的二次函數(shù)，且對應二次項系數(shù)為εamp。令表示從節(jié)點i到基站s在最短路徑樹中的路徑，有于是，當且僅當基站位置滿足如下條件時，網絡最短路徑樹保持不變。

當基站位于每個這樣的多面體上時，網絡最短路徑樹不變，故而網絡流f也保持不變，于是網絡總能耗是關于基站位置ps的二次函數(shù)。

推論1 對任意網絡流f，基站的最優(yōu)位置ps的各坐標分量滿足

對于固定的網絡流f，基站的最優(yōu)位置 ps使得函數(shù)(ps)=C (ps,f )最小。由于各傳感器節(jié)點的坐標都是常數(shù)，而關于ps取值范圍的約束已被去除，故函數(shù)(ps)是關于點ps的二次函數(shù)。令：

即得式(7)。

根據(jù)推論1，在目標函數(shù)每個分段內應用式(7)，就能得到對應于任意網絡流的基站最佳位置。

3.3 最短路徑樹剖分

根據(jù)定理 2，只需在目標函數(shù)的各分段上運用推論1的結論，就能獲得問題(4)的全部局部最優(yōu)解，從而獲得全局最優(yōu)解。通過式(6)，可將n維空間剖分為若干區(qū)域。由此，本文給出如下定義。

定義1 定義最短路徑樹剖分單元為

在定理2的證明中，從節(jié)點i出發(fā)到基站s的全部路徑的集合 Hi中的元素個數(shù)為其中，P ( i, j)表示從j個元素中選取i個元素的排列數(shù)，直接通過式(6)計算目標函數(shù)各分段的復雜度太高。

定理 3 當且僅當基站位置 ps滿足如下條件時，網絡最短路徑樹T保持不變

證明 對于任意路徑 hi，表示為有

4 二維空間中SPT剖分單元的結構

首先，在二維空間中，式(11)可以被表示為一組二維線性不等式：

其中，αi是一個二維列向量，βi是一個常數(shù)。其邊界為如下線性方程對應的解：

該邊界方程的解可以被表示為單個參變量it的形式：

其中，A為-π/2單位旋轉變換矩陣

于是，Aαi是αi的正交補空間中的一組基。

然后，確定參數(shù)ti的取值范圍，就能夠得到對應SPT剖分單元在式(14)上的一條邊界。對于其他任意二維線性不等式：

要求找到ti，使xi對于任意 j都滿足式(17)。于是，將式(15)代入式(17)，得

記此時ti所對應的取值區(qū)間為Tij，且令：

則Tij可以被表示為

其中，當 μij=0時，LIi對應半平面的邊界與LIj對應半平面的邊界平行。此時，當νij＞0時，LIi對應半平面包含在 L Ij對應半平面中；當νij=0時，LIi對應半平面與 L Ij對應半平面重合；當νij＜0時，LIi對應半平面包含 L Ij對應半平面。故 ti的取值范圍為

如果Ti≠?，那么對應SPT剖分單元的一條邊是LIi對應半平面的邊界上的一條線段或一個點。如果Ti=?，表示對應SPT剖分單元是LIi對應的半平面內部的一個區(qū)域，SPT剖分單元的邊不與該半平面邊界相交。通過跨越SPT剖分單元邊界，就能對相鄰SPT剖分單元進行遍歷。

5 基站最優(yōu)位置的啟發(fā)式算法

5.1 單點迭代下降

本文設計了單點迭代下降（SPRD，single-point recursive descendent）算法。令基站初始位置為，通過Dijkstra算法[14]計算網絡最短路徑樹，得到對應的網絡流 f(0)。通過式(1)得到對應于網絡流 f(0)的最優(yōu)基站位置。重復以上步驟，直到基站位置不變。對于第k和 k + 1 次迭代，如果與屬于同一個SPT剖分單元，由于SPT剖分單元內最優(yōu)網絡流具有不變性，根據(jù)推論 1，那么對任意k′＞k，都有又因為SPT剖分單元的總數(shù)有限，算法能夠在有限步驟內收斂。算法收斂時迭代次數(shù)k的值稱為迭代深度。

5.2 節(jié)點深度搜索

證明 當基站位于 pi時，由于基站與節(jié)點i位于同一點上，任意節(jié)點通過節(jié)點i將數(shù)據(jù)轉發(fā)到基站與直接將數(shù)據(jù)傳給基站時的能耗是相同的。于是，令節(jié)點集合即將數(shù)據(jù)直接發(fā)送給基站s或者節(jié)點i的節(jié)點集合。注意到≥ 2 ，于是 Vi≠?。從 Vi中任選m≤個節(jié)點，令這些節(jié)點的數(shù)據(jù)直接傳給基站，而 Vi中的其他節(jié)點的數(shù)據(jù)經節(jié)點i轉發(fā)給基站，而原最短路徑樹中的其余鏈路不變，所得到的依然是一棵最短路徑樹。由此可知，每個位置 pi都位于某些 SPT剖分單元的交界。

根據(jù)定理 4，本文設計節(jié)點深度搜索（NDS，nodal depth search）算法。對于網絡中每個節(jié)點iV∈，可以通過點ip搜索相交于該點的非退化SPT剖分單元。對這些剖分單元計算對應網絡流的最優(yōu)基站位置以及對應該基站位置的網絡總能耗，可以得到基站最優(yōu)位置的一個近似解，稱此時的搜索深度為1。當搜索深度為k時，可以對所有已搜索剖分單元的相鄰剖分單元做進一步搜索，其中的最優(yōu)解作為搜索深度為 1k+ 時算法的解。記搜索深度為n的NDS算法為NDS-n。由于對于給定的有向圖，其生成樹的數(shù)量是有限的[15]。于是，當階數(shù)足夠大時，算法能夠遍歷其中所有剖分單元，因而能夠在有限步驟內收斂到全局最優(yōu)解。

5.3 多點迭代下降算法

將SPRD與NDS算法相比較，可以發(fā)現(xiàn)SPRD算法采用了深度優(yōu)先的搜索方法，沿著目標函數(shù)下降的方向搜索SPT剖分單元；而NDS算法采用了廣度優(yōu)先的搜索方法，對每個節(jié)點周圍的SPT剖分單元逐層遍歷。SPRD算法性能決定于初始點的選擇；而NDS算法收斂速率緩慢。本文將以上2種算法的優(yōu)點加以綜合，由此設計了多點迭代下降（MPRD，multiple-point recursive descendent）算法。算法分為 2個步驟，首先采用 NDS-n算法獲得深度為n的SPT剖分單元，以這些SPT剖分單元中的任意點作為初始點進行SPRD算法，并選擇最好的結果作為基站最優(yōu)位置的近似。對應于深度n的MPRD算法記為MPRD-n算法。定義MPRD算法的迭代深度為其中SPRD算法步驟的迭代深度。

6 仿真實驗

本文采用MATLAB對所提出的算法進行仿真。傳感器節(jié)點隨機分布于100 m × 1 00m 的矩形區(qū)域內，數(shù)據(jù)收集速率均勻隨機分布于0～1bit/s的范圍內。由于網絡總能耗與εamp成正比例關系，為簡便起見，設置 εamp= 1 J/bit/m2。

首先，演示10個傳感器節(jié)點的場景。如圖2所示，在XY平面上，10個編號的圓點表示傳感器節(jié)點，在XY平面上粗色黑線所圍成的區(qū)域表示這些傳感器節(jié)點的凸包，垂直于XY平面的虛線的垂足對應于基站的最佳位置。從圖中可以看到，基站的最佳位置是在上的，與定理1相符。XY平面經過SPT剖分，被劃分為若干SPT剖分單元，在同一剖分單元內網絡最短生成樹的結構保持不變。相同灰度的剖分單元表示以其中的任意點為初始點，經過SPRD算法之后會收斂于同一點。從圖中還可以看到，每個傳感器節(jié)點都位于某些剖分單元的交界上，與定理4相符。圖中的曲面表示目標函數(shù)的取值。曲面上粗線所圍成的區(qū)域對應于目標函數(shù)在各SPT剖分單元中的取值。可以看到，在各剖分單元內，目標函數(shù)是光滑凸函數(shù)，與定理2相符。

圖2 二維空間情形下目標函數(shù)的圖像

接下來，本文通過仿真實驗在節(jié)點數(shù)目為10～100個的網絡場景下對 SPRD、MPRD、NDS以及FMINC算法的性能進行研究。其中，F(xiàn)MINC算法是采用 MATLAB提供的帶約束非線性規(guī)劃求解函數(shù)[16]計算獲得的結果。

為對比算法性能，定義歸一化網絡總能耗Cnorm為算法所得網絡總能耗與最優(yōu)網絡總能耗的相對差，用百分比表示，即

其中，Calg表示算法性能，Copt表示最優(yōu)性能，該值通過NDS算法遍歷SPT單元求解。

由于所涉及的算法數(shù)量較多，本文分別用圖 3表示SPRD、NDS以及FMINC算法在不同網絡規(guī)模下所得歸一化網絡總能耗，而用圖4表示MPRD算法的性能。其中，SPRD及FMINC算法中基站位置初始點取值為

從圖3中發(fā)現(xiàn)SPRD算法的性能較差，這是因為SPRD算法的性能與初始點的選取有很大關系，難以通過簡單的方法獲得一個對各場景都有很好效果的初始點。由于FMINC算法采用最速下降算法，只能收斂到初始點鄰域內的局部最優(yōu)，例如局限在一個SPT單元中，不像SPRD算法的迭代過程具有一定的搜索深度，因而FMINC算法的性能更差。對于 NDS算法，隨著搜索深度的增加算法能夠遍歷更多的 SPT單元，因而性能也隨之提升。NDS-40算法能夠在所考慮的網絡規(guī)模下收斂到最優(yōu)解，并被用作式(22)中的Copt。

圖3 各算法歸一化網絡總能耗的比較

從圖4中不難看出，MPRD算法性能與最優(yōu)性能非常接近。MPRD算法通過NDS算法對SPT剖分單元的搜索，為SPRD算法選取了行之有效的初始點集合。由于MPRD算法在NDS算法的廣度優(yōu)先搜索的基礎上進行深度優(yōu)先搜索，因而其性能明顯優(yōu)于SPRD算法和NDS算法。這是因為NDS算法是一種廣度優(yōu)先搜索算法，當節(jié)點數(shù)目增多時，節(jié)點周圍的SPT剖分單元變得更加密集，因而往往需要更大的搜索深度才能獲得較好的解。而MPRD算法通過結合深度優(yōu)先搜索，可以得到更優(yōu)的解。

圖4 MPRD算法歸一化網絡總能耗的比較

圖5所示為SPRD和MPRD算法收斂時所需的平均迭代深度。從圖中可以看到，SPRD算法收斂時的迭代深度小于 MPRD算法，這是因為 MPRD算法具有更豐富的初始迭代點，能夠在更加深廣的范圍內搜索最優(yōu)解，隨著搜索深度的增加，算法能夠獲得更好的解，這與圖5中的結果是一致的。

圖5 SPRD和MPRD算法收斂時的平均迭代深度

由于目前針對非線性非凸非光滑規(guī)劃問題往往采用全局啟發(fā)式搜索方法，本文也進行了對比。本文采用 PSO工具包[17]，其中粒子數(shù)量與節(jié)點數(shù)量相同，每個場景下獨立運行20次算法，并對結果取均值。圖6所示為PSO算法的歸一化網絡總能耗，其中誤差線表示PSO算法所得的最大值。由于PSO算法的隨機搜索性質，算法能夠收斂到局部最優(yōu)，但不能保證每次都獲得全局最優(yōu)解，所得到的解具有一定的隨機性質。對比圖4，不難看出MPRD算法性能較好且較穩(wěn)定。

圖6 與PSO算法歸一化網絡總能耗的比較

7 結束語

無線傳感器網絡中，基站位置對網絡總能耗有很大影響，因而研究基站位置的節(jié)能優(yōu)選問題具有重要意義。由于問題在通常情況下是一類非光滑非凸規(guī)劃問題，為設計有效的求解算法，本文針對問題的目標函數(shù)和約束條件的性質進行研究。通過分析，本文為二維空間中的情形提出了3種啟發(fā)式算法，通過仿真實驗驗證了算法的有效性和收斂性。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8)∶ 102-114.

[2] APPADWEDULA S, VEERAVALLI V V, JONES D L. Energy-efficient detection in sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2005, 23(4)∶ 693-702.

[3] YANG Y, PRASSANA V K, KRISHNAMACHARI B. Energy minimization for real-time data gathering in wireless sensor networks[J].IEEE Transactions on Wireless Communications, 2006, 5(11)∶3087-3096.

[4] MING L, YUAN Z, JIANNONG C, et al. An energy-aware protocol for data gathering applications in wireless sensor networks[A]. IEEE International Conference on Communications (ICC’07)[C]. 2007.3629-3635.

[5] PANDANA C, LIU K J R. Robust connectivity-aware energy-efficient routing for wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(10)∶ 3904-3916.

[6] LIU X, HAENGGI M. Toward quasiregular sensor networks∶ topology control algorithms for improved energy efficiency[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(9)∶ 975-986.

[7] AMMARI H M, DAS S K. Promoting heterogeneity, mobility, and energy-aware voronoi diagram in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(7)∶995-1008.

[8] NOCEDAL J, WRIGHT S J. Numerical Optimization[M]. New York∶Springer-Verlag, 1999.

[9] SELVARAJAH K, KADIRKAMANATHAN V. Energy efficient sink node placement in sensor networks using particle swarm optimization[A]. The 5th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS’06)[C]. Brussels, Belgium, 2006.510-511.

[10] LEE K Y, EL-SHARKAWI M A. Modern Heuristic Optimization Techniques[M]. Hoboken, New Jersey∶ John Wiley & Sons, 2008.

[11] KANNAN R, IYENGAR S S. Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2004,22(6)∶ 1141-1150.

[12] LUENBERGER D, YE Y. Linear and Nonlinear Programming[M]. 3rd Ed. New York∶ Springer-Verlag, 2008.

[13] BOYD S, VANDENGERGHE L. Convex Optimization[M]. Cambridge University Press, 2009.

[14] DIJKSTRA E W. A note on two problems in connexion with graphs[J].Numerische Mathematik, 1959, 1∶ 269-271.

[15] GABOW H N, MYERS E W. Finding all spanning trees of directed and undirected graphs[J]. SIAM Journal on Computing, 1978, 7(3)∶280-287.

[16] YANG W Y, CAO W, CHUNG T-S, et al. Applied Numerical Methods using MATLAB[M]. Hokeben, New Jersey∶ John Wiley& Sons, 2005.

[17] SIGNH J. The particle swarm (PSO) toolbox for MATLAB[EB/OL].http∶//psotoolbox.sourceforge.net, 2009.