异构传感网成本优化的节点部署策略

李 明，胡江平，曹晓莉

(1.重庆工商大学 检测控制与系统集成重点实验室，重庆 400067；2.电子科技大学 自动化工程学院，四川 成都 611731)

节点部署技术是传感器网络的一项关键技术，对传感器网络性能有着重要影响[1-2]。按照部署方式，节点部署分为确定性部署和随机部署。确定性部署是指在部署前已知节点位置信息或网络状态较为稳定的部署技术。如何在确定性部署的方式下保障网络的连通性和覆盖性能，备受研究者青睐[1]。文献[3]提出一种能量有效的采用分簇拓扑结构的分布式覆盖算法，但其为保证网络连通性的路由构造算法较为复杂。文献[4]提出了一种适用于同构节点构成的无线传感器网络最小刚性拓扑控制算法以满足覆盖与节能应用需求。文献[5]提出了一种基于量子退火算法的无线传感器网络二维目标覆盖算法，但文献研究对象是同构传感器网络。文献[6]提出了一种基于选择框的，含有最少节点的有向强栅栏覆盖算法。文献[7]提出了两种基于Voronoi的移动无线传感器网络覆盖控制方法用于优化在给定区域内无线传感器网络的覆盖控制。文献[8]利用遗传算法解决异构传感器网络中覆盖优化问题，但未考虑到网络连通问题。文献[9]提出一种基于和声搜索算法的同构节点部署策略，但忽略了工程实践中异构节点才是节点的普遍状态。同时该文章假定节点部署成本在整个区域中都是相同的，与节点的部署实际不符。上述文献[3-9]对解决节点覆盖问题提出了有效方案，然而却大多忽略了节点之间的相互通信，也就是传感器网络的连通性问题。同时仅适用于同构节点构成的传感网络，当应用于异构网络时存在诸多限制。文献[10]利用粒子群算法解决节点非均匀分布条件下异构传感网络的覆盖控制问题，但未考虑网络的连通性问题，导致成果的适用性受到限制。针对用最少的传感器节点覆盖感兴趣区域并确保传感器节点之间连通的最优化问题，文献[11]提出了基于集合覆盖的传感器网络目标覆盖算法。文献[12]对网络中存在移动sink节点的连通覆盖算法进行研究。但该算法仅适用于同构节点构成的网络。文献[13]提出一种面向能量异构的期望网络覆盖优化算法。文献[14]对节点异构条件下的传感器网络覆盖问题进行研究，忽略了网络的连通性。

上述文献尽管对传感器网络的覆盖问题进行研究并取得了一定成果，但大多忽视了网络连通性问题，也就是不仅要保证对象被监测和感知到，同时还要把监测到的数据传输到后台以进行处理。还应注意到，应用于工程实践的传感器由于制造工艺或类型不同(比如，温度传感器、湿度传感器和红外传感器等)，其感知半径、通信半径和成本等参数也不同。现有的研究成果大多假定传感器网络由相同参数的节点构成，将这些研究成果应用于由不同参数的节点构成的传感器网络中有很大的局限性。再者，传感器网络节点经常部署在恶劣的工作环境中，由于能量耗尽、物理环境和人为破坏导致节点的故障率较高。如何保证网络的容错性和提供可靠的监测服务，对于面向目标监测的传感器网络至为重要。最后，上述研究成果在部署节点时，大多假定区域中节点的成本相同，未考虑到由于部署位置差异造成的部署成本不同。

针对这些问题，考虑到目标监测应用中部署节点众多、网络连通和目标覆盖性能不高和容错性差的特点，笔者针对在给定的具有不同代价的部署位置中如何部署具有不同性能参数的传感器节点，使得在同时满足监测目标多重覆盖和部署传感器节点之间多重连通条件下的成本优化问题进行研究，提出了一种适合目标监测的最小代价的异构传感器网络容错部署策略。通过构建异构传感器节点的多重连通覆盖数学模型，借助改进的珊瑚礁算法对优化问题进行求解，在部署代价优化条件下，保证传感器网络的多重覆盖和连通性能。

1 系统模型与问题描述

1.1 节点感知模型和连通模型

节点的感知模型是研究网络覆盖性能的关键。笔者使用布尔感知模型，通过判断目标ti与节点si的距离与节点si的感知半径的关系决定监测目标是否被传感器节点覆盖。若为小于等于关系，那么目标ti被节点si感知(覆盖)。对于k覆盖和c连通，笔者采用文献[9]中的概念。

概念1(k覆盖)k覆盖是指在节点部署区域中，每个监测对象ti(i=1，2，…，W)至少能被k个传感器节点感知(覆盖)[9]。

概念2(连通) 若节点si和节点sj之间距离不大于节点si的通信半径，则两个节点si和sj是连通的。注意：此处的连通对同构节点来说是双向连通，对于异构节点则为单向连通[9]。

概念3(c连通)c连通是指每个部署在监测区域的传感器节点都至少与c个部署在监测区域内传感器节点连通[9]。

1.2 问题描述

在工程实践中，为了更准确地刻画监测对象的性质，可在监测对象周围部署不同类型(参数)的传感器节点。比如，在野外动植物监测系统中，通常要部署温度传感器节点、湿度传感器节点、红外传感器节点和视频采集传感器节点等。这些传感器节点的感知半径、通信半径、成本等参数均不相同(或者即使同一种类型的传感器节点由于制造工艺等原因其参数也不完全相同)，同时由于部署位置不同和传感器本身的特点使得节点部署代价均不同。如何在保证监测质量和网络容错性的前提下，以经济的方式部署传感器节点，是一个非常重要的问题。

对上述的工程实践问题进行抽象，也就是：假定二维监测区域内有W个监测对象ti(i=1，2，…，W) 和M个用于部署传感器节点的位置Pi(i=1，2，…，M)，每个部署位置的代价为di(i=1，2，…，M)。其中，每个监测目标ti的位置已知，且每个位置只能部署一个传感器节点。如何在现有的M个候选位置中，选择合适的部署位置(不同部署位置的部署代价不同)部署传感器节点si，u(传感器节点性能参数和成本不同)，在满足所有的监测目标能够被传感器节点k覆盖(k≥1)和布设的传感器节点之间能够c连通(c≥1)的条件下，网络部署成本最小。假定传感器节点si，u的性能指标诸如感知半径、通信半径和成本bi，u均不同，按照性能指标进行分类，有U种类型(u=1，2，…，U)。最小网络部署成本用数学语言描述为

(1)

(2)

约束(1)为每个监测目标为k覆盖；约束(2)为布设的异构传感器节点之间满足c连通的条件，S为选择的部署位置的数量。

命题：要解决的问题为NP-complete问题。

证明：首先证明其为NP问题，然后通过归约方式证明该问题的一个特殊情形(或称特例)是NP-complete 问题，从而证明该问题为NP-complete问题。

假设A为问题的一个解，采用广度遍历算法验证以当前部署位置节点为根节点的树是否符合c连通要求，其时间复杂度为O(M2)。接着，来验证对于每个监测目标是否符合k覆盖的要求。可知验证M个节点W个监测目标是否满足k覆盖，其时间复杂度为O(M×W)。可以看出，验证解A是否满足覆盖和连通的要求需要多项式的时间。因此，首先证明要解决的问题是NP问题。

当候选部署位置的部署代价都相同，且用于部署的传感器节点类型和成本都相同，要解决的成本优化问题，即转化成了如何在候选位置集合中选择最少的部署位置，使得部署的传感器节点满足k覆盖，并且每个传感器节点的类型和成本都相同。而这一问题已经在文献[15]和文献[16]中被证明了是一个NP-complete问题。综上，命题得证，要解决的问题是NP-complete问题。

考虑到要解决的问题是NP-complete问题，传感器网络大规模部署以及资源受限的情况，传统的算法比如穷举方式耗费资源较多，因此，笔者采用生物启发式算法得到算法的近似解。

2 基于改进珊瑚礁算法的异构传感器网络容错部署策略

2.1 珊瑚礁算法

图1 珊瑚礁算法流程图

珊瑚礁算法(Coral Reef Optimization algorithm，CRO)是由SALCEDO-SANZ在2014年提出的一种模拟珊瑚虫行为的智能进化算法[17]，具有良好的搜索能力和收敛速度。目前已应用于北欧风力农场设计优化[17]、有向传感器网络资源优化[18]、约束条件下的移动传感器网络部署问题[19]等组合优化问题。该算法的流程图如图1所示。

图1中，种群初始化主要完成算法参数的设置，包括附着珊瑚虫的珊瑚礁的大小，一般设为矩形；附着珊瑚虫的珊瑚礁占总珊瑚礁的比例r1，最大迭代次数T1，非性繁殖(即雌雄同体)的比例Fa，进化过程中子代允许附着的最大次数T2，每次迭代珊瑚虫被淘汰的概率g1和淘汰的数量比例r2。珊瑚虫的繁殖过程分为两类，一类为雌雄同体的繁殖过程，通过在可行区域内随机产生，另一类为雌雄异体的繁殖过程，通过模拟二进制交叉的方式产生2个子代。竞争过程，也就是子代珊瑚虫寻找珊瑚礁的过程，若寻找到的珊瑚礁无其他珊瑚虫附着，则寻找成功，该珊瑚虫附着于此，否则若已有其他珊瑚虫附着此珊瑚礁，则比较两个珊瑚虫的健康度(即适应度)，适应度优的珊瑚虫胜出，占有该珊瑚礁。此过程一直继续，直到达到最大允许的尝试次数T2。若达到最大允许的尝试次数T2时仍没找到，则该珊瑚虫死亡。淘汰过程为按照初始化时设定的淘汰概率g1和淘汰数量比例r2自动淘汰部分珊瑚虫，被淘汰的珊瑚虫附着的珊瑚礁就会被空出，以便供其他的珊瑚虫进行竞争。

2.2 改进珊瑚礁算法

改进算法(Enhanced version of CRO，ECRO)依然沿用图1所示的原始的珊瑚礁算法的流程。为了增强原始CRO算法的优化能力，一方面，借鉴和声搜索算法[20]中具有良好全局优化能力的HMCR过程和PAR局部扰动过程，并将其引入CRO算法，进一步增强算法的全局优化能力；另一方面，充分利用算法求解过程中得到的优秀解，使其更好地发挥“引导”作用。具体改进之处在于以下两点。

(1) 与和声搜索算法结合

和声搜索算法中新产生的解向量一方面来自和声记忆库(Harmony Memory，HM)，其概率为H；另一方面，新产生解向量来自变量允许的范围内的随机取值，其概率为 1-H。在新的解向量产生后，对来自和声记忆库的解向量以概率P进行局部微调[20]。通过参数H和参数P控制解产生的来源和解质量，从而使得算法具有良好的优化能力。结合原始CRO算法中雌雄异体的珊瑚虫随机产生后代的方式，笔者借鉴和声搜索算法中产生子代过程，将雌雄异体的珊瑚虫子代设定有H比例是来自于雌雄异体的珊瑚虫个体，其余的1-H比例的雌雄同体的珊瑚虫子代为按式(3)随机产生。对于雌雄同体的珊瑚虫产生子代后，以概率P进行局部扰动(类似遗传算法的变异操作)，从而增强CRO算法的优化能力和避免过早收敛。固定数值的H和P不能根据算法过程中种群的进化情况做出相应的调整，对算法的优化能力产生不利影响。为此，采用文献[21]中自适应的算法参数，即

(3)

(4)

其中，x为当前的迭代次数，X为最大迭代次数，Hmin和Hmax分别为H的最小值和最大值，Pmin和Pmax分别为P的最小值和最大值。随着迭代次数的增加，H的值逐渐减少，P的值逐渐增大，使得雌雄异体子代一方面通过H参数的控制能保持原有种群的优化能力，另一方面P的扰动增强了算法的局部搜索能力，使得算法的探索能力和开发能力得以平衡，满足问题求解的需求。

(2) 算法中优秀基因再利用

2.3 改进珊瑚礁算法时间复杂度分析

2.4 应用ECRO求解异构传感器网络容错部署问题

对于节1.2所描述的异构传感网络的容错部署问题，通过数学建模，将其转换成目标优化问题，以笔者提出的ECRO算法为工具得到优化的部署策略。结合待解决问题的特点，算法的关键部分叙述如下：

(1) 解的编码

珊瑚礁种群中的每个个体表示问题的一个解，解的维数为M×U，解的编码示意图如图2所示。

图2 解的编码示意图

图2中，解的每个位置pi，h表示第i个候选位置里是否部署传感器节点，也就是

(2) 健康度函数的设计

根据要解决的问题，在满足监测目标k覆盖和布设传感器节点之间c连通的条件下，在给定的位置集合中选择合适的位置布设合适的节点，使得部署成本最低，设计合适的健康度函数(适应度函数)。对于要处理的约束问题，采用将约束优化问题转化为多目标优化问题。结合前面的分析，笔者优化的目标有3个，分别为：

(5)

(6)

(7)

其中，max(bi，u) 表示成本最大的传感器节点。

(8)

(9)

S为选择的部署位置的数量，即布设在监测区域的传感器节点数量。对于上述3个优化目标选取的依据为：一方面，要保证没有量纲；另一方面，使目标函数的取值在[0，1]之间，也就是进行归一化处理。

对于3个优化目标在进行优化时是相互冲突的。这主要由于，一方面要保证节点的多重连通和目标的多重覆盖，使得必须选择更多的候选位置来部署更多的节点，而这导致部署成本的增加；另一方面，为降低网络部署成本，使得部署位置和部署节点类型的选择受到限制，从而又影响了网络的连通性和目标的覆盖。加权方式作为一种经典的多目标转化为单目标的方法，广泛应用在传感器网络资源优化上[22-23]。笔者用子目标加权的方法将多目标函数优化转换成单目标函数优化问题，即

F=α1f1+α2f2+α3f3，

(10)

其中，α1+α2+α3=1，αi∈[0，1]，i=1，2，3。f1为部署代价的子目标函数，其值域为[0，1]；f2为k覆盖的子函数，值域为[0，1]；f3为c连通的子函数，取值范围为[0，1]。F为最终要优化的目标函数，α1、α2和α3为3个子函数所对应的权重。F为[0，1]之间的一个值，该值越大，表示得到的解越好。

3 仿真及结果分析

3.1 仿真环境设置

表1 传感器参数表

在MATLAB 2013b平台上对提出的算法进行数值仿真验证。监测区域大小设置为200 m×200 m，监测目标数量W为75，可部署传感器节点的位置M为400。每个候选位置布设节点的代价为区间[1，5]上随机数(假定代价单位为￥)。采用文献[21]的模型，假定节点的通信半径是其感知半径的2倍。考虑到工程实践中，节点的参数性能越高，价格越贵。假定传感器节点的性能参数如表1所示。

对于部署传感器节点的位置，预设两种情形，情形1：部署传感器节点的位置随机分布在监测区域内；情形2：首先将监测区域划分成大小为10 m×10 m的网格，每个网格的中心点即为部署传感器节点的位置。CRO算法中，矩形区域设为10×5，Fa=0.1，r1=0.7，T2=3，g1=0.1，r2=0.01[17]；ECRO算法中，Hmin=0.6，Hmax=0.8，Pmin=0.05，Pmax=0.3[20]，最大迭代次数T1为400，E=1，其他参数设置同CRO算法。进行优秀基因再利用中的参数Z设置为当前迭代次数能整除20时进行。

下面通过仿真实验来检验提出的ECRO算法的性能表现。为确保结果的可信性，每一个仿真结果均为50次独立运行算法所得到结果的平均值。

3.2 仿真结果及分析

(1) 不同权重下子目标比较

设置覆盖度k=2和连通度c=2，分别在情形1和情形2两种情形下对改进算法和未改进珊瑚礁算法的3个子函数进行比较，仿真实验结果详见表2和表3。

表2 情形1不同权重下子目标取值

表3 情形2不同权重下子目标取值

从结果可以看出，在不同的权值系数条件下，改进算法ECRO求解的3个子目标函数F1、F2和F3均优于原始CRO求解算法，证明了改进方案的优越性。得益于笔者提出的两种改进种群优化能力的策略使得珊瑚虫种群的全局和局部搜索能力增强，从而在目标函数优化方面优于原始的CRO算法。同时，当3个子目标的权重分布比较均匀即取值为(0.3，0.35，0.35)时，子目标取值在表中所列出的权值集合中取值最优。

(2) 不同数量候选位置条件下的网络部署代价比较

为比较在不同连通和覆盖要求以及不同候选位置条件下改进算法ECRO部署成本的优化效果，分别在场景1和场景2利用ECRO算法进行仿真，3个子目标的权值分别设为0.3、0.35和0.35，结果如图3和图4所示。其中，(k|c)为监测目标的覆盖度和布设节点的连通性要求。从图中可以看出，在相同的可放置节点的候选位置数目条件下，连通和覆盖要求越高，所需的节点部署代价越多。在相同的连通和覆盖条件下，随着横坐标可放置节点的候选位置数目的增加，纵坐标算法求解得到的网络部署代价也随之增加。这主要由于节点候选位置的增加具有随机性，增加的候选位置若分布比较分散且在该位置的部署节点代价较高的话，就需要更多的节点部署在新增的代价较高的部署区域以维持区域的覆盖度和节点之间的连通度，从而导致节点部署代价的增加。

图3 情形1中不同连通和覆盖要求下的网络部署代价

图4 情形2中不同连通和覆盖要求下的网络部署代价

(3)算法性能对比

将部署传感器节点的位置M设为200，分别在情形1和情形2下对提出的改进算法、原始珊瑚礁算法、文献[21]提出的GA算法、LADE算法和贪婪算法进行仿真实验，3个子目标的权值分别设为0.3、0.35和0.35，求解结果详见图5～图10。图中横坐标(k|c)为监测目标的覆盖度和布设节点的连通性要求。从图中的结果可以得出，在(k|c)的值一定的情况下，提出的改进算法求解的网络部署代价、子函数F2和F3均优于其余4种比较算法。比如，当横坐标为(3|3)时，较之贪婪算法、CRO算法、GA算法和LADE算法，ECRO算法在保证F2和F3取值最优情况下，部署代价最低。其中，情景1中ECRO算法求解的部署代价降低13.6%、4.6%、 8.7%和1.6%，情景2中ECRO算法求解的结果降低11.4%、6.3%、7.67%和5.2%。同时，ECRO算法在表征覆盖和连通性能的F2和F3中也优于4种比较算法，证明了改进算法的有效性。出现上述结果的原因为：使用贪婪算法得到的结果本质上是个局部最优解，在诸如笔者要解决的连通覆盖一类的复杂组合优化问题上，求解得到的结果往往劣于具有全局优化能力的进化算法。较之原始CRO算法、GA算法和LADE算法，改进算法ECRO一方面通过借鉴和声搜索算法中良好的算法结构框架，使得算法全局搜索能力增强，另一方面通过对算法迭代过程中优秀解基因的再利用，提高了算法的优化能力。

图5 情形1中的函数F2比较

图6 情形2中的函数F2比较

图7 情形1中的函数F3比较

图8 情形2中的函数F3比较

图9 情形1中的网络部署代价比较

图10 情形2中算法的网络部署代价比较

4 结束语

笔者提出了一种基于改进珊瑚礁算法的面向目标监测异构传感网成本优化的覆盖连通算法。该算法主要用于解决二维区域内节点性能指标异构和传感器节点之间的多重连通以及区域监测目标的多重覆盖条件下的成本优化部署问题。下一步的工作在于，研究更贴近工程实践的优化方法和优化模型。在优化方法上，寻求一种低复杂度且不依赖经验确定权重的解评价方法。在优化模型上，一方面，将障碍物引入部署模型，对有障碍物条件下的部署优化技术进行研究；另一方面，将连通概念与多跳路由算法结合，拓展连通概念的内涵，研究更具普适意义的覆盖连通算法，满足工程实践的要求。