面向監測應用的物聯網節點布局方法研究

楊 斌，郝楊楊，李軍軍

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

1 引言

物聯網的理想是“物物相連”。然而，“物物相連”要付出以下代價：節點軟硬件投資、網絡通信、節點能耗、維護與管理。因此，如何采用集約的方式設計和部署物聯網節點，并采用合理的物聯網運作模式，是物聯網推廣應用的一個重要決策問題。

目前，國內外對于無線傳感器網絡節點布局問題的研究也很多。文獻[1]提出了一種無線傳感器網絡中多sink節點的P中值布局模型。文獻[2]研究了對于一個給定的探測區域，至少需要多少節點才能實現對該區域的完全無縫覆蓋的問題。文獻[3]提出一種基于粒子群算法的無線傳感器布局優化方案，但是僅討論了基于節點位置調整的動態布局優化。文獻[4]提出了一種基于遺傳算法的異構節點成本優化部署方法。文獻[5,6]利用改進的NSGA-Ⅱ解決多目標節點部署優化問題。文獻[7]提出一種結合了Hopfield網絡與遺傳算法的動態節點選擇優化策略。文獻[8]提出了一種基于新量子遺傳算法的分布優化機制。除了遺傳算法之外，文獻[9]采用模擬退火法解決了基于網格的傳感器節點布局問題。文獻[10]采用了加權平均的方法，提出了一種基于魚群算法的布局優化策略。

目前無線傳感器的網絡節點布局問題的研究僅限于對網絡節點的總成本、總覆蓋率、總能耗的單目標分析，而將幾個目標綜合考慮的布局方案的決策問題少有研究。同時，以往的文獻沒有考慮每個物聯網節點的監測任務的均衡性，會出現某些節點任務過重而某些節點任務過少的現象。本文的研究將改善以上幾方面不足，在物聯網應用于監測系統的背景下，提出了物聯網在監測區域的節點選擇與布局方案，通過非線性多目標優化模型和遺傳算法解決節點數量決策問題與部署問題。

2 問題定義與分析

監測系統中物聯網節點布局問題的關鍵是對監測區域的采樣。監測區域可以看成是由具有不同監測重要性的監測點構成的二維平面集合。物聯網節點布局即是選擇一定數量的點，包括確定監測點的數量和每個監測點的位置。物聯網節點設備安裝在選擇的這些監測點上。物聯網數據采集的概念視圖如圖1所示：(1)監測區域由分布的監測點構成，每個監測點具有一定的重要性；(2)每個監測點上配置同質設備，即物聯網設備的投資、維護和管理具有相同的成本；(3)節點設備的數據采集量和通信量都是確定的，相互之間沒有差異；(4)物聯網節點與數據中心的通信成本與節點的分布沒有直接關系。

Figure 1 Data acquisition conceptual view of IoT圖1 物聯網數據采集概念視圖

因此，該問題可以抽象為在網絡中的一次性采樣問題，使得樣本具有最好的代表性，同時樣本所代表的物聯網節點的代價之間達到均衡。該問題的關鍵點包括以下幾點：(1)物聯網節點集合對監測點集合的覆蓋性的評價指標設計；(2)物聯網節點數量決策問題與節點部署問題的定義與分析；(3)節點數量與節點定位的兩階段問題的建模與求解策略。

本文綜合考慮物聯網規模、成本、綜合代表性和均衡度四個目標，圖2給出了監測應用中監測點管理和物聯網部署方案決策的概念圖。

Figure 2 Monitoring point management and deployment of IoT圖2 監測點管理與物聯網部署方案

3 模型

3.1 符號說明

Table 1 Symbol description表1 符號說明

在上述符號定義中，D、S、SI、R、Mi、C是參數，而節點數量N和節點的集合SI(S)是最終需要確定的。

3.2 假設條件

(1)監測點之間的地理關系采用兩點之間的歐氏距離表示；

(2)在任何監測點安裝物聯網節點的成本完全相同；

(3)物聯網節點的維護和管理成本，以及單位時間的數據傳輸量都完全相同；

(4)物聯網節點上傳數據的傳輸代價僅與傳送量相關，與相對于服務器的距離無關；

(5)監測點的重要性采用0～1之間的數表示，越大則相關性越大；

(6)事件與物聯網節點之間的關系，通過物聯網節點集合表示，本文僅考慮與全部節點相關的情況；

(7)物聯網節點本身具有較明確的感應范圍，即感應半徑。

3.3 抽樣評價

(1)物聯網節點的規模。

物聯網節點規模是物聯網節點構成的集合的大小。式(1)表示物聯網節點集合。式(2)表示物聯網節點的規模是節點集合大小，也可以直接由標識變量xi表示。

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

(1)

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

(2)

(2)物聯網的代價。

由于物聯網節點配置設備、維護和管理的代價一致，物聯網的代價與其規模成正比，如式(3)所示。

C(IoT)=C·N(IoT)

(3)

(3)物聯網節點代表性的均衡度。

首先，通過式(4)定義物聯網節點a∈S對監測點i∈I的代表性。對于與s∈S具有相同距離的不同監測點，重要性越大的，代表性越小；對于具有同樣重要性的監測點，與s∈S距離越大的，代表性越小。

顯然，對任意監測點，根據式(4)可以確定各個物聯網節點對它的代表性。在本文中，簡單地取代表性最大的物聯網點作為該監測點的監測設備，如式(5)所示。

相反，對于任意物聯網節點，能夠確定由該節點代表的監測點集合，如式(6)所示。

在以上定義的基礎上，采用式(7)作為物聯網節點s∈S的綜合代表性。

對整個物聯網節點集合，代表性的最小值通過式(8)計算，而代表性的均衡度則采用方差，如式(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 優化模型

較好的采樣及物聯網節點配置方案，應當均衡物聯網節點規模、成本和代表性，即規模和成本的最小化；綜合代表性的最大化；代表性均衡度的最大化，即各個物聯網節點代表性均衡性標準差的最小化。

MinimizeN(IoT)

(10)

MinimizeC(IoT)

(11)

MaximizeM(IoT)

(12)

MinimizeB(IoT)

(13)

將以上目標都轉化為最小化目標，得到式(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對i的代表性，式(16)表示取代表性最大的物聯網節點監測該點，式(17)表示每個點都要被監測到，式(18)是對物聯網節點監測半徑的約束，式(19)是指決策變量為0-1變量。

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

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

λ3·ZM+λ4·ZB

(20)

s.t.

∑k∈Kλk=1

(21)

(22)

(23)

(24)

其中，式(20)是對各目標進行線性加權后的目標函數，式(21)表示各權重之和應該為1。式(22)～式(24)表示對各目標的歸一化。

4 算法

4.1 遺傳算法求解

第3節建立的模型是一個整數非線性多目標優化模型，下文采用遺傳算法進行求解。

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

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

(25)

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

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

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

(26)

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

(27)

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

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

4.2 代表性矩陣生成算法

輸入：I：監測點集合;

pxi,i∈I：監測點i的橫坐標;

pyi,i∈I：監測點i的縱坐標;

Mi：監測點i的重要性;

λk：多目標最優中每個單目標所占的權值比重。

輸出：Pa,b：任意監測點a和b之間的代表性矩陣

?i∈I,qi=1：物聯網節點集合;

?i∈I,hsi=1,s∈S：由物聯網節點s代表的監測點集合;

zN，zC，zM，zB：單目標最優值;

F：單目標基礎上，給定權重的多目標最優值。

步驟1準備Da,b:將矩陣元素的默認值設為無窮大，對角線元素設置為0：

?a,b,Da，b=G：其中G是一個足夠大的數字，如9999;

?a,Da,a=0。

步驟2初始化Da,b:

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

步驟3計算任意兩點之間a對b的代表性矩陣:

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

步驟4對于任意監測點i∈I，選擇代表性最大的節點s對i進行監測:

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

步驟5計算出物聯網節點集合:

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

計算出物聯網節點的監測點集合:

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

計算出單目標最優值zN，zC，zM，zB。

對λk進行賦值，計算F的值。

5 仿真驗證

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

Figure 3 Monitor nodes location圖3 各監測點位置

5.1 單目標分析

(1)物聯網規模及成本。

if ?i，?xi=0，即不設置任何物聯網節點時，物聯網規模及成本最小，此時，minzN=0,minzC=0。if ?i,?xi=1，即在所有監測點設置物聯網節點時，物聯網規模及成本最大，本例中maxzN=100，maxzC=500，即zN的范圍為[0,100]。

(2)物聯網的總代表性。

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

(3)物聯網節點代表性的均衡度。

僅設置一個任意物聯網節點，或設置若干個等代表性的物聯網節點，此時各個物聯網節點代表性均衡性標準差最小，minzB=0，物聯網代表性均衡度達到最大。若物聯網僅有兩個節點，且設置在maxi∈IP(i)、mini∈IP(i)對應的監測點，此時各個物聯網節點代表性均衡性標準差最大，物聯網代表性均衡度達到最小。本例中，maxzB=0.7438，則zB的范圍為[0,0.743 8]。

5.2 目標函數的相關度分析

5.1節分別以zN(zC)、zM、zB為單目標求解，求解結果對應X向量分別用YN、YM、YB表示。可以YN、YM、YB的相關度來衡量三個目標函數之間的相關度。由5.1節可知，YN、YM完全是兩個極端，即zN(zC)與zM完全不相關。zB的大小由物聯網節點代表性差異程度決定，而受物聯網節點數影響程度不是很明顯；而zN(zC)完全由物聯網節點數決定，zM受物聯網節點數影響很大。因此，zB與zN(zC)的相關度、zB與zM的相關度情況不明朗。

5.3 線性加權法求解

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

(28)

采取7種不同的組合，如表2所示。第一種組合表示對4個目標函數均等重視，第2～4組分別表示單獨重視物聯網規模及成本、物聯網的總代表性、物聯網節點代表性的均衡度，第5～7組分別表示重視zN、zM、zB三個目標函數中的兩個。

Table 2 Optimize results in different weights表2 不同權重下優化結果

由表2可知，ZN、ZM、ZB受權重影響很明顯，比如zN(zC)權重最大的第2種權重組合中，物聯網節點數明顯較少；zN(zC)權重最小的第3、4、6種權重組合中，物聯網節點數明顯較多。為量化描述各目標對權重的敏感程度，通過式(29)計算SN，衡量式(29)中zN(zC)的權重敏感度。其中λ1,i、λ1,j分別為表1中第i、j種組合中的λ1值，ZNi、ZNj分別為表1中第i、j種組合中的ZN值。以此類推，可獲得zM、zB的權重敏感度SM、SB。zN(zC)、zM、zB這三個目標函數對權重的敏感度分別是：SN=8.8500，SM=1.3448，SB=2.4981。可見，zN(zC)對權重最為敏感，zB次之，zM敏感程度最低。

(29)

各監測點位置如圖3所示。這7種同權重組合下的物聯網節點布局如圖4～圖10所示，其中,○表示未設置物聯網節點的監測點，*表示設置物聯網節點的監測點，虛線圓圈表示各節點監測的感應范圍。

Figure 4 Weight combination 1圖4 權重組合1

Figure 5 Weight combination 2圖5 權重組合2

Figure 6 Weight combination 3圖6 權重組合3

Figure 7 Weight combination 4圖7 權重組合4

Figure 8 Weight combination 5圖8 權重組合5

Figure 9 Weight combination 6圖9 權重組合6

Figure 10 Weight combination 7圖10 權重組合7

6 結束語

本文提出了一個面向監測應用的物聯網節點布局問題，主要側重于確定物聯網節點數量與布局方法。將問題抽象為帶有網絡拓撲關系的數據集上的抽樣問題，建立了節點相對于監測點的代表性的評價指標模型和節點之間代表性的均衡度評價模型，并在此基礎上建立了物聯網節點選擇決策模型。通過一個隨機仿真案例，分別對單目標與多目標優化問題進行了分析。結果顯示，在對物聯網節點的規模、成本、總代表性和均衡度給予不同的重視情況下，會產生不同的布局方案。并且，通過權重敏感度分析，可以發現物聯網規模對權重較為敏感，對物聯網節點的數量影響較大。

在此基礎上，考慮對于異構網絡節點的布局、物聯網節點能耗、節點之間的連通性與容錯性等問題的研究是本文需要進一步探索的課題。

[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)

附中文參考文獻:

[1] 徐久強, 柏大治, 羅玎玎, 等. 遺傳算法在WSNs多Sink節點布局中的應用[J]. 東北大學學報(自然科學版), 2008,29(6):815-818.

[2] 汪學清, 楊永田, 孫亭, 等. 無線傳感器網絡中基于網格的覆蓋問題研究[J]. 計算機科學, 2006,33(11):38-40.

[4] 李明, 石為人. 異構無線傳感器網絡中基于模擬退火算法的成本最優部署機制[J]. 傳感技術學報, 2010,23(6):55-58.

[7] 王晟,王雪,畢道偉. 無線傳感器網絡動態節點選擇優化策略[J]. 計算機研究與發展, 2008,45(1):188-195.

[8] 付華, 韓爽. 基于新量子遺傳算法的無線傳感器網絡感知節點的分布優化[J]. 傳感技術學報, 2008,21(7):1259-1263.

[10] 周利民, 楊科華, 周攀. 基于魚群算法的無線傳感網絡覆蓋優化策略[J]. 計算機應用研究, 2010, 27(6):2776-2779.