面向监测应用的物联网节点布局方法研究

杨 斌，郝杨杨，李军军

(上海海事大学物流研究中心，上海 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.