COMPUTERENGINEERINGANDDESIGN Apr.2018Vol. 39 No. 4
基于Harmony搜索算法的节点部署方案
刘君12
(1.潍坊科技学院中印计算机软件学院，山东潍坊262700&2.潍坊科技学院山东省高校设施园艺实验室，山东潍坊262700)
摘要：无线传感网络(wireless sensor networks，WSNs)的覆盖问题就是优化节点部署，其目的在于给传感节点找到最 优的位置，以最小的节点满足覆盖要求。为此，提出基于Harmony搜索算法的优化节点部署方案（Harmony search based optimal nodes deployment，HS-OND)。结合网络覆盖率、传感节点数和传感节点间最小距离建立目标函数，利用Harmony
搜索（Harmony search，HS)找到最优的节点位置和节点数，最大化网络覆盖并最小化网络成本。实验数据表明，HS- OND方案能够有效找到最优的节点数和节点位置，提高网络覆盖率，延长网络寿命。
关键词$无线传感网；节点部署&覆盖问题& Harmony搜索；网络成本中图法分类号！ TP393
文献标识号$ A
文章编号$ 1000-7024 (2018) 04-0987-05
doi： 10. 16208/.. issnl000-7024. 2018. 04. 016
Harmony search based nodes deployment
LIU Jun1，2
(1. Department of Sino-India
Computer Software，Weifang
University
of
Science and
Tech
2. Facility Horticulture Laboratory of Universities in Shandong，Weifang University of Science
and Technology，Weifang 262700, China)
Abstract： In wireless sensor networks , coverage problem is a devoted study of the node placem
jective is to find the optimal locations to place sensor nodes，so that the number of nodes can be minimized and the coverage requirements can be satisfied. Harmony search based optimal nodes deployment (HS-OND) scheme was proposed. An objectivefunction was established
combining
network coverage ratio , optimal number of
the number sensor
nodes
of sensor nodes and
and the minim
sor nodes，to support the selection of the their locations，to maxim
and minimize the network cott Experimental results show the ability of the proposed HS-OND to find the appropriate number ofsensor nodes and their locations. HS-OND improves the network coverage and network lifetime.
Key words： wireless sensor network； nodes deployment； coverage problem； Harmony search; network cot
/引言
传感节点部署节点目的在于给所有传感节点找到最合 适的位置，进而既满足网络覆盖又降低网络成本[1]。然而， 由于WSNs节点数量的巨大，部署传感节点成为存在挑战。 此外，传感节点存在多项，如能量、数据处理能力和 通信容量。这些影响了 WSN的性能，如传感节点间的 通信连接、网络覆盖以及网络寿命)]。
现存的节点部署方案主要分为：随机性部署和确定性收稿日期：2017-02-22;修订日期：2017-05-17
部署12]。当感测区域过大，随机性部署可能是最好的选 择。在随机部署方案中，传感节点随机性分布于感测区域。 然而，随机性部署传感节点会导致传感节点分布不均匀， 有些区域部署过稀，导致网络覆盖率不达，出现覆盖空 洞）];有些区域部署过密，增加了部署成本。
换而言之，确定性部署是用于给传感节点寻找最优的 位置，满足服务要求，即网络覆盖率。换而言之，以最少 的节点数，满足网络覆盖要求。因此，传感节点的部署是 受网络覆盖和网络成本的约束45]。在这些方案的近似优化
基金项目：2014年度潍坊科技学院校级课题“基于物联网技术的高等院校智能卡管理系统”基金项目（W14K027);国家自然科学基金项 目（61572283);山东省优秀中青年科学家科研奖励基金项目（BS2014DX005);山东省高校科研计划基金项目（J15LN06); +十三五”山 东省高等学校科研创新平台立项基金项目（鲁教科字[2017] 4)
作者简介：刘君（1986-)，女，山东潍坊人，硕士，助教，研究方向为物联网技术及其应用。E-mail: liu」in;jin@yeah.net
• 988 •
计算机工程与设计
2018 年
算法能解决节点部署问题[6 9]。这主要是因为确定性部署方 案受多个设计目标影响。解决多个目标的优化问题是一个 NP-Hard问题，无法用多项-时间算法解决此问题)0]。
Harmony 搜索（Harmony search，HS)算法）1]是元启
向量表示一些传感节点的位置。因此，HSBND算法就是 从一群解向量中寻找一个最优向量，传感节点就是依据此 最优向量所指示的位置部署。换而言之，HS-OND算法的 目标函数就是寻找最优解向量。
HS算法主要涉及5个参数：①Harmony存储容量 HMS(Harmonymemorysize)，即 HM 内的解向量数；② Harmony 存储顾虑率 HMCR(Harmonymemory considering rate)，且HMCR为0至1的有理数；③调整率PARCpitch adjusting rate)，且PAR为0至1的有理数；④带宽BW，
发式(meta-heuristic)优化算法。文献[2, 13]表明，HS 能够解决大范围的NP-Had问题。
为此，本文利用HS算法特性，解决网络覆盖问题， 致使通过优化传感节点位置，减少传感节点数，并满足覆 盖要求。因此，本文提出基于HS的HSBND算法。HS- OND算法先建立目标函数，其融合了网络覆盖率和网络成
本。实验数据表明，提出的HS-OND算法能够有效地优化 节点部署，降低成本，并延长了网络寿命。
1系统模型
假定被监测的网络区域为A，其二维维度分别为宽度
W和高度H。将监测区域A划分为rnXn个元区（Cell)，
每个元区尺寸取决于传感节点的感测半径兄。此外，将每 个元区中心点，称为需求点（demand point，DP)。它的二 维坐标分别为^，^，它们分别表示元区块的第^行和第 ，列，如图1所示。
NP点
感测范围
图1网络模型
图1描述了 A = 50X 50的网络区域，小黑点为每个元 区的NP。三角形表示传感节点。每个传感节点具有相同的 圆形的感测范围。
2 HS-OND算法概述
HS-OND算法的目的就是以最小的成本（传感节点数）
实现最大化网络覆盖率。换而言之，HS-OND算法通过HS 算法，优化传感节点的部署，进而最大化网络覆盖。因此， 目标函数主要涉及两个因素：网络覆盖率和传感节点数 (成本)。2.1 HS算法
HS算法就是优化一群解向量（solution vector)的过
程。存储解向量的单元称为HM(Harmonymemory)。每个用于提高HS的性能；⑤停止标准，即HS算法的迭代 次数。2.2目标函数
HS-OND算法就是优化传感节点部署，进而以最小的
传感节点数实现最大的网络覆盖。因此，目标函数如式(1) 所示
F _Yj =5 X #ratio XM _ dist ⑴
式中：s为传感节点数，其表示网络成本。s值越大，成本 越高。反之，越小。C'o表示网络覆盖率，其反映了对网络 服务质量要求，因此，Cso越大越好，其定义如式（2) 所示
Crano = Neff/N〇U
⑵
式中：Nd/为部署的传感节点数，而风3为监测区域的总的 位置数)](
而M_d;s表示传感节点间的最小距离，其定义如式(3) 所示
M _
dis' = mmn，z)d(i，3
$)
槡 Wi8Hi式（）的分子min,，/)d；，，）用于计算两节点间的最 小距离。而分母用于计算最大长度，也就是监测区域的对
角线距离。因此，W!、H!分别是W、H的修改成，其定 义如式$)所示
式中：尺为传感节点的感测误差。
3 HS-OND 算法
3.1初始阶段
首先，将存储解向量的HM定义为解矩阵，其行等于 HMS的长度、列为N，即为每个解向量的宽度，如式（）
所示
，1
， …，N，2
，2
…
，N2
,、
在HM的初始阶段，从所有可能值范围内随机产生解
第39卷第4期
向量，且每个值在区间U
^
刘君
：
基于Harmony搜索算法的节点部署方案
• 9 •
W内。式中：/Zoor$)为向下取整的函数。
假定第z个传感节点&的坐标位置为（^，％ )，再依 据式$2)更新
在HM矩阵中，每个元素&编码一个节点位置，这个 位置由^^构成。同时，^^的下限如式（6)所示
例如，在（50，25)的网络区域内，假定兄= 10、尺（ 5，则
( 50 ? 10 ? 5 ( 35、
( 25 ? 10 ? 5 ( 10。
的上限
此外，对于宽度为W和高度为H的网络，定义如式$)所示
如果随机数rand大于HMCR，就利用式（3)更新 位置坐标
fxs. = L* 8 U* — L* ) Xrand(•)
0 U ； (13)
W*； = w- (Rs~Re )-
$)
\\Uy; = H—(RS—Re)因此，传感节点的随机位置由式（8)产生
(xsl = L*s 8 CU*s ? Lxs ) - X rand (•)(ysl = Ly； 8 CUys — Ly； ) X rand (•)
(8)
式中：rand$)---产生随机数的函数。
对于每个解向量的宽度N，HS-OND算法允许每个解向量编码不同的传感节点数。例如，第一个解向量编10个节点，而第二解向量编6个节点。为此，给每个解向量定义可编的传感节点的最小数M&S和最大数MaxS，它们的定义分别如$)所示
M&S ( 2(尺8兄）0 2(尺8兄) …
因此，每个解向量可编的传感节点数LMye&是由式 $0)产生
HM 由于每个解向量长度等于Ma*s，而每个解向量可编 码的传感节点数小于Ma*s。因此，将解向量中未能编的 传感节点，即未使用的位置标记为“ ◊”。例如，在（0, 25)的网络区域内，假定Rs = 10、Re = 5，因此，MOxS =25、MnS = 3。因此，HM<3&在3与25间随机产生。 例如，一个解向量HM 先利用式（）所示的HM产生初始解向量。第一传感 节点从HM的第一列随机产生一个数作为其X轴坐标。例 如，传感节点；的*轴坐标xS1从HM的第一列向量{*1， *2 *3，…，xHS }随机选择作为其值，类似地，再从{ys1， y1，y3，…，yH^ }中随机选择作为其y轴的坐标。 然后，产生一个随机数rand，且rand , (0，1)。如果 rand小于HMCR，则再产生数randLoc，定义如式（11) 所示 randLoc = 1 8 floor {rand X HMS) (11) ; ;2 y. = Lys 8 (Uys — Lys ) X rand (•) 依据式（12)或式（13)更新的解向量；。如果更新 后的解向量/的传感节点数Nwm _ ector小于MnS，就 丢弃此解向量/，否则就利用/代入目标函数，并计算 值。如果只_而（/)小于F_^()，就将/替换 ;。即丢弃；存储/。并将F_^(/)的值作为最小值。若 迭代次数小于M ，就继续迭代。当迭代次数结束后，HM 中存留下的解向量就是最佳解向量，即传感节点的最优部 署方案。 整个HS-OND算法的伪代码如图2所示。 HS-OND方案 1 input： F _ obj, HMCR, HMS, bw, NI W~H,Rs,Re,Cell SizeLx , UXs, L}>s, Uys, MinS, MaxS, HMVlen 2 HM <— Generate initial poplution3 While [iter^Nl) do 4 while (i ^ MaxS) d〇5 if [rand < HMCR) then6 = MinS + i^MaxS - MinS) x rand (•) 7 _ ^^randljoc S 3^5. _ y^randLoc8 Else 9 \\ = L、' +、' 'UXs - Lx、xrand10 ^ =Lys +(^ -Ly )xrand(-) 11 End if12 End while 13 Update sf14 if (Num _ vector ^ MinS) then15 if (F_obj(s') S — S，17 End if 18 Else 19 Reject s' 20 End if21 End while 22 Output： find the best solution in HM 图2 HS-OND方案的伪代码 4性能分析 4.1仿真场景及性能评价指标 利用Matlab软件建立仿真平台。考虑50X50 m2的监 控区域，而监控区域的监测位置取决于实验设置。将50X 50 m2区域划分25个监测位置，每个元区由大小为10 Xm2，如图 3 所示。 10 • 990 • 60 计算机工程与设计 2018 年 值，而后者表示实验仿真结束后，节点所剩余的能量与初 始能量之比。 $)网络寿命 从图4可知，HS-OND方案和随机Random方案的归 一化网络寿命随兄增加呈增长趋势。原因在于：兄的增加 有利于传感节点感测环境数据。与Random方案相比，HS- OND方案的归一化网络寿命得到显著地提高。例如，凡（ 100时，兄=9、兄=36两种情况下，归一化网络寿命分别 为0.77和0.92,远高于随机Random方案。这些数据充分 _1-10 0 10 20 30 40 50 60 图3仿真模型 此外，依据文献）4，15*设置HS参数：HMS ( 30，HMCR ( 0. 9、^ ( 0. 2 以及 ( 60 000。同时，选 择1A算法进行参照。4.2实验数据 4.2. 1 实验一 首先，考查元区尺寸和传感节点半径尺对HS- OND算法性能。实验中分别考虑3种场景：在场景一中， ( 10 X 10，兄（10 m # 在场景二中，( 10 X 10， 疋（5 m #在场景三中，( 5 X 5，兄（10 m。实验数 据见表1。 表1 实验数据 HS-OND方案 随机部署方案 场景一场景二场景二场景一场景二场景二 最大覆盖率100%96%90%72%80%68%部署节点数 15 5221133216平均覆盖率93% 91% 80% 51% 57% 41% 从表1可知，HS-OND方案在场景一的环境中达到 100%覆盖率，而随机Random方案的最大覆盖率仅为 72j。换而言之，HS-OND方案利用15个传感节点能使得 最大覆盖率达到10%，而随机Random方案用13个传感 节点达到的最大覆盖率仅为72%。因此，HS-OND方案的 平均覆盖率达到93%、而随机Random方案的平均覆盖率 仅为51%。类似地，在场景二、场景三的环境下，HS- OND算法的性能均优于随机Random方案。 4. 2. 2 实验二 为了更好地分析HS-OND方案性能，选用随机部署节 点方案与HS-OND方案进行参照，并进行比较。在本次实 验，网络区域为400X400 m2,其中节点数为凡（50、 =100两类情况，每个传感节点能量为25 J，传感节点 感测半径兄从1变化至49。同时，选用归一化网络寿命 (normalized lifetime)和剩余能量百分比作为性能指标。前 者等于将100次实验中寿命最大值与100次平均寿命的比 说明，HS-OND方案通过优化部署传感节点，降低成本， 减少覆盖重叠区域，进而提高网络寿命。 0 5 10 15 20 25 30 35 40 45 50 感测半径7?s -0- random, N=50 HS-OND, N=50 —〇 - random，7V= 100 —□ - HS-OND，7V=100 图4 400X400 m2网络内的归一化网络寿命(2)剩余能量 图5描述HS-OND方案和随机Random方案下在达到 网络寿命时，节点的平均剩余能量百分比。从图5可知， 随着兄的增加，剩余能量百分比均下降。然而，随着兄的 增加，剩余能量百分比下降率减少，当剩余能量百分比低 14j后，剩余能量百分比随兄增加而下降很慢，当兄=49 时，剩余能量百分比仍达到12j。 6 o 4 o2 o o oox3 = 2 马^o………1 ^ \\V^o\\ . — _n—-—-------------E 3-----------! 仔n -------i ---------□ o ) 5 10 15 20 25 30 35 40 45 50 感测半径 —©— random，jY=100 —□— HS-OND, A^=100 | 5 400X400 m2网络内的剩余能量百分比 第39卷第4期 刘君：基于Harmony搜索算法的节点部署方案• 991 • optimization and Voronoi diagram [C] //International Confe 5结束语 网络覆盖是无线传感网络研究热点，也是部署无线传 rence on Networking， 2009 ： 602-607. [8] Cayirpunar 0, Kadioglu E. Optimd base station mobility pa- terns for wireless sensor network lifetime maximization [J], IEEE Sensors Journal， 2015， 15 (10)： 6592-6603. 感网络的目的所在。本文提出HS-OND的节点部署方案， 其目的在于以最少的节点数实现网络覆盖的最大化。HS- OND通过寻找传感节点最优位置，保证每个节点的覆盖最 [9] Abidin ZH， Din NM， Radri NAM. Deterministic static sensor node placement in wireless sensor network based on territorid predator scent marking behavior [J], International Journal of Communication Networks f Information Security， 2013， 5 大化，避免覆盖重叠。在维持网络覆盖的同时，降低网络 成本。实验数据表明，与随机部署方案相比，在维持同等 覆盖率的条件下，HS-OND方案的节点数下降，并且网络 寿命有所提高。参考文献： [1] WangB, Coverage problems in sensor networks： A survey [J]. ACM Computing Surveys， 2011， 43 (4)： 1-53.)]Dei£ DS， Gadallah Y. Classification of wireless sensor ne-- works deployment techniques [J], IEEE Communications Su-- veysf Tutorials，2014，16 (2): 834-855. [3] AghikhakiZT，Meratnia N， Havinga PJM. A trust-based probabilistic coverage algorithm for wireless sensor networks [J], Procedia Computer Science， 2013， 21: 455-4.[4] Mulligan R， Ammari HM, Coverage in wireless sensor net works： A survey [J], Protocols Algorithms， 2013, 2 (2): 27-53. [5] Sangwan A， Singh RP. Survey on coverage problems in wire less sensor networks [J], Kluwer Academic Publishers， 2015， 80 $): 1475-1500. [6] Chen CP， Mukhopadhyay S， Chuang C， et al. Efficient cove rage and connectivity preservation with load balance for wireless sensor networks [J], Sensors Journal IEEE， 2015， 15 (1)： 48-62. [7] Aziz NABA， Mohemmed AW， Alias MY. A wireless sensor network coverage optimization algorithm based on particle swarm (3)： 186-191. [10] Chakrabarty K， Iyengar SS， QiH，et al. Grid coverage for surveillance and target location in distributed sensor networks [J], Computers IEEE Transactions on，2002, 51 (12)： 1448-1453. [11] Geem ZW，Kim JH， Loganathan GV. A new heuristic opti mization algorithm： Harmony search [J] J Simul， 2013， 76 (2)： 60-68. [12] Alia OM， Mandava R. The variants of the harmony search algorithm： An overview [J] Artificial Intelligence Review， 2011， 36 (1)： 49-68. [13] Manjarres D， Landa-Torres I， Gil-Lopez S， et al. A survey on applications of the harmony search algorithm [J], Engineering Applications of Artificid Intelligence， 2013， 26 (8)： 1818-1831. [14] Alia OM，Shaaban Z， Basheer A，et al. Musicians? -in spired clustering protocol for efficient energy wireless sensor networks [C] //Internationd Conference on Communications f Networking， 2014： 1-6. [15] Chen CP， Mukhopadhyay SC， Chuang CL， et al. A hybrid memetic framework for coverage optimization in wireless sensor networks [J]. IEEE Transactions on Cybernetics， 2015， 45 (10)： 2309-2322.
因篇幅问题不能全部显示，请点此查看更多更全内容