楊 斌，郝楊楊，李軍軍

(上海海事大學(xué)物流研究中心，上海 201306)

1 引言

物聯(lián)網(wǎng)的理想是“物物相連”。然而，“物物相連”要付出以下代價(jià)：節(jié)點(diǎn)軟硬件投資、網(wǎng)絡(luò)通信、節(jié)點(diǎn)能耗、維護(hù)與管理。因此，如何采用集約的方式設(shè)計(jì)和部署物聯(lián)網(wǎng)節(jié)點(diǎn)，并采用合理的物聯(lián)網(wǎng)運(yùn)作模式，是物聯(lián)網(wǎng)推廣應(yīng)用的一個(gè)重要決策問(wèn)題。

目前，國(guó)內(nèi)外對(duì)于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)布局問(wèn)題的研究也很多。文獻(xiàn)[1]提出了一種無(wú)線傳感器網(wǎng)絡(luò)中多sink節(jié)點(diǎn)的P中值布局模型。文獻(xiàn)[2]研究了對(duì)于一個(gè)給定的探測(cè)區(qū)域，至少需要多少節(jié)點(diǎn)才能實(shí)現(xiàn)對(duì)該區(qū)域的完全無(wú)縫覆蓋的問(wèn)題。文獻(xiàn)[3]提出一種基于粒子群算法的無(wú)線傳感器布局優(yōu)化方案，但是僅討論了基于節(jié)點(diǎn)位置調(diào)整的動(dòng)態(tài)布局優(yōu)化。文獻(xiàn)[4]提出了一種基于遺傳算法的異構(gòu)節(jié)點(diǎn)成本優(yōu)化部署方法。文獻(xiàn)[5,6]利用改進(jìn)的NSGA-Ⅱ解決多目標(biāo)節(jié)點(diǎn)部署優(yōu)化問(wèn)題。文獻(xiàn)[7]提出一種結(jié)合了Hopfield網(wǎng)絡(luò)與遺傳算法的動(dòng)態(tài)節(jié)點(diǎn)選擇優(yōu)化策略。文獻(xiàn)[8]提出了一種基于新量子遺傳算法的分布優(yōu)化機(jī)制。除了遺傳算法之外，文獻(xiàn)[9]采用模擬退火法解決了基于網(wǎng)格的傳感器節(jié)點(diǎn)布局問(wèn)題。文獻(xiàn)[10]采用了加權(quán)平均的方法，提出了一種基于魚(yú)群算法的布局優(yōu)化策略。

目前無(wú)線傳感器的網(wǎng)絡(luò)節(jié)點(diǎn)布局問(wèn)題的研究?jī)H限于對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的總成本、總覆蓋率、總能耗的單目標(biāo)分析，而將幾個(gè)目標(biāo)綜合考慮的布局方案的決策問(wèn)題少有研究。同時(shí)，以往的文獻(xiàn)沒(méi)有考慮每個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)的監(jiān)測(cè)任務(wù)的均衡性，會(huì)出現(xiàn)某些節(jié)點(diǎn)任務(wù)過(guò)重而某些節(jié)點(diǎn)任務(wù)過(guò)少的現(xiàn)象。本文的研究將改善以上幾方面不足，在物聯(lián)網(wǎng)應(yīng)用于監(jiān)測(cè)系統(tǒng)的背景下，提出了物聯(lián)網(wǎng)在監(jiān)測(cè)區(qū)域的節(jié)點(diǎn)選擇與布局方案，通過(guò)非線性多目標(biāo)優(yōu)化模型和遺傳算法解決節(jié)點(diǎn)數(shù)量決策問(wèn)題與部署問(wèn)題。

2 問(wèn)題定義與分析

監(jiān)測(cè)系統(tǒng)中物聯(lián)網(wǎng)節(jié)點(diǎn)布局問(wèn)題的關(guān)鍵是對(duì)監(jiān)測(cè)區(qū)域的采樣。監(jiān)測(cè)區(qū)域可以看成是由具有不同監(jiān)測(cè)重要性的監(jiān)測(cè)點(diǎn)構(gòu)成的二維平面集合。物聯(lián)網(wǎng)節(jié)點(diǎn)布局即是選擇一定數(shù)量的點(diǎn)，包括確定監(jiān)測(cè)點(diǎn)的數(shù)量和每個(gè)監(jiān)測(cè)點(diǎn)的位置。物聯(lián)網(wǎng)節(jié)點(diǎn)設(shè)備安裝在選擇的這些監(jiān)測(cè)點(diǎn)上。物聯(lián)網(wǎng)數(shù)據(jù)采集的概念視圖如圖1所示：(1)監(jiān)測(cè)區(qū)域由分布的監(jiān)測(cè)點(diǎn)構(gòu)成，每個(gè)監(jiān)測(cè)點(diǎn)具有一定的重要性；(2)每個(gè)監(jiān)測(cè)點(diǎn)上配置同質(zhì)設(shè)備，即物聯(lián)網(wǎng)設(shè)備的投資、維護(hù)和管理具有相同的成本；(3)節(jié)點(diǎn)設(shè)備的數(shù)據(jù)采集量和通信量都是確定的，相互之間沒(méi)有差異；(4)物聯(lián)網(wǎng)節(jié)點(diǎn)與數(shù)據(jù)中心的通信成本與節(jié)點(diǎn)的分布沒(méi)有直接關(guān)系。

Figure 1 Data acquisition conceptual view of IoT圖1 物聯(lián)網(wǎng)數(shù)據(jù)采集概念視圖

因此，該問(wèn)題可以抽象為在網(wǎng)絡(luò)中的一次性采樣問(wèn)題，使得樣本具有最好的代表性，同時(shí)樣本所代表的物聯(lián)網(wǎng)節(jié)點(diǎn)的代價(jià)之間達(dá)到均衡。該問(wèn)題的關(guān)鍵點(diǎn)包括以下幾點(diǎn)：(1)物聯(lián)網(wǎng)節(jié)點(diǎn)集合對(duì)監(jiān)測(cè)點(diǎn)集合的覆蓋性的評(píng)價(jià)指標(biāo)設(shè)計(jì)；(2)物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)量決策問(wèn)題與節(jié)點(diǎn)部署問(wèn)題的定義與分析；(3)節(jié)點(diǎn)數(shù)量與節(jié)點(diǎn)定位的兩階段問(wèn)題的建模與求解策略。

本文綜合考慮物聯(lián)網(wǎng)規(guī)模、成本、綜合代表性和均衡度四個(gè)目標(biāo)，圖2給出了監(jiān)測(cè)應(yīng)用中監(jiān)測(cè)點(diǎn)管理和物聯(lián)網(wǎng)部署方案決策的概念圖。

Figure 2 Monitoring point management and deployment of IoT圖2 監(jiān)測(cè)點(diǎn)管理與物聯(lián)網(wǎng)部署方案

3 模型

3.1 符號(hào)說(shuō)明

Table 1 Symbol description表1 符號(hào)說(shuō)明

在上述符號(hào)定義中，D、S、SI、R、Mi、C是參數(shù)，而節(jié)點(diǎn)數(shù)量N和節(jié)點(diǎn)的集合SI(S)是最終需要確定的。

3.2 假設(shè)條件

(1)監(jiān)測(cè)點(diǎn)之間的地理關(guān)系采用兩點(diǎn)之間的歐氏距離表示；

(2)在任何監(jiān)測(cè)點(diǎn)安裝物聯(lián)網(wǎng)節(jié)點(diǎn)的成本完全相同；

(3)物聯(lián)網(wǎng)節(jié)點(diǎn)的維護(hù)和管理成本，以及單位時(shí)間的數(shù)據(jù)傳輸量都完全相同；

(4)物聯(lián)網(wǎng)節(jié)點(diǎn)上傳數(shù)據(jù)的傳輸代價(jià)僅與傳送量相關(guān)，與相對(duì)于服務(wù)器的距離無(wú)關(guān)；

(5)監(jiān)測(cè)點(diǎn)的重要性采用0～1之間的數(shù)表示，越大則相關(guān)性越大；

(6)事件與物聯(lián)網(wǎng)節(jié)點(diǎn)之間的關(guān)系，通過(guò)物聯(lián)網(wǎng)節(jié)點(diǎn)集合表示，本文僅考慮與全部節(jié)點(diǎn)相關(guān)的情況；

(7)物聯(lián)網(wǎng)節(jié)點(diǎn)本身具有較明確的感應(yīng)范圍，即感應(yīng)半徑。

3.3 抽樣評(píng)價(jià)

(1)物聯(lián)網(wǎng)節(jié)點(diǎn)的規(guī)模。

物聯(lián)網(wǎng)節(jié)點(diǎn)規(guī)模是物聯(lián)網(wǎng)節(jié)點(diǎn)構(gòu)成的集合的大小。式(1)表示物聯(lián)網(wǎng)節(jié)點(diǎn)集合。式(2)表示物聯(lián)網(wǎng)節(jié)點(diǎn)的規(guī)模是節(jié)點(diǎn)集合大小，也可以直接由標(biāo)識(shí)變量xi表示。

S(IoT)={i∈I|xi=1}

(1)

N(IoT)=|S(IoT)|=∑i∈Ixi

(2)

(2)物聯(lián)網(wǎng)的代價(jià)。

由于物聯(lián)網(wǎng)節(jié)點(diǎn)配置設(shè)備、維護(hù)和管理的代價(jià)一致，物聯(lián)網(wǎng)的代價(jià)與其規(guī)模成正比，如式(3)所示。

C(IoT)=C·N(IoT)

(3)

(3)物聯(lián)網(wǎng)節(jié)點(diǎn)代表性的均衡度。

首先，通過(guò)式(4)定義物聯(lián)網(wǎng)節(jié)點(diǎn)a∈S對(duì)監(jiān)測(cè)點(diǎn)i∈I的代表性。對(duì)于與s∈S具有相同距離的不同監(jiān)測(cè)點(diǎn)，重要性越大的，代表性越??；對(duì)于具有同樣重要性的監(jiān)測(cè)點(diǎn)，與s∈S距離越大的，代表性越小。

顯然，對(duì)任意監(jiān)測(cè)點(diǎn)，根據(jù)式(4)可以確定各個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)對(duì)它的代表性。在本文中，簡(jiǎn)單地取代表性最大的物聯(lián)網(wǎng)點(diǎn)作為該監(jiān)測(cè)點(diǎn)的監(jiān)測(cè)設(shè)備，如式(5)所示。

相反，對(duì)于任意物聯(lián)網(wǎng)節(jié)點(diǎn)，能夠確定由該節(jié)點(diǎn)代表的監(jiān)測(cè)點(diǎn)集合，如式(6)所示。

在以上定義的基礎(chǔ)上，采用式(7)作為物聯(lián)網(wǎng)節(jié)點(diǎn)s∈S的綜合代表性。

對(duì)整個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)集合，代表性的最小值通過(guò)式(8)計(jì)算，而代表性的均衡度則采用方差，如式(9)所示。

(4)

IS(i)=argmins∈S(P(s,i))∈S

(5)

SI(s)={i∈I|IS(i)=s}?I

(6)

P(s)=∑i∈IP(s,i)

(7)

M(IoT)=∑s∈SP(s)

(8)

(9)

3.4 優(yōu)化模型

較好的采樣及物聯(lián)網(wǎng)節(jié)點(diǎn)配置方案，應(yīng)當(dāng)均衡物聯(lián)網(wǎng)節(jié)點(diǎn)規(guī)模、成本和代表性，即規(guī)模和成本的最小化；綜合代表性的最大化；代表性均衡度的最大化，即各個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)代表性均衡性標(biāo)準(zhǔn)差的最小化。

MinimizeN(IoT)

(10)

MinimizeC(IoT)

(11)

MaximizeM(IoT)

(12)

MinimizeB(IoT)

(13)

將以上目標(biāo)都轉(zhuǎn)化為最小化目標(biāo)，得到式(14)所示的模型。

Minimizef=(zN,zC,zM,zB)

(14)

minzN=∑i∈Iqi

minzC=∑i∈I(Ci·qi)

minzM=1/(1+∑s∈S,i∈IP(s,i))

minzB=

s.t.

P(s,i)=(1-Mi)/(1+Ds i)

(15)

P(s1,i)·hs1,i>P(s2,i)·hs2,i,

?s1,s2∈SI,i∈I

(16)

∑s∈Shs i=1,?i∈I

(17)

hs iDs i≤R

(18)

qi∈{0,1},hs i∈{0,1}

(19)

式(15)表示s對(duì)i的代表性，式(16)表示取代表性最大的物聯(lián)網(wǎng)節(jié)點(diǎn)監(jiān)測(cè)該點(diǎn)，式(17)表示每個(gè)點(diǎn)都要被監(jiān)測(cè)到，式(18)是對(duì)物聯(lián)網(wǎng)節(jié)點(diǎn)監(jiān)測(cè)半徑的約束，式(19)是指決策變量為0-1變量。

以上是在考慮單目標(biāo)的情況下所建立的模型。在考慮多目標(biāo)的情況下，要綜合考慮到各目標(biāo)函數(shù)間的差異，因此不能將單目標(biāo)簡(jiǎn)單相加，因此本文采用了線性加權(quán)的方法量化不同目標(biāo)之間的差異。設(shè)參數(shù)λk(k∈K={1,2,3,4})分別表示為各目標(biāo)zN、zC、zM、zB的權(quán)重，從而在以上單目標(biāo)模型基礎(chǔ)上，得出一個(gè)混合整數(shù)非線性多目標(biāo)規(guī)劃模型。

MaximizeF=λ1·ZN+λ2·ZC+

λ3·ZM+λ4·ZB

(20)

s.t.

∑k∈Kλk=1

(21)

(22)

(23)

(24)

其中，式(20)是對(duì)各目標(biāo)進(jìn)行線性加權(quán)后的目標(biāo)函數(shù)，式(21)表示各權(quán)重之和應(yīng)該為1。式(22)～式(24)表示對(duì)各目標(biāo)的歸一化。

4 算法

4.1 遺傳算法求解

第3節(jié)建立的模型是一個(gè)整數(shù)非線性多目標(biāo)優(yōu)化模型，下文采用遺傳算法進(jìn)行求解。

(1)對(duì)決策變量進(jìn)行編碼操作。編碼模式反映了問(wèn)題的可能解與遺傳染色體的對(duì)應(yīng)關(guān)系。根據(jù)De Jong提出的兩條操作性較強(qiáng)的實(shí)用編碼原則，本文采用決策變量x構(gòu)成的一維數(shù)組為編碼對(duì)象，采用二進(jìn)制編碼方法，如式(25)所示。式中，問(wèn)題的可能解由xi表示，xi取值為1的點(diǎn)則設(shè)置物聯(lián)網(wǎng)節(jié)點(diǎn)，否則xi=0。初始群體中每個(gè)染色體是隨機(jī)產(chǎn)生的，即在每個(gè)染色體中隨機(jī)選擇部分基因位放置物聯(lián)網(wǎng)節(jié)點(diǎn)，另外一部分不放置。

X=[x1x2…xNI],xi∈{0,1}

(25)

(2)根據(jù)目標(biāo)函數(shù)確定適值函數(shù)，如式(26)所示，直接采用F的值作為適值函數(shù)。

Fit(xi)=F=λ1·ZN+

λ2·ZC+λ3·ZM+λ4·ZB

(26)

pi=Fi/∑k=1,…,NIFk

(27)

(4)交叉與變異。對(duì)染色體的繁殖采用均勻交叉與均勻變異的方法。

(5)算法的終止條件。采用設(shè)定最大代數(shù)(NG)的方法作為算法停止的準(zhǔn)則。

4.2 代表性矩陣生成算法

輸入：I：監(jiān)測(cè)點(diǎn)集合;

pxi,i∈I：監(jiān)測(cè)點(diǎn)i的橫坐標(biāo);

pyi,i∈I：監(jiān)測(cè)點(diǎn)i的縱坐標(biāo);

Mi：監(jiān)測(cè)點(diǎn)i的重要性;

λk：多目標(biāo)最優(yōu)中每個(gè)單目標(biāo)所占的權(quán)值比重。

輸出：Pa,b：任意監(jiān)測(cè)點(diǎn)a和b之間的代表性矩陣

?i∈I,qi=1：物聯(lián)網(wǎng)節(jié)點(diǎn)集合;

?i∈I,hsi=1,s∈S：由物聯(lián)網(wǎng)節(jié)點(diǎn)s代表的監(jiān)測(cè)點(diǎn)集合;

zN，zC，zM，zB：?jiǎn)文繕?biāo)最優(yōu)值;

F：?jiǎn)文繕?biāo)基礎(chǔ)上，給定權(quán)重的多目標(biāo)最優(yōu)值。

步驟1準(zhǔn)備Da,b:將矩陣元素的默認(rèn)值設(shè)為無(wú)窮大，對(duì)角線元素設(shè)置為0：

?a,b,Da，b=G：其中G是一個(gè)足夠大的數(shù)字，如9999;

?a,Da,a=0。

步驟2初始化Da,b:

?a,b:Da,b=Db,a=

步驟3計(jì)算任意兩點(diǎn)之間a對(duì)b的代表性矩陣:

?a,b∈I,Pa,b=(1-Mb)/(1+Da,b)

步驟4對(duì)于任意監(jiān)測(cè)點(diǎn)i∈I，選擇代表性最大的節(jié)點(diǎn)s對(duì)i進(jìn)行監(jiān)測(cè):

IS(i)=argmins∈S(P(s,i))∈S

步驟5計(jì)算出物聯(lián)網(wǎng)節(jié)點(diǎn)集合:

S(IoT)={i∈I|qi=1}

計(jì)算出物聯(lián)網(wǎng)節(jié)點(diǎn)的監(jiān)測(cè)點(diǎn)集合:

SI(s)={i∈I|IS(i)=s}?I

計(jì)算出單目標(biāo)最優(yōu)值z(mì)N，zC，zM，zB。

對(duì)λk進(jìn)行賦值，計(jì)算F的值。

5 仿真驗(yàn)證

為驗(yàn)證本文模型，隨機(jī)產(chǎn)生一個(gè)監(jiān)測(cè)點(diǎn)集合，監(jiān)測(cè)點(diǎn)數(shù)NI=100，每個(gè)監(jiān)測(cè)點(diǎn)的橫縱坐標(biāo)都是在[0,100]內(nèi)隨機(jī)生成，則各監(jiān)測(cè)點(diǎn)之間的距離可由它們的坐標(biāo)求得。各監(jiān)測(cè)點(diǎn)的重要性在(0,1]隨機(jī)產(chǎn)生，感應(yīng)半徑R=15，物聯(lián)網(wǎng)節(jié)點(diǎn)的成本C=5。各監(jiān)測(cè)點(diǎn)位置如圖3所示，*表示監(jiān)測(cè)點(diǎn)。由第4節(jié)可知，該問(wèn)題要求確定決策變量x，因此本文以標(biāo)識(shí)變量xi構(gòu)成的二進(jìn)制一維數(shù)組[x1,x2,…,xNI]作為總決策變量。由3.3節(jié)的式(3)可知，物聯(lián)網(wǎng)的代價(jià)與其規(guī)模成正比。由于模型中已有物聯(lián)網(wǎng)規(guī)模最小化目標(biāo)zN，則物聯(lián)網(wǎng)代價(jià)最小化目標(biāo)zC可由zN描述，因此這里僅以zN、zM、zB為目標(biāo)進(jìn)行分析。

Figure 3 Monitor nodes location圖3 各監(jiān)測(cè)點(diǎn)位置

5.1 單目標(biāo)分析

(1)物聯(lián)網(wǎng)規(guī)模及成本。

if ?i，?xi=0，即不設(shè)置任何物聯(lián)網(wǎng)節(jié)點(diǎn)時(shí)，物聯(lián)網(wǎng)規(guī)模及成本最小，此時(shí)，minzN=0,minzC=0。if ?i,?xi=1，即在所有監(jiān)測(cè)點(diǎn)設(shè)置物聯(lián)網(wǎng)節(jié)點(diǎn)時(shí)，物聯(lián)網(wǎng)規(guī)模及成本最大，本例中maxzN=100，maxzC=500，即zN的范圍為[0,100]。

(2)物聯(lián)網(wǎng)的總代表性。

if ?i,?xi=1，即在所有監(jiān)測(cè)點(diǎn)設(shè)置物聯(lián)網(wǎng)節(jié)點(diǎn)時(shí)，物聯(lián)網(wǎng)的總代表性最大。在本例中，maxM(IoT)=81.8068，minzM=0.0121。if ?i,?xi=0，即不設(shè)置任何物聯(lián)網(wǎng)節(jié)點(diǎn)時(shí)，物聯(lián)網(wǎng)的總代表性最小，此時(shí)minM(IoT)=0，maxzM=1。則本例中zM的范圍為[0.012 1,1]。

(3)物聯(lián)網(wǎng)節(jié)點(diǎn)代表性的均衡度。

僅設(shè)置一個(gè)任意物聯(lián)網(wǎng)節(jié)點(diǎn)，或設(shè)置若干個(gè)等代表性的物聯(lián)網(wǎng)節(jié)點(diǎn)，此時(shí)各個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)代表性均衡性標(biāo)準(zhǔn)差最小，minzB=0，物聯(lián)網(wǎng)代表性均衡度達(dá)到最大。若物聯(lián)網(wǎng)僅有兩個(gè)節(jié)點(diǎn)，且設(shè)置在maxi∈IP(i)、mini∈IP(i)對(duì)應(yīng)的監(jiān)測(cè)點(diǎn)，此時(shí)各個(gè)物聯(lián)網(wǎng)節(jié)點(diǎn)代表性均衡性標(biāo)準(zhǔn)差最大，物聯(lián)網(wǎng)代表性均衡度達(dá)到最小。本例中，maxzB=0.7438，則zB的范圍為[0,0.743 8]。

5.2 目標(biāo)函數(shù)的相關(guān)度分析

5.1節(jié)分別以zN(zC)、zM、zB為單目標(biāo)求解，求解結(jié)果對(duì)應(yīng)X向量分別用YN、YM、YB表示?？梢訷N、YM、YB的相關(guān)度來(lái)衡量三個(gè)目標(biāo)函數(shù)之間的相關(guān)度。由5.1節(jié)可知，YN、YM完全是兩個(gè)極端，即zN(zC)與zM完全不相關(guān)。zB的大小由物聯(lián)網(wǎng)節(jié)點(diǎn)代表性差異程度決定，而受物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)影響程度不是很明顯；而zN(zC)完全由物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)決定，zM受物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)影響很大。因此，zB與zN(zC)的相關(guān)度、zB與zM的相關(guān)度情況不明朗。

5.3 線性加權(quán)法求解

綜合考慮zN、zM、zB三個(gè)目標(biāo)函數(shù)，以線性加權(quán)法求解，并轉(zhuǎn)化為最大化目標(biāo)，如式(28)所示。其中λ1、λ2、λ3的大小決定各目標(biāo)函數(shù)的權(quán)重。由于第一項(xiàng)實(shí)際涵蓋了物聯(lián)網(wǎng)規(guī)模及成本兩個(gè)目標(biāo)，因此這一項(xiàng)上再增加一個(gè)系數(shù)2。這幾個(gè)權(quán)重系數(shù)滿足2λ1+λ2+λ3=1。

(28)

采取7種不同的組合，如表2所示。第一種組合表示對(duì)4個(gè)目標(biāo)函數(shù)均等重視，第2～4組分別表示單獨(dú)重視物聯(lián)網(wǎng)規(guī)模及成本、物聯(lián)網(wǎng)的總代表性、物聯(lián)網(wǎng)節(jié)點(diǎn)代表性的均衡度，第5～7組分別表示重視zN、zM、zB三個(gè)目標(biāo)函數(shù)中的兩個(gè)。

Table 2 Optimize results in different weights表2 不同權(quán)重下優(yōu)化結(jié)果

由表2可知，ZN、ZM、ZB受權(quán)重影響很明顯，比如zN(zC)權(quán)重最大的第2種權(quán)重組合中，物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)明顯較少；zN(zC)權(quán)重最小的第3、4、6種權(quán)重組合中，物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)明顯較多。為量化描述各目標(biāo)對(duì)權(quán)重的敏感程度，通過(guò)式(29)計(jì)算SN，衡量式(29)中zN(zC)的權(quán)重敏感度。其中λ1,i、λ1,j分別為表1中第i、j種組合中的λ1值，ZNi、ZNj分別為表1中第i、j種組合中的ZN值。以此類推，可獲得zM、zB的權(quán)重敏感度SM、SB。zN(zC)、zM、zB這三個(gè)目標(biāo)函數(shù)對(duì)權(quán)重的敏感度分別是：SN=8.8500，SM=1.3448，SB=2.4981?？梢?jiàn)，zN(zC)對(duì)權(quán)重最為敏感，zB次之，zM敏感程度最低。

(29)

各監(jiān)測(cè)點(diǎn)位置如圖3所示。這7種同權(quán)重組合下的物聯(lián)網(wǎng)節(jié)點(diǎn)布局如圖4～圖10所示，其中,○表示未設(shè)置物聯(lián)網(wǎng)節(jié)點(diǎn)的監(jiān)測(cè)點(diǎn)，*表示設(shè)置物聯(lián)網(wǎng)節(jié)點(diǎn)的監(jiān)測(cè)點(diǎn)，虛線圓圈表示各節(jié)點(diǎn)監(jiān)測(cè)的感應(yīng)范圍。

Figure 4 Weight combination 1圖4 權(quán)重組合1

Figure 5 Weight combination 2圖5 權(quán)重組合2

Figure 6 Weight combination 3圖6 權(quán)重組合3

Figure 7 Weight combination 4圖7 權(quán)重組合4

Figure 8 Weight combination 5圖8 權(quán)重組合5

Figure 9 Weight combination 6圖9 權(quán)重組合6

Figure 10 Weight combination 7圖10 權(quán)重組合7

6 結(jié)束語(yǔ)

本文提出了一個(gè)面向監(jiān)測(cè)應(yīng)用的物聯(lián)網(wǎng)節(jié)點(diǎn)布局問(wèn)題，主要側(cè)重于確定物聯(lián)網(wǎng)節(jié)點(diǎn)數(shù)量與布局方法。將問(wèn)題抽象為帶有網(wǎng)絡(luò)拓?fù)潢P(guān)系的數(shù)據(jù)集上的抽樣問(wèn)題，建立了節(jié)點(diǎn)相對(duì)于監(jiān)測(cè)點(diǎn)的代表性的評(píng)價(jià)指標(biāo)模型和節(jié)點(diǎn)之間代表性的均衡度評(píng)價(jià)模型，并在此基礎(chǔ)上建立了物聯(lián)網(wǎng)節(jié)點(diǎn)選擇決策模型。通過(guò)一個(gè)隨機(jī)仿真案例，分別對(duì)單目標(biāo)與多目標(biāo)優(yōu)化問(wèn)題進(jìn)行了分析。結(jié)果顯示，在對(duì)物聯(lián)網(wǎng)節(jié)點(diǎn)的規(guī)模、成本、總代表性和均衡度給予不同的重視情況下，會(huì)產(chǎn)生不同的布局方案。并且，通過(guò)權(quán)重敏感度分析，可以發(fā)現(xiàn)物聯(lián)網(wǎng)規(guī)模對(duì)權(quán)重較為敏感，對(duì)物聯(lián)網(wǎng)節(jié)點(diǎn)的數(shù)量影響較大。

在此基礎(chǔ)上，考慮對(duì)于異構(gòu)網(wǎng)絡(luò)節(jié)點(diǎn)的布局、物聯(lián)網(wǎng)節(jié)點(diǎn)能耗、節(jié)點(diǎn)之間的連通性與容錯(cuò)性等問(wèn)題的研究是本文需要進(jìn)一步探索的課題。

[1] Xu Jiu-qiang, Bai Da-zhi, Luo Ding-ding, et al. The application of genetic algorithm to deployment of multiple sink nodes in WSNs[J]. Journal of Northeastern University(Natural Science), 2008,29(6):815-818.(in Chinese)

[2] Wang Xue-qing,Yang Yong-tian,Sun Ting,et al.Research on the grid-based coverage problem in wireless sensor networks[J]. Computer Science, 2006,33(11):38-40.(in Chinese)

[3] Lin Zhu-liang,Feng Yuan-jing.Optimization strategy of wireless sensor networks coverage based on oarticle swarm algorithm [J]. Computer Simulation, 2009, 26(4):190-193.

[4] Li Ming, Shi Wei-ren. Optimal sensor deployment scheme based on simulated annealing approach in heterogeneous wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2010,23(6):55-58.(in Chinese)

[5] Jia Jie, Chen Jian, Chang Gui-ran, et al. Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm[J]. Computers and Mathematics with Applications, 2009, 57(11-12):1756-1766.

[6] Jia Jie, Chen Jian, Chang Gui-ran, et al. Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius[J]. Computers and Mathematics with Applications, 2009,57(11-12):1767-1775.

[7] Wang Sheng, Wang Xue, Bi Dao-wei. Dynamic sensor selection optimization strategy for wireless sensor networks[J]. Journal of Computer Research and Development. 2008,45(1):188-195.(in Chinese)

[8] Fu Hua,Han Shuang.Optimal sensor node distribution based on the new quantum genetic algorithm[J]. Chinese Journal of Sensors and Actuators, 2008,21(7):1259-1263.(in Chinese)

[9] Lin F Y S, Chiu P L. A near-optimal sensor placement algorithm to achieve complete coverage/discrimination in sensor networks [J]. IEEE Communications Letters, 2005, 9(1):43-45.

[10] Zhou Li-min,Yang Ke-hua, Zhou Pan. Optimal coverage configuration based on artificial fish swarm algorithm in WSNs[J]. Application Research of Computers, 2010,27(6):2776-2779.(in Chinese)

附中文參考文獻(xiàn):

[1] 徐久強(qiáng), 柏大治, 羅玎玎, 等. 遺傳算法在WSNs多Sink節(jié)點(diǎn)布局中的應(yīng)用[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008,29(6):815-818.

[2] 汪學(xué)清, 楊永田, 孫亭, 等. 無(wú)線傳感器網(wǎng)絡(luò)中基于網(wǎng)格的覆蓋問(wèn)題研究[J]. 計(jì)算機(jī)科學(xué), 2006,33(11):38-40.

[4] 李明, 石為人. 異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中基于模擬退火算法的成本最優(yōu)部署機(jī)制[J]. 傳感技術(shù)學(xué)報(bào), 2010,23(6):55-58.

[7] 王晟,王雪,畢道偉. 無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)選擇優(yōu)化策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2008,45(1):188-195.

[8] 付華, 韓爽. 基于新量子遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)感知節(jié)點(diǎn)的分布優(yōu)化[J]. 傳感技術(shù)學(xué)報(bào), 2008,21(7):1259-1263.

[10] 周利民, 楊科華, 周攀. 基于魚(yú)群算法的無(wú)線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(6):2776-2779.