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

邵開麗，付 輝

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

?

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

邵開麗，付 輝

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

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

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

0 引言

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

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

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

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

1．1 問題描述

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

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

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

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

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

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

1.3.1 多Sink節(jié)點布局目標

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

表1 WSNs多Sink節(jié)點布局目標參數(shù)

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

可以建立的多Sink節(jié)點布局目標函數(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)

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

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

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

(7)

每輪傳感器節(jié)點接收li位數(shù)據(jù)消耗的能量為：

Eri=liEelec

(8)

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

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

(9)

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

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

(10)

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

2.1 化為單目標

(11)

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

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

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

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

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

(3) forg=1∶1∶gmax

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

(10)end if

(11)end for

輸出：最優(yōu)目標Obj3和集合P對應(yīng)的最優(yōu)Sink節(jié)點位置。

3 仿真實驗與分析

3．1 實驗參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

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

Sink節(jié)點數(shù)量布局目標能耗目標(10-6)多目標(10-6)Obj*1節(jié)點位置Obj*1節(jié)點位置Obj*3節(jié)點位置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é)點數(shù)量與目標權(quán)重的關(guān)系

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

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

4 結(jié)論

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

[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é)點傳感器網(wǎng)絡(luò)路由算法． 計算機研究與發(fā)展，2008，45(1): 41-46．

[10] 羅玎玎，趙海，尹震宇，等． WSNs 中基于 PMP 的多 SINK 節(jié)點布局研究與實現(xiàn)． 小型微型計算機系統(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)計劃項目(20120473)

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

TP393

A

1002-1841(2015)09-0106-05

邵開麗(1976—)，講師，碩士，研究方向為物聯(lián)網(wǎng)技術(shù)。 E-mail：sklemail@163．com 付輝(1982—)，講師，碩士，研究方向為計算機應(yīng)用。 E-mail：iefh@163．com