邵開(kāi)麗，付 輝

(黃河科技學(xué)院，河南鄭州 450063)

?

能耗均衡的無(wú)線傳感器網(wǎng)絡(luò)多Sink節(jié)點(diǎn)部署優(yōu)化方法

邵開(kāi)麗，付 輝

(黃河科技學(xué)院，河南鄭州 450063)

針對(duì)傳感器網(wǎng)絡(luò)中單Sink節(jié)點(diǎn)存在近距離傳感器節(jié)點(diǎn)過(guò)早死亡、傳輸路徑單一、傳輸延遲及節(jié)點(diǎn)失效等問(wèn)題，提出了一種綜合考慮網(wǎng)絡(luò)布局和網(wǎng)絡(luò)能耗的多Sink節(jié)點(diǎn)部署優(yōu)化新方法。首先，為縮短Sink節(jié)點(diǎn)到傳感器節(jié)點(diǎn)的傳輸距離，建立了加權(quán)距離最小化模型；同時(shí)，為均衡網(wǎng)絡(luò)能耗，建立了無(wú)線傳感器網(wǎng)絡(luò)能耗最小化模型。然后，根據(jù)所建立多Sink節(jié)點(diǎn)部署優(yōu)化模型的特點(diǎn)，使用加權(quán)系數(shù)將多目標(biāo)模型單目標(biāo)化，并設(shè)計(jì)了上升啟發(fā)式算法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，提出的多Sink節(jié)點(diǎn)部署優(yōu)化方法既能保證網(wǎng)絡(luò)布局最優(yōu)，又進(jìn)一步均衡了網(wǎng)絡(luò)能量消耗，有助于延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期。

無(wú)線傳感器網(wǎng)絡(luò)；多Sink節(jié)點(diǎn)；布局優(yōu)化；多目標(biāo)模型

0 引言

隨著微電子機(jī)械系統(tǒng)(Micro-Electro-Mechanical System，MEMS)的發(fā)展，低成本、低能耗、多功能的無(wú)線傳感器及其網(wǎng)絡(luò)得到廣泛應(yīng)用[1]，涉及軍事傳感、交通監(jiān)控、視頻監(jiān)控、工業(yè)和制造業(yè)自動(dòng)化等領(lǐng)域[2-3]。無(wú)線傳感器網(wǎng)絡(luò)(Wireless sensor networks，WSNs)由大量體積微小的節(jié)點(diǎn)設(shè)備組成，該節(jié)點(diǎn)設(shè)備集成一個(gè)或多個(gè)傳感器、數(shù)據(jù)處理單元、短距離無(wú)線通信模塊和供電電源，可實(shí)現(xiàn)信息采集、存儲(chǔ)、計(jì)算、通信等功能[4]。然而，WSNs節(jié)點(diǎn)受固定電源的限制，其能量和計(jì)算資源嚴(yán)重受限。因此，如何高效利用網(wǎng)絡(luò)電源，最大限度延長(zhǎng)網(wǎng)絡(luò)生命周期，成為WSNs研究的關(guān)鍵及熱點(diǎn)。近年來(lái)，很多專(zhuān)家和學(xué)者致力于網(wǎng)絡(luò)中的節(jié)點(diǎn)設(shè)備、網(wǎng)絡(luò)協(xié)議、節(jié)點(diǎn)布局、數(shù)據(jù)處理、電池等進(jìn)行深入研究，在方法和技術(shù)上取得了一定成果。本文擬以WSNs中多Sink節(jié)點(diǎn)的布局為研究對(duì)象，旨在通過(guò)優(yōu)化節(jié)點(diǎn)布局有效提高網(wǎng)絡(luò)生命周期。

Sink節(jié)點(diǎn)也稱匯聚節(jié)點(diǎn)或網(wǎng)關(guān)節(jié)點(diǎn)，連接WSNs與外網(wǎng)并實(shí)現(xiàn)通信。目前，國(guó)內(nèi)外學(xué)者針對(duì)多Sink節(jié)點(diǎn)的布局問(wèn)題，研究其對(duì)網(wǎng)絡(luò)壽命的影響已有部分成果。文獻(xiàn)[5-6]運(yùn)用線性規(guī)劃模型研究多Sink節(jié)點(diǎn)部署的最佳位置，并確定了WSNs中的最優(yōu)路由信息流量路徑，能有效提高網(wǎng)絡(luò)的壽命和保證能量的均衡性。文獻(xiàn)[7]提出一種基于基因表達(dá)式編程(Gene Expression Programming，GEP)的多sink節(jié)點(diǎn)部署策略和一種GEP-MSN算法，達(dá)到了延長(zhǎng)網(wǎng)絡(luò)生存周期和降低響應(yīng)時(shí)間的目的。文獻(xiàn)[8]采用最短路徑和矩陣位置方法部署最佳多Sink節(jié)點(diǎn)，實(shí)驗(yàn)結(jié)果顯示這種基于約束的部署算法與KSP 和KDP算法相比，更能充分發(fā)揮WSNs的潛能。文獻(xiàn)[9]提出一種基于能量水平的多Sink節(jié)點(diǎn)傳感器網(wǎng)絡(luò)路由算法，與最小能量消耗路由算法相比，更能有效延長(zhǎng)WSNs的壽命。

針對(duì)WSNs中單Sink節(jié)點(diǎn)存在近距離傳感器節(jié)點(diǎn)過(guò)早死亡、傳輸路徑單一、傳輸延遲及節(jié)點(diǎn)失效等問(wèn)題，本文主要研究多Sink的部署策略，提出一種綜合考慮網(wǎng)絡(luò)布局和網(wǎng)絡(luò)能耗的多Sink節(jié)點(diǎn)部署優(yōu)化新方法。該方法通過(guò)建立多Sink節(jié)點(diǎn)布局優(yōu)化多目標(biāo)模型，同時(shí)實(shí)現(xiàn)兩個(gè)優(yōu)化目標(biāo)：一是實(shí)現(xiàn)各傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的總加權(quán)距離最小化，二是實(shí)現(xiàn)WSNs網(wǎng)絡(luò)能耗最小化。根據(jù)所建立模型的特點(diǎn)，本文首先使用加權(quán)系數(shù)將多目標(biāo)模型單目標(biāo)化，并結(jié)合設(shè)計(jì)的上升啟發(fā)式算法進(jìn)行求解，得到多Sink節(jié)點(diǎn)最優(yōu)仿真部署方案，最后在仿真實(shí)驗(yàn)中分析和驗(yàn)證了多Sink節(jié)點(diǎn)布局優(yōu)化模型和上升啟發(fā)式算法的有效性。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)只考慮距離的節(jié)點(diǎn)部署策略相比，本文提出的多Sink節(jié)點(diǎn)部署優(yōu)化方法綜合考慮了距離和網(wǎng)絡(luò)能耗兩個(gè)目標(biāo)，既能保證網(wǎng)絡(luò)布局最優(yōu)，又進(jìn)一步均衡了網(wǎng)絡(luò)能量消耗，有助于延長(zhǎng)WSNs生命周期。

1 多Sink節(jié)點(diǎn)布局模型

1．1 問(wèn)題描述

無(wú)線傳感器網(wǎng)絡(luò)中，能耗、時(shí)延和可靠性是度量QOS的重要指標(biāo)。基此，研究多Sink節(jié)點(diǎn)的布局及優(yōu)化問(wèn)題，有利于減少傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的距離，即有效縮短了信息傳輸時(shí)延；而且，多Sink節(jié)點(diǎn)傳感器網(wǎng)絡(luò)拓展了傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的信息通信路徑，有利于均衡網(wǎng)絡(luò)能耗和保證信息可靠性。因此，本文在對(duì)多Sink節(jié)點(diǎn)布局時(shí)，采用經(jīng)典選址模型P-中位問(wèn)題(p-median problems)對(duì)多Sink節(jié)點(diǎn)布局進(jìn)行優(yōu)化，使傳感器節(jié)點(diǎn)到所有Sink節(jié)點(diǎn)的加權(quán)距離最?。煌瑫r(shí)，為了使整個(gè)網(wǎng)絡(luò)能量消耗最少，建立了網(wǎng)絡(luò)能量最小化模型，以最大化延長(zhǎng)網(wǎng)絡(luò)生命周期。

1．2 網(wǎng)絡(luò)結(jié)構(gòu)模型

無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)模型采用如圖1所示的網(wǎng)絡(luò)結(jié)構(gòu)。其中，傳感器節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域，將采集的監(jiān)測(cè)信息無(wú)線傳輸?shù)讲季肿顑?yōu)的Sink節(jié)點(diǎn)，對(duì)信息進(jìn)行處理后通過(guò)Internet/GPRS/3G等網(wǎng)絡(luò)上傳至監(jiān)控中心。與傳感器節(jié)點(diǎn)相比，Sink節(jié)點(diǎn)連接外網(wǎng)的前置機(jī)或數(shù)據(jù)服務(wù)器，具有持續(xù)電源和更強(qiáng)的數(shù)據(jù)處理能力。

圖1 無(wú)線傳感器網(wǎng)絡(luò)多Sink節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)

1．3 布局優(yōu)化模型

文獻(xiàn)[10]中采用PMP模型對(duì)WSNs中的多Sink節(jié)點(diǎn)進(jìn)行部署，仿真結(jié)果表明，該方法與隨機(jī)布局方案相比進(jìn)一步降低了網(wǎng)絡(luò)能量消耗，有效延長(zhǎng)了網(wǎng)絡(luò)壽命。然而，WSNs更關(guān)注能量?jī)?yōu)先，不能僅考慮傳統(tǒng)選址中注重的路徑最優(yōu)。因此，研究多Sink節(jié)點(diǎn)布局優(yōu)化時(shí)，應(yīng)該把節(jié)點(diǎn)能量消耗及網(wǎng)絡(luò)能量均衡使用放在第一位。本文研究WSNs多Sink節(jié)點(diǎn)的部署時(shí)，同時(shí)兼顧了路徑最優(yōu)和網(wǎng)絡(luò)能量消耗最少兩項(xiàng)指標(biāo)，并基于此建立了相應(yīng)的最小化目標(biāo)函數(shù)，提出一種有效的多Sink節(jié)點(diǎn)布局優(yōu)化模型及方法。

1.3.1 多Sink節(jié)點(diǎn)布局目標(biāo)

假設(shè)可以用S={se1,se2,L,seN}(|S|=N)和R={si1,si2,L,siP}(|R|=P)表示網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)集合和Sink節(jié)點(diǎn)集合，V=S∪R，用E表示網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的通信邊，則監(jiān)測(cè)區(qū)域布設(shè)的WSNs可以用有向圖G(V,E)來(lái)表示。若網(wǎng)絡(luò)中Sink節(jié)點(diǎn)候選位置集合為Q={L1,L2,L,LM}(|Q|=M)，為了使Sink節(jié)點(diǎn)到各傳感器節(jié)點(diǎn)的總加權(quán)距離最小，將WSNs多Sink節(jié)點(diǎn)布局目標(biāo)Obj1表示為目標(biāo)函數(shù)式(1)。目標(biāo)函數(shù)中的參數(shù)定義詳見(jiàn)表1。

表1 WSNs多Sink節(jié)點(diǎn)布局目標(biāo)參數(shù)

定義的決策變量Xj和Yij描述如下：

可以建立的多Sink節(jié)點(diǎn)布局目標(biāo)函數(shù)Obj1的數(shù)學(xué)模型表示為：

(1)

(2)

(3)

Yij-Xj≤0 ?i∈S，j∈Q

(4)

Yij=0，1 ?i∈S，j∈Q

(5)

Xj=0,1 ?j∈Q

(6)

目標(biāo)函數(shù)式(1)是多Sink節(jié)點(diǎn)布局目標(biāo)函數(shù)Obj1的數(shù)學(xué)模型，使各傳感器節(jié)點(diǎn)到Sink節(jié)點(diǎn)的總加權(quán)距離最小化；約束式(2)是保證每個(gè)傳感器節(jié)點(diǎn)只能將發(fā)送的請(qǐng)求數(shù)上傳到最近的一個(gè)Sink節(jié)點(diǎn)；約束式(3)是保證網(wǎng)絡(luò)中的Sink節(jié)點(diǎn)數(shù)量為預(yù)置的 個(gè)；約束式(4)是保證傳感器節(jié)點(diǎn)只能被建立的Sink節(jié)點(diǎn)服務(wù)；約束式(5)和(6)是目標(biāo)函數(shù)中所有決策變量的0-1約束。

1.3.2 網(wǎng)絡(luò)能耗目標(biāo)

在WSNs中，傳感器節(jié)點(diǎn)負(fù)責(zé)把采集的數(shù)據(jù)經(jīng)過(guò)一跳或多跳上傳到Sink節(jié)點(diǎn)，并通過(guò)外網(wǎng)(Internet/GPRS/3G等)上傳至監(jiān)控中心。由于多Sink節(jié)點(diǎn)適用于大規(guī)模、高可靠性的網(wǎng)絡(luò)，網(wǎng)絡(luò)傳感器節(jié)點(diǎn)密度及距離都較大，因此采用分層的多跳分簇路由協(xié)議，簇頭兼具中繼和數(shù)據(jù)融合的作用，Sink節(jié)點(diǎn)融合轉(zhuǎn)發(fā)簇頭或最近傳感器節(jié)點(diǎn)數(shù)據(jù)至上層網(wǎng)絡(luò)。假設(shè)每個(gè)傳感器節(jié)點(diǎn)在固定的時(shí)間內(nèi)發(fā)送li(i=1,2,L,N)位數(shù)據(jù)，則每輪傳感器節(jié)點(diǎn)傳輸數(shù)據(jù)消耗的能量為：

(7)

每輪傳感器節(jié)點(diǎn)接收l(shuí)i位數(shù)據(jù)消耗的能量為：

Eri=liEelec

(8)

式中：N為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)量；Eelec為接收或發(fā)送單位數(shù)據(jù)的無(wú)線電路損耗能量；d0和d分別為距離門(mén)限和各傳感器到簇頭或Sink節(jié)點(diǎn)間距離；eft與emp為自由空間功率放大系數(shù)和多徑衰落功率放大系數(shù)[11]。

假設(shè)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)個(gè)數(shù)為K，m為簇內(nèi)傳感器節(jié)點(diǎn)數(shù)目，則每輪簇頭消耗的能量包括接收簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)時(shí)消耗能量，數(shù)據(jù)融合時(shí)消耗能量，以及發(fā)送融合后數(shù)據(jù)所消耗能量的總和，即：

(9)

式中：Eda為簇頭融合單位數(shù)據(jù)時(shí)消耗能量；ε為簇頭融合后的總數(shù)據(jù)量傳輸?shù)絊ink節(jié)點(diǎn)所消耗的eftd2或empd4能量。

故為使多Sink節(jié)點(diǎn)傳感網(wǎng)能耗最小化，建立的多Sink節(jié)點(diǎn)網(wǎng)絡(luò)能耗目標(biāo)Obj2的數(shù)學(xué)模型為：

(10)

2 多Sink節(jié)點(diǎn)部署優(yōu)化方法實(shí)現(xiàn)

2.1 化為單目標(biāo)

(11)

2.2 部署優(yōu)化方法的實(shí)現(xiàn)

在對(duì)WSNs的多Sink節(jié)點(diǎn)布局優(yōu)化模型實(shí)現(xiàn)過(guò)程中，采用上升啟發(fā)式算法[12]對(duì)式(1)、式(9)和式(10)的最優(yōu)目標(biāo)值進(jìn)行求解，求解過(guò)程描述如下。

輸入：初始化所有參數(shù)。

(1)設(shè)置Sink節(jié)點(diǎn)數(shù)量P值，目標(biāo)權(quán)重系數(shù)w值；

(2)求解P個(gè)Sink節(jié)點(diǎn)的初始目標(biāo)值，并將P個(gè)節(jié)點(diǎn)位置設(shè)置為初始最優(yōu)方案。即從候選M個(gè)Sink節(jié)點(diǎn)位置中隨機(jī)選取P個(gè)節(jié)點(diǎn)位置，計(jì)算集合P的目標(biāo)值Obj3，初始最優(yōu)方案設(shè)置為OL1×P={L1,L2,L,Lt},t∈P，并設(shè)置迭代次數(shù)最大值gmax值；

(3) forg=1∶1∶gmax

(4)從候選 個(gè)Sink節(jié)點(diǎn)位置中隨機(jī)選取節(jié)點(diǎn)位置i和j(i∈P,j?P)，將i和j交換，組成新的集合P′；

(10)end if

(11)end for

輸出：最優(yōu)目標(biāo)Obj3和集合P對(duì)應(yīng)的最優(yōu)Sink節(jié)點(diǎn)位置。

3 仿真實(shí)驗(yàn)與分析

3．1 實(shí)驗(yàn)參數(shù)設(shè)置

3．2 布局計(jì)算結(jié)果

圖2 WSNs多Sink節(jié)點(diǎn)最優(yōu)布局

圖3 Sink節(jié)點(diǎn)布局尋優(yōu)過(guò)程中解的變化

3．3 Sink節(jié)點(diǎn)數(shù)量與最優(yōu)布局的關(guān)系

在實(shí)際應(yīng)用場(chǎng)景中，Sink節(jié)點(diǎn)數(shù)量可根據(jù)網(wǎng)絡(luò)規(guī)模、數(shù)據(jù)精度及傳輸時(shí)延等要求做出適當(dāng)調(diào)整，因此，本文分析了當(dāng)Sink節(jié)點(diǎn)數(shù)量P從1到10變化時(shí)對(duì)最優(yōu)布局的影響，且預(yù)置Sink節(jié)點(diǎn)數(shù)量 發(fā)生變化時(shí)，最優(yōu)布置方案也會(huì)發(fā)生變化。實(shí)驗(yàn)結(jié)果表明，當(dāng) 從1到10增加時(shí)，網(wǎng)絡(luò)最小加權(quán)距離逐步減小，如圖4所示。這種現(xiàn)象與文獻(xiàn)[10]中所得到的結(jié)果相吻合。在此基礎(chǔ)上，本文從WSNs網(wǎng)絡(luò)生命周期考慮，進(jìn)一步分析了多Sink節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)能耗值的關(guān)系，如圖5所示。

圖4 Sink節(jié)點(diǎn)數(shù)量與最小加權(quán)距離的關(guān)系

圖5 Sink節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)能耗的關(guān)系

在圖5中，隨著Sink節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)能耗值整體上呈現(xiàn)出逐步減少的趨勢(shì)，但個(gè)別P值對(duì)應(yīng)的能耗值有所增加，呈現(xiàn)出與最小加權(quán)距離不同步的結(jié)果。產(chǎn)生這種現(xiàn)象的原因是：由于本文中WSNs的路由協(xié)議采用Leach協(xié)議，該協(xié)議是一種帶有族頭選舉的分層、多跳路由協(xié)議，其簇頭的選舉是變化的，會(huì)導(dǎo)致個(gè)別P值對(duì)應(yīng)的多Sink節(jié)點(diǎn)的網(wǎng)絡(luò)能耗會(huì)出現(xiàn)一定偏差。這種不同步的結(jié)果說(shuō)明，在考慮WSNs多Sink節(jié)點(diǎn)布局優(yōu)化時(shí)，除了要考慮加權(quán)距離最小化外，還必須考慮Sink節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)能耗值的關(guān)系。

圖6綜合了最小加權(quán)距離與網(wǎng)絡(luò)能耗，描述了P從1到10變化時(shí)Sink節(jié)點(diǎn)數(shù)量與多目標(biāo)最優(yōu)值的關(guān)系。表2詳細(xì)列出了多Sink節(jié)點(diǎn)數(shù)量的最優(yōu)布局方案。從該表中數(shù)據(jù)可以看出，僅考慮單目標(biāo)(最小加權(quán)距離或最小網(wǎng)絡(luò)能耗)的多Sink節(jié)點(diǎn)布局方案，與同時(shí)考慮兩個(gè)目標(biāo)的優(yōu)化方案存在一定的差異性。多目標(biāo)的布局方案兼具了加權(quán)距離和網(wǎng)絡(luò)能量消耗，要優(yōu)于單目標(biāo)的布局方案，更適用于WSNs實(shí)際應(yīng)用場(chǎng)景。

圖6 Sink節(jié)點(diǎn)數(shù)量與多目標(biāo)最優(yōu)值的關(guān)系

Sink節(jié)點(diǎn)數(shù)量布局目標(biāo)能耗目標(biāo)(10-6)多目標(biāo)(10-6)Obj*1節(jié)點(diǎn)位置Obj*1節(jié)點(diǎn)位置Obj*3節(jié)點(diǎn)位置117821(10.9,10.0)1502(3.7,3.4)78742(11.5,8.3)212920(14.1,17.1),(9.3,7.6)1407(13.9,6.0),(18.3,10.7)49898(11.3,14.1),(5.8,2.9)39952(4.1,4.5),(12.9,7.8),(14.2,17.5)1228(11.6,9.8),(0.4,11.3),(16.8,16.5)66667(2.3.16,9.8),(10.9,9.0),(16.8,16.5)47572(15.3,17.5),(4.7,3.3),(2.6,16.6),(13.0,8.2)1285(8.1,10.3),(7.4,5.5),(9.0,4.3),(3.7,3.4)96109(15.8,11.9),(7.9,5.9),(2.5,16.5),(16.7,16.5)56456(14.8,17.4),(2.1,17.1),(14.2,7.1),(5.2,4.0)(9.8,9.5)1049(7.6,10.2),(17.2,1.1),(2.7,18.3),(3.7,3.4),(16.8,16.5)153121(16.0,19.7),(0.9,16.8),(12.0,8.9),(3.7,3.4),(16.7,16.5)65816(2.1,17.8),(15.6,10.5),(4.7,3.3),(14.2,6.3),(9.8,9.5),(15.2,17.2)1163(5.8,2.9),(17.2,1.1),(3.1,7.2),(13.7,8.1),(3.7,3.4),(10.3,4.6)98364(2.6,15.4),(7.8,1.4),(15.0,16.1),(13.7,8.1),(3.7,3.4),(10.3,4.6)75327(15.4,10.6),(19.1,18.8),(10.3,10.8),(14.2,18.0),(13.6,6.2),(5.2,3.5),(2.3,16.9)1045(2.3,15.0),(6.5,19.3),(17.0,2.4),(18.1,9.8),(13.4,12.3),(3.7,3.4),(2.8,5.0)94790(14.0,9.7),(16.0,19.7),(17.0,2.4),(9.8,9.5),(0.9,13.5),(3.7,3.4),(2.9,16.6)84723(13.7,17.4),(5.3,3.1),(10.9,9.4),(14.8,10.4),(1.3,1.7),(13.5,5.4),(2.2,18.0),(19.0,18.8)1181(6.3,8.1),(5.1,5.0),(18.4,0.9),(18.1,9.7),(0.2,6.2),(5.5,0.7),(2.7,5.0),(7.8,10.9)78026(13.6,17.9),(5.1,5.0),(11.513.3),(18.0,17.6),(16.6,10.7),(13.0,4.2),(2.9,16.6),(7.8,10.9)94552(19.3,19.4),(8.3,8.9),(7.1,17.5),(1.0,1.8),(15.0,17.0),(13.6,6.1),(0.9,17.5),(15.0,10.0),(4.4,4.0)1083(6.3,8.1),(5.1,4.9),(9.9,4.2),(7.4,4.6),(17.2,6.6),(4.6,17.1),(2.8,16.5),(15.0,11.7),(12.0,3.3)186616(14.1,3.5),(5.2,5.0),(11.5,13.3),(18.1,9.8),(12.8,16.6),(19.5,15.3),(2.9,16.5),(10.5,7.9),(12.0,3.4)103750(1.6,16.0),(9.7,9.4),(7.1,17.5),(14.0,7.0),(13.2,0.8),(13.5,17.9),(18.9,17.5),(1.3,1.7),(15.4,10.8),(4.4,4.0)1017(14.1,3.5),(8.2,10.7),(6.5,19.3),(19.9,15.4),(19.6,6.2),(14.0,7.2),(2.8,16.5),(10.5,7.7),(15.0,11.7),(14.6,15.1)327556(6.3,8.1),(10.9,9.0),(6.5,19.3),(18.4,19.9),(17.2,6.6),(5.5,0.7),(2.9,16.5),(10.5,7.8),(15.0,11.7),(14.6,15.1)

3．4 Sink節(jié)點(diǎn)數(shù)量與目標(biāo)權(quán)重的關(guān)系

表3描述了目標(biāo)權(quán)重系數(shù)變化對(duì)多Sink節(jié)點(diǎn)布局的影響。其中，Sink節(jié)點(diǎn)數(shù)量P=2，權(quán)重系數(shù)w值從0．1～0．9。從表中可以看出，權(quán)重系數(shù)w變化時(shí)，Sink節(jié)點(diǎn)多目標(biāo)最優(yōu)方案也相應(yīng)變化。當(dāng)w增加時(shí)，最小加權(quán)距離在總目標(biāo)中的比重增加；相反，則網(wǎng)絡(luò)能耗目標(biāo)的比重增加。實(shí)際應(yīng)用時(shí)，可根據(jù)WSNs的應(yīng)用場(chǎng)景適當(dāng)調(diào)整目標(biāo)權(quán)重系數(shù)，得到更滿意的多Sink節(jié)點(diǎn)部署方案，從而擴(kuò)大本論文所提出部署方法的適用范圍。

表3 W值變化對(duì)多Sink節(jié)點(diǎn)布局的影響

4 結(jié)論

本文通過(guò)分析WSNs的特點(diǎn)及單Sink節(jié)點(diǎn)傳感器網(wǎng)絡(luò)存在的問(wèn)題，研究WSNs多Sink節(jié)點(diǎn)最佳部署策略，提出了一種能耗均衡的多Sink節(jié)點(diǎn)部署優(yōu)化方法。與傳統(tǒng)多Sink節(jié)點(diǎn)布局不同，本文建立的布局優(yōu)化模型綜合考慮了距離和網(wǎng)絡(luò)能耗兩個(gè)指標(biāo)，并結(jié)合上升啟發(fā)式算法實(shí)現(xiàn)了多sink節(jié)點(diǎn)的仿真布局。實(shí)驗(yàn)數(shù)據(jù)分析和結(jié)果表明，本文提出的多Sink節(jié)點(diǎn)部署模型及其部署優(yōu)化方法，與只考慮單目標(biāo)(最小加權(quán)距離或最小網(wǎng)絡(luò)能耗)的多Sink節(jié)點(diǎn)布局方案相比，部署方案存在一定的差異性，為WSNs多Sink節(jié)點(diǎn)部署策略提供了一種參考方案。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al． Wireless sensor networks: a survey． Computer Networks, 2002, 38(4): 393-422．

[2] CHONG C Y, KUMAR S P． Sensor networks: evolution, opportunities, and challenges． Proceedings of the IEEE, 2003, 91(8): 1247-1256．

[3] YOUNIS M, AKKAYA K． Strategies and techniques for node placement in wireless sensor networks: A survey． Ad Hoc Networks, 2008, 6(4): 621-655．

[4] SLIJEPCEVIC S, POTKONJAK M． Power efficient organization of wireless sensor networks． Communications, 2001． ICC 2001． IEEE International Conference on． IEEE, Helsinki, 2001．

[5] KIM H, SEOK Y, CHOI N, et al． Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks． Berlin: Springer Berlin Heidelberg, 2005: 264-274．

[6] HAEYONG K, TAEKYOUNG K, PYEONGSOO M． Multiple sink positioning and routing to maximize the lifetime of sensor networks． IEICE transactions on communications, 2008, 91(11): 3499-3506．

[7] DAI S, TANG C, QIAO S, et al． Optimal multiple sink nodes deployment in wireless sensor networks based on gene expression programming． 2010 ICCSN’10 Second International Conference on IEEE, Chengdu, 2010．

[8] FLATHAGEN J, KURE Q, ENGELSTAD P E． Constrained-based multiple sink placement for wireless sensor networks． 2011 IEEE 8th International Conference on IEEE, Valencia, 2011．

[9] 吳中博，樊小泊，陳紅． 基于能量水平的多Sink節(jié)點(diǎn)傳感器網(wǎng)絡(luò)路由算法． 計(jì)算機(jī)研究與發(fā)展，2008，45(1): 41-46．

[10] 羅玎玎，趙海，尹震宇，等． WSNs 中基于 PMP 的多 SINK 節(jié)點(diǎn)布局研究與實(shí)現(xiàn)． 小型微型計(jì)算機(jī)系統(tǒng)，2007，28(6): 979-982．

[11] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H． Energy-efficient communication protocol for wireless microsensor networks． Proceedings of the 33rd annual Hawaii international conference on． IEEE, Hawaii, 2000．

[12] TEITZ M B, BART P． Heuristic methods for estimating the generalized vertex median of a weighted graph． Operations research, 1968, 16(5): 955-961．

Novel Optimal Deployment Method of Multiple Sink Nodes in WSNs for Balanced Energy Consumption

SHAO Kai-li, FU Hui

(College of HUANGHE Science & Technology，Zhengzhou 450063，China)

Wireless sensor network (WSNs) with a single sink node has some disadvantages of the quickness of consuming energy on the critical path, the singleness of routing algorithm, and the invalidation of the sink node. To solve these problems, a novel multi-objective programming approach for multiple sink nodes in WSNs was developed in this paper. In our approach, multiple sink nodes were not only deployed，but energy consumption was also considered as the uncertain parameters. Our multi-objective model attempted to minimize the weighted distance from sensor nodes to sink nodes, at the same time to balance WSNs energy consumption through minimizing the objective of consuming energy. Considering the global evaluation of two objectives, a compromise programming model was formulated and solved to obtain a non-dominating compromise solution with ascent algorithm. Experiment results show that the proposed approach can keep both optimal deployment of multi-sink nodes and balance of energy consumption in WSNs, which can prolong the lifetime of the network.

WSNs;multiple sink nodes; optimal deployment; multi-objective model

鄭州市科技攻關(guān)計(jì)劃項(xiàng)目(20120473)

2015-05-30 收修改稿日期：2015-07-27

TP393

A

1002-1841(2015)09-0106-05

邵開(kāi)麗(1976—)，講師，碩士，研究方向?yàn)槲锫?lián)網(wǎng)技術(shù)。 E-mail：sklemail@163．com 付輝(1982—)，講師，碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用。 E-mail：iefh@163．com