《硅谷》杂志：无线传感器网络中的K覆盖问题 |
| 2014-02-28 10:35 作者：秦 俭 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
硅谷网文 《硅谷》杂志2012年第14期刊文称，在无线传感器网络中，通常使得最少的传感器节点处于活跃状态来节省能量，延长网络的使用寿命。将区域覆盖问题近似的看成点覆盖问题，为达到完全K覆盖，给出求解最小交叉集合H的新的近似算法，算法的时间复杂度更优，仿真结果验证理论上的分析。
无线传感器网络是由大量的，任意配置的传感器节点所组成，网络覆盖是基本问题之一。环境因素，外力损坏或电量耗尽等原因都可能使得传感器节点失效，为避免失效节点影响网络正常通信，考虑使某个目标区域能被至少k个节点覆盖，来提高网络服务质量。因为所有的传感器节点的能量都是由电池提供的，所以节能是主要问题之一。为了延长传感器网络的使用寿命，通常使得最少的传感器节点处于活跃状态来节省能量。
解决k覆盖问题，延长网络寿命的算法多样。如将时间分段主休眠算法[1]、集中分布算法[2]、实践算法[3]、利用可调的感应半径给出的分布启发式算法[4]，与本文工作相近的是RKC算法[5]，将k覆盖问题归结为求解最小交叉集合，使中传感器节点处于活跃状态，达到k覆盖并节省能量。
1主要理论
每个传感器节点均能感知和监测周围区域，节点间能相互通信，既代表传感器节点也代表节点所在的位置。
邻居：节点的感应半径为，若节点落在了以节点为中心，为半径的圆内，即，，则称节点为节点的邻居。如果节点的感应半径相同，则邻居关系是相互的。
覆盖：一点落在了以节点为圆心，为半径的圆内，则称节点覆盖点。
k覆盖：个节点构成集合，若点和的欧氏距离小于的感应半径，即，则称节点集合覆盖点。显然，覆盖关系说明点落在了中至少个传感器节点的感应半径范围内。
k覆盖问题：目标区域内任意配置个传感器节点，将覆盖每个节点所在的位置近似的看成覆盖目标区域。要求区域覆盖度，即
1）每个节点位置落在至少个不同节点的感应半径范围内，即被至少个不同节点覆盖。
2）必须要活跃的节点数达到最小值。
集合系统：设集合与集合构成集合系统。无线传感器网络中所有节点的位置构成集合，显然中元素个数为，记为。中的节点的所有邻居节点构成集合，而，中元素为的子集。
交叉集合：如果集合与中每个元素均有非空交集，则称为交叉集合。即，如果中每个元素都是包含个节点的集合，那么使得H中节点处于活跃状态就能够解决覆盖问题。
k-flower：在感应半径范围内，个节点相交于一个中心点，称这个节点的集合为-flower。
由以上理论可知，覆盖问题归结为求最小交叉集合，是必须活跃的节点集合，其中中元素为-flower。使得中节点处于活跃状态达到覆盖，其余节点处于休眠状态来节省能量，延长网络使用寿命。
2新的k覆盖算法（NKC算法）
RKC算法中net-finder算法循环多次，会使得冗余节点活跃。如果RKC算法运行超过次没有找到交叉集合，就说明没有大小为的交叉集合，这个结果是在大量的循环之后才出现的，而且每次都会运行验证k覆盖的算法，验证算法每次都会检查所有的节点，在这个过程中存在大量重复工作。RKC算法中，若活跃所有节点仍不能达到k覆盖，此时算法失效。由于k覆盖问题归结为求最小支配集是NP难问题[6]，因此提出一个新的近似k覆盖算法（NKC算法），利用可调的感应半径达到完全k覆盖解决失效情况，提出的k-finder算法避免冗余缺陷，时间复杂度更优。
2.1排序
定义1：（N-邻居）：设节点的感应半径为，，，称节点为的N-邻居。
例如，，，，则的N-邻居为，记为。
定义2：（N-度数）：节点的所有N-邻居的数目称为的N-度数。如果有个N-邻居，记为。
定义3：（N-集合）的所有N-邻居构成一个集合，则集合称为N-集合。
定义4：（内部排序）：对某个点的N-邻居节点按照N-度数从大到小排列称为内部排序。若度数相同，则排序随机。
定义5：（外部排序）：对于所有点按照N-度数从小到大排列称为外部排序。若度数相同，则排序随机。
对于集合系统，k覆盖问题归结为求最小交叉集合，中元素为k-flower.N-度数大的节点有更高的优先权被选到k-flower中。对于k-flower中的某个节点，我们希望能够多次出现，因此给出内部排序的概念。为了确保k覆盖，N-度数小的点必须加入中，因此给出外部排序的概念。
2.2k-finder算法
k-finder算法分为两部分：
1）找k-flower部分
在内部排序中按照N-度数从大到小选择个节点，N-度数高的节点对延长网络寿命更有价值。基于N-度数优先权和已被选择优先权，N-度数优先权是主要优先权，就能够选出所有的k-flowers。，如果一个N-邻居节点有更高的N-度数，就首先被选择。如果一些N-邻居节点有相同的N-度数，k-finder算法选择曾经被选择过的节点，即此节点会再被选择一次。这样使得交叉集合尽可能的小。首次选择是随机的。
2）验证k覆盖部分
对于某个节点，找到一个k-flower集合后，运行验证k覆盖部分。验证算法检查所有的N-邻居节点是否被k覆盖，如果一些节点被k-flower集合k覆盖，则在外部排序中删去这些节点。
k-finder算法从外部排序中N-度数最小的节点开始运行一直到N-度数最大的节点即可。
k-finder算法选择了最有价值的节点放到中，使得足够的小。
2.3NKC算法过程
为确保覆盖要求，将感应半径看成是变量。NKC算法给出了近似最佳的求法。
1）输入个节点。所有节点有最小的感应半径。
2）找到每个节点的N-邻居节点，并标记节点的N-度数。
3）对每个节点，检查，如果，例如，在中剩下的节点中，选取与的欧式距离最小的个节点作为的N-邻居节点，改变这个节点的感应半径，使得在感应半径范围内。
4）对每个节点的N-邻居节点按N-度数排序，并对所有节点按N-度数排序。
5）对每个排序后的节点，运行k-finder算法：找到k-flowers和验证覆盖以删除冗余节点。
6）输出交叉集合。
3NKC算法的时间复杂度
在每个循环中，NKC算法时间消耗主要在初始的两次排序和k-finder算法中，需要其中为k-finder算法的运行次数。
k-finder算法包括两部分，寻找k-flower部分需要步，验证k覆盖部分需要步，其中常数是每个节点N-邻居个数的最大值，因此NKC算法的时间复杂度为。
4仿真结果
NKC算法中节点数目、目标区域大小、初始感应半径、覆盖度均为可调变量。个节点任意配置在50*50的正方形目标区域，覆盖度，初始感应半径变化范围。对比NKC算法和RKC算法得出的交叉集合的大小。
图中横轴表示感应半径，纵轴表示中活跃节点的数目。
图1H中活跃节点数对比
Fig.1thecomparisonofactivesensorsinH
5结论
本文提出了NKC算法解决无线传感器网络的覆盖问题，仿真结果说明在同样条件下NKC算法得出的交叉集合更小，节能效果好，且NKC算法避免了无效循环，应用范围更广。
作者简介：
秦俭（1981-），女，辽宁沈阳人，讲师，研究方向：应用数学。（原文载于《硅谷》杂志2012年第14期，硅谷网及《硅谷》杂志版权所有，未经允许禁止转载）
|
|
|
|
【对“《硅谷》杂志：无线传感器网络中的K覆盖问题”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
