錢建新,施沈科,何 燕,馮佳俊,徐會彬,成新民
(1.湖州市特種設備檢測研究院, 浙江 湖州 313000;2.湖州師范學院 信息工程學院,, 浙江 湖州 313000)
隨著通信、電子技術(shù)的進步,物聯(lián)網(wǎng)應用得到迅速的發(fā)展。而無線傳感網(wǎng)絡(Wireless Sensor Networks,WSNs)[1]是物聯(lián)網(wǎng)的基石。WSNs由多個低功耗、具有感測、通信能力的微型傳感節(jié)點組成。通常傳感節(jié)點是由電池供電。當電池用盡,節(jié)點無法工作[2]。由于節(jié)點常部署于野外或人不便接入的復雜環(huán)境,即使電池用盡,也無法給節(jié)點更換電池或者補充能量。因此,網(wǎng)絡能耗問題成為WSNs的研究熱點之一。
監(jiān)測興趣區(qū)域(Region of Interest,RoI)是部署節(jié)點的主要目的。高效率的監(jiān)測RoI是需要高質(zhì)量覆蓋保證[3]。通常覆蓋分區(qū)覆蓋和目標覆蓋。前者是把監(jiān)測整個部署區(qū)域,而后者是監(jiān)測區(qū)域內(nèi)某個具體一點[4]。而目標覆蓋又可分為Q-覆蓋和簡化覆蓋。在簡化覆蓋中,每個目標至少由一個傳感節(jié)點監(jiān)測。而Q-覆蓋至少由Q個傳感節(jié)點監(jiān)測目標[5]。
除了網(wǎng)絡覆蓋外,維護網(wǎng)絡連通也是部署節(jié)點必須考慮的問題。所謂網(wǎng)絡連通是指每個節(jié)點至少存在一條路徑通往信宿。
網(wǎng)絡能耗、網(wǎng)絡覆蓋和網(wǎng)絡連通都是部署節(jié)點時要考慮的問題。具體而言,部署節(jié)點時應考慮以下4個問題:① 最小化網(wǎng)絡總體能耗;② 最大化覆蓋區(qū)域;③ 延長網(wǎng)絡壽命;④ 維護網(wǎng)絡連通,致使RoI內(nèi)每個節(jié)點能與信宿通信。
換而言之,考慮上述4個問題可理解成優(yōu)化節(jié)點部署的4個目標。因此,優(yōu)節(jié)點部署問題屬多目標優(yōu)化問題。利用多目標優(yōu)化(Multi-objective Optimization,MOO)算法解決多目標優(yōu)化問題是最好的選擇。例如,為了最大化網(wǎng)絡覆蓋區(qū)域,應將傳感節(jié)點部署的位置離信宿越遠越好。然而,離信宿越遠,數(shù)據(jù)傳輸路徑就越長,這加大了能耗。因此,基于MOO算法的節(jié)點部署策略實質(zhì)上就是在兩個矛盾目標間尋找一種平衡[6-7]。
花朵授粉(Flow Pollinate,FP)算法是由英國學者于2012年提出的啟發(fā)式智能算法[8]。FP算利用Levy飛行模式,具有良好的全局搜索能力[9],且可實現(xiàn)全局搜索與局部搜索間的平衡,已在目標函數(shù)優(yōu)化、電子系統(tǒng)優(yōu)化等問題中廣泛應用[10-11]。
為此,將FP算法解決節(jié)點部署的多目標優(yōu)化問題。通過FP算法計算節(jié)點的最優(yōu)位置,進而使網(wǎng)絡能耗、壽命以及覆蓋、連通達到平衡。仿真數(shù)據(jù)表明:相比于同類算法,F(xiàn)PNP算法能夠在滿足96%覆蓋率的條件,能耗最少,網(wǎng)絡壽命最長。
考慮兩維平面l1×l2網(wǎng)絡結(jié)構(gòu)。在該網(wǎng)絡區(qū)域內(nèi)部署N個傳感節(jié)點。令Rs、Rc分別表示節(jié)點的感測半徑和通信半徑。通常,假定Rs>Rc。用G=(V,E)圖表示描述網(wǎng)絡拓撲,其中V為頂點集,其表示傳感節(jié)點{s1,s2,…,si,…,sN}。E為邊集。若對于任意兩個節(jié)點(si,sj),如果它們間的距離di, j小于Rc,則它們存在一邊,即它們能夠直接通信(圖1)。
圖1 傳感節(jié)點感測和通信范圍示意圖
(1)
其中:MEi表示維持節(jié)點正常工作的啟動能耗;TEi為傳輸能耗;Psi表示從節(jié)點至信宿的最短路徑;REi為接收數(shù)據(jù)所消耗的能量;αi表示節(jié)點si將數(shù)據(jù)傳輸至信宿中所參與的節(jié)點數(shù)。
整個網(wǎng)絡所消耗的能量可依式(2)計算,并形成第一個目標函數(shù):
(2)
對于網(wǎng)絡而言,引用兩個指標表述網(wǎng)絡壽命。首先,考慮網(wǎng)絡內(nèi)第一個節(jié)點能量消耗殆盡的時間,如式(3)所示:
LT1=min(ti),i=1,2,…,N
(3)
同時,考慮最后一個節(jié)點能量消耗殆盡的時間,如式(4)所示:
LT2=max(ti),i=1,2,…,N
(4)
將l1×l2網(wǎng)絡區(qū)域劃分離散的m×n個網(wǎng)格。令(xi,yi)表示節(jié)點si的位置坐標。如圖2所示,節(jié)點si的感知區(qū)域就是以(xi,yi)為圓心,半徑為Rc的圓。
圖2 基于網(wǎng)格的感測示意圖
對于網(wǎng)格內(nèi)點p(x,y),它與節(jié)點si間的距離d(si,p):
(5)
令P(ri)表示點p(x,y)被節(jié)點si覆蓋的概率,其定義如式(6)所示:
(6)
假定有多個節(jié)點對點p(x,y)進行了覆蓋,這些節(jié)點構(gòu)成集合C。而點p(x,y)被C覆蓋的概率可表示為:
(7)
其中|C|表示集合C的元素個數(shù)。
集合C內(nèi)的節(jié)點覆蓋的網(wǎng)格點的面積之和:
(8)
將式(8)進行推廣。網(wǎng)絡內(nèi)總共有N個節(jié)點。令Ψ表示這N個節(jié)點所形成的節(jié)點集。集合Ψ所覆蓋的網(wǎng)格點的面積之和:
(9)
最后,建立第2個目標函數(shù):
f2=1-ρc
(10)
最后,建立式(11)所示的目標函數(shù),其中ω1、ω2為權(quán)重系數(shù)。式(11)由兩項組成。第一項是最小能耗,第二項最大化覆蓋率:
(11)
FP算法是基于顯花植物的授粉過程而演化的算法。有兩種方式授粉:自花授粉和異花授粉。前者是指植株成熟的花粉粒傳播到花朵上,而后者是通過自然界動物飛行攜帶花粉粒給花朵授粉。相比于自花授粉,異花授粉的傳播范圍大[9]。
FP算法求解目標函數(shù)的實質(zhì),就是搜索解。對應其兩種授粉方式,搜索解也分為兩種:局部尋優(yōu)搜索和全局尋優(yōu)搜索。且這種搜索方式可進行轉(zhuǎn)換,且轉(zhuǎn)換概率為p。
表1反映了求解目標函數(shù)的過程。先初始化基本參數(shù),包括迭代參數(shù)MaxT、種群個體數(shù)Nf和轉(zhuǎn)換概率p。
表1 FP算法的偽代碼
然后,再對種群內(nèi)每個個體位置進行隨機初始化,并計算其對應的適應度值。再獲取最優(yōu)的全局解g*。
第3步,檢測是否滿足條件rand≥p′檢測是否滿足搜索模式的轉(zhuǎn)換條件。若滿足,進行全局搜索,并依據(jù)式(12)進行處理:
Fi(t+1)=Fi(t)+L(g*-Fi(t))
(12)
其中Fi(t+1)、Fi(t)分別表示第t+1、t次迭代的第i解。而g*為全局解。L是服從Levy分布的隨機步長。
若不滿足,就進行局部搜索,并依式(13)處理:
Fi(t+1)=Fi(t)+ε(Fk(t)-Fj(t))
(13)
其中:ε表示在[0,1]區(qū)間內(nèi)的隨機數(shù);Fk(t)和Fj(t)表示不同于Fi(t)的兩個位置。
再判斷Fi(t+1) 最后,判斷是否滿足迭代終止條件。終止迭代后,就輸出最優(yōu)解。最優(yōu)解就是部署節(jié)點的最優(yōu)位置。 利用NS 2.34軟件建立仿真平臺,并分析FPNP算法的性能。在60 m×60 m區(qū)域內(nèi)部署N個節(jié)點。并將60 m×60 m區(qū)域劃分為邊長為1 m的網(wǎng)格。具體的仿真參數(shù)值如表2所示。 表2 仿真參數(shù) 此外,選擇同類的PSO算法[1]和NSG-Ⅱ算法[13]作為參照,并對比分析FPNP算法性能,包括能耗及網(wǎng)絡壽命。 首先,分析在實現(xiàn)網(wǎng)絡覆蓋率ρ=0.96時,3個算法所消耗的能量,簡稱能耗如圖3所示。 從圖3可知:相比于PSO和NSGA-Ⅱ算法,提出的FPNP算法的能耗最低,即在實現(xiàn)同樣的覆蓋率的同時,所消耗的網(wǎng)絡能量最低。而PSO算法的能耗最高,原因在于:PSO算法在運行時,具有兩個復雜的約束條件,并限制了種群個體數(shù)的分布。而FPNP算法將降低能耗作為目標函數(shù)的第一項(如式(11)),其旨在降低能耗。 接下來,分析網(wǎng)絡壽命,圖4、圖5分別顯示了第一個節(jié)點能量消耗殆盡的時間、最后一個節(jié)點能量消耗殆盡的時間,定義分別如式(3)、式(4)所示。 圖3 能耗曲線 圖4 第一個節(jié)點能量消耗殆盡的時間曲線 圖5 最后一個節(jié)點能量消耗殆盡的時間 從圖4可知:FPNP算法有效地延長了第一個節(jié)點能量消耗殆盡的時間,而PSO算法最早出現(xiàn)能量消耗殆盡的節(jié)點。而NSGA-Ⅱ算法與FPNP算法的性能相近,F(xiàn)PNP算法的性能略優(yōu)于NSGA-Ⅱ算法,第1個節(jié)點能量消耗殆盡的時間延長了平均約6 h。 圖5顯示了最后一個節(jié)點能量消耗殆盡的時間,與圖4類似。結(jié)合圖4、圖5可知,F(xiàn)PNP算法的有效地降低網(wǎng)絡能耗。相比于PSO算法、NSGA-Ⅱ算法,F(xiàn)PNP算法通過優(yōu)先部署節(jié)點,在維持相同的覆蓋率,降低了網(wǎng)絡能耗,延長網(wǎng)絡壽命。 針對無線傳感網(wǎng)絡的節(jié)點部署問題,提出基于花朵授粉算法的節(jié)點部署FPNP。FPNP算法先將節(jié)點部署問題轉(zhuǎn)換成多目標優(yōu)化問題,再利用花朵授粉算法搜索部署節(jié)點的最優(yōu)位置。通過部署最優(yōu)位置,降低能耗,延長網(wǎng)絡壽命。仿真結(jié)果表明:提出的FPNP算法降低了網(wǎng)絡能耗,延長了網(wǎng)絡壽命。3 性能仿真
3.1 仿真參數(shù)
3.2 數(shù)據(jù)分析
4 結(jié)論