1、第 卷 第 期 年 月传 感 技 术 学 报 .项目来源:山西省高等学校教学改革创新项目()收稿日期:修改日期:(,):,:;:;:随机通信时延下传感器连通覆盖保持算法研究郭彩萍(太原工业学院电子工程系,山西 太原)摘 要:随机通信环境下传感网络节点信息传输随机性较强,导致传感器网络的连通覆盖难以保持。为此,提出基于模拟二维分析的传感器连通覆盖保持算法。标记传感器感知范围内任意一个节点形成的感知圆,以该圆作为传感器对该节点的初步覆盖范围,分别计算该节点、相邻节点端与传感器端间接收到能量的起始时间,构建不同时延量对节点实际覆盖度、覆盖面积以及覆盖概率的影响模型。获取单节点与整个区域的覆盖范围重叠
2、部分,根据串联覆盖路径连通覆盖法约束传感器节点,实现连通及覆盖的保持。设置通信时延为 和 ,设计仿真实验。实验结果验证了所提方法受到时延环境的影响较小,且耗时更短,适应能力强,连通覆盖保持的范围更广。该方法具有实际应用价值。关键词:传感器连通覆盖;串联覆盖路径;二维平面分析法;随机通信时延环境;二维平面分析;时延量;感知范围中图分类号:文献标识码:文章编号:()现阶段,随着无线通信、嵌入式网络以及分布式信息网络处理技术的不断成长,网络资源分布广、种类多。一般情况下,网络介质的传输工作主要依靠网线、传感器以及基站等设备实现。无线传感器需要采集感知范围内的初始数据,然后通过多跳的方式将接收到的数据
3、传递给基站,基站再通过网络实现传输。这种多频段的传输方式具有一定的随机性和不确定性,且在时延较为严重的环境中,各个通信的收发端之间会缺失同步能力,此时,就需要保证能量的有效连通和覆盖,才能保证端与端之间的同步性,降低外界随机时延影响,达到最佳效果。针对传感器网络的连通覆盖保持问题,当前已经有了一些较好的研究成果。文献提出了一种连通有向传感器网络的目标覆盖增强算法。该方法先采集传感器的网络数据,计算节点重叠概率。根据概率比例推导出传感器可覆盖的最大范围,预设几个关键节点,标记几何关系,结合实际进行调整,形成连通链。但是这种方法求得的覆盖比例误差过大,导致网络连通保持的效果较差;文献提出了提出了一
4、种基于马尔可夫链蒙特卡罗()的传传 感 技 术 学 报第 卷感器连通覆盖保持算法。利用延迟消息的错误模式识别传感器节点的故障,阈值限制基于时间概率分布函数。使用阈值限制和剩余能量来检测传感器节点连通覆盖情况。但是,该方法忽略了对传感节点能量的控制,导致传感覆盖保持过程耗时较长。文献提出了一种基于有向视觉传感器网络连通保持覆盖控制方法。根据传感器环境构建视觉导向模型,通过覆盖型函数计算传感器网络中各个节点的覆盖能力,通过导向模型推导连通能力。建立约束函数,对覆盖力和连通力不达标的节点进行约束。但由于视觉导向模型一次性可计算的数量较小,需要多次输入求解,得到的数值之间时延相差过大,误差较大,有效性
5、不强。综合上述问题,提出一种在随机通信时延下也能应用的传感器连通覆盖保持算法。传感能量有效是连通覆盖问题的重要评判标准,无线传感器周围会存在大量的干扰信号导致节点多跳方式被迫改变,影响初始覆盖范围和连通标准的判定。据此,采用二维平面法,计算每个传感器节点在不同的时延环境下可得到的最远通信路径,来求得覆盖和连通参数,得出的数据具有有向关联性,准确率高。同时给出了两种传感器节点分布模型,分析其中节点之间相通和不相通的分布情况,由此可知需要从单节点的覆盖范围出发并与整个区域的覆盖范围进行重叠查找,以此作为约束条件,建立最为合理的约束函数。计算传感节点连通性对于随机通信时延下传感器连通覆盖保持问题,多
6、数研究学者首先建立覆盖网络数据集,利用线性规划选取检测区域汇总最优节点的部署情况,以达到全部覆盖且节点关联的特点。由于无线传感节点数量过多、种类较为繁杂,易存在覆盖重叠问题,影响效率和连通质量,还会造成额外的能耗。算法需要将传感器时间划分为不同的时间周期,计算每个节点的连通性并判定是否处于休眠状态,保证传感网络的整体覆盖。提出了一种模拟二维平面的分析方法,通过选取并计算任意节点在该平面上的连通向、时延量以及位置等,将这些信息作为后续连通覆盖保持的参考系数,在最大程度上提高节点的连通质量。设置一个二维平面,节点为,感知范围是以该节点为圆心选取半径值所形成的的圆形范围,计算公式为:(,)()式中:
7、表示节点的感知半径;(,)是连接点 与参照节点 之间的欧式距离。传感器信号可覆盖的全部区域用 来表示,区域内可能涉及到的网络数据并集为,计算公式为:,()式中:为活跃节点数量。若传感器的覆盖网络 大于预设的二维平面,那么称该网络就为全覆盖网络,如果只覆盖了部分区域或未完全覆盖,那么就称为局部覆盖网络。通过上述对网络覆盖程度的判断,结合当下环境中的随机时延情况,对传感器范围内的任意一点进行点覆盖度 定义:()式中:表示选取的任意一段时延 的长度;表示在时间段 内从点 网络信号覆盖到传感器接收点的时间长度。根据点覆盖度的分析规律,同理推导传感器网络在特定区域内的覆盖度值为,计算在区域 内任意一点
8、与参照点 对比的数学期望值,公式为:()()图 节点通信连通图预设一个传感器网路数据集合,若该集合内的所有节点都存在有向关系,将所有存在有向关系的通信网络 形成一种有向的连通图,如图 所示。中的一条通信路径用,来表示,该路径由多个节点共同组成,其中,每个节点之间都互为传感通信邻居。从图 中可以看出,每个节点都有一条(汇聚结点)连通路径,该 负责传感器网与外网的连接。由图中可以看到,由活动节点共同组成的集合中,都存在同样的 连通路径,集合内的节点与外部节点连接,但集合内的节点不一定互相连接。由此说明,传感器节点具有一定关联性,进行下一步保持覆盖连通时,就以求得的 数值为参考基础,给出适应随机通信
9、时延的保持算法。第 期郭彩萍:随机通信时延下传感器连通覆盖保持算法研究 随机通信时延下传感器连通覆盖保持算法从实际应用角度考虑,以提高随机通信时延下传感器连通覆盖保持能力为目的,需要算法具备容错能力强、兼容性强、协议简单易操作的特点。本文选择随机算法作为连通覆盖保持的工作的基础,分析传感器网节点受随机时延影响的分布特点及概率,从概率分析求得各个节点的实际覆盖度、覆盖面积 以及连通度 等,三者之间的定向关系为:()()式中:表示期望覆盖度值;表示期望连通度值;表示实际覆盖度值;表示实际连通度值;表示区域面积;表示传感器可以感知到范围的半径。从关系式可以得出,对于覆盖度值 来说,传感器节点数目 达
10、到一定量时,保持算法在很大概率上可以达到覆盖连通需求。即使保持算法在整体上覆盖连通概率较小,但对于其中的单个节点状态来说,每个节点与其他节点之间的覆盖连通能力都属于集中状态,表明保持能力较强,能很好缓解环境的通信时延影响。在实际的传感器网络节点部署中,若其中的某个节点与相邻节点之间都互不相通,就表明整个传感器网络就是不连通的,这种情况如图 所示。图 节点连通条件分布示意图 中虚线内区域为每个节点的最大感知范围;实线为每个节点的实际通信范围,节点 与节点、之间互不相通,覆盖不易到达,但节点、之间却是一个整体的连通集,覆盖可轻松到达。由此可得,需要从单个节点的 通信路径出发,将单节点的覆盖范围与整
11、个区域的覆盖范围进行结合,查找重叠部分。从整个网络角度考虑每个节点相对于整体的连通性,提出有针对性的连通覆盖条件,如下所示。假设 为传感器感知内的所有节点集合,作为中心连接点,同时,设置 为节点可覆盖到的集合,为节点不可覆盖到的集合,提出一种串联覆盖路径,使得保持算法可以满足所有点连通覆盖需求,约束函数如下:;():;()需要注意的是,由于传感器的实际部署区域存在一些传输信号难以捕捉且不被其他节点所熟知的节点。因此,在进行连通保持阶段,需要根据传感器节点的熟知情况设置相关参数。仿真实验 实验背景本次实验在 网络模拟仿真平台上进行,无线传感器采用的是。假设传感器部署在 的监测环境内,所涉及到的数
12、据数量为 个,传感器预设为 个,随机散布多个节点。考虑到外界环境中存在的干扰因素,传感器节点的实际感知半径为 。本文将所提算法与文献提出的连通有向传感器网络的目标覆盖增强算法和文献提出的基于树网络拓扑的传感节点连接覆盖率优化算法进行对比分析。仿真实验环境参数如表 所示。表 仿真实验环境参数项目内容语言环境节点最大感知范围 节点数量 个平均时延情况:情况:信号传播速度 执行前后传感器覆盖情况预设两种随机通信时延环境,情况一:时延量为 ,这种时延情况不会太影响传感器网络的信号传播,节点活跃度较高,节点连通覆盖保持难度较低;情况二:时延量为 ,这种时延情况已经严重影响传感器网络的信号传播,端与端之间
13、同步性差,节点活跃度较低,节点连通覆盖保持难度较高。在这两种情况下采用所提方法进行连通覆盖保持,并与上述两种方法进行对比分析,实验结果如图、图 所示,图中给出了活跃节点的覆盖分布情况。图中的虚线以内区域表示每个节点的最大感知范围,实线以内区域表示每个节点的实际通信范围。传 感 技 术 学 报第 卷图 时延 下传感器节点分布情况图 时延 下传感器节点分布情况 从图 中可以看出,原始图像(图()中节点分布不清晰,重叠现象严重,经过本文算法保持后(图()传感器网络节点之间重叠的覆盖范围减少,分布比之间更为均匀。并且,所需的节点数量更少,传感空间的留白减少,提高覆盖面积的同时降低了界定啊耗用,节点之间
14、的连通关系也较之间更为第 期郭彩萍:随机通信时延下传感器连通覆盖保持算法研究 清晰,连通性和覆盖性都得到了很大的提升。而另外两种方法虽然相对原始图像都耗费了较少的节点分布,但重叠现象严重,空间留白过多,覆盖和连通效果都表现欠佳。从图 中可以看出,相比于时延 环境下的实验结果,时延下的传感器节点分布效果更差,但差异点只存在节点间的连通度的方面,覆盖范围及重叠范围未受到任何影响。这是因为:通信时延量升高,表示节点之间网络连接传输的时间会增加,一定程度上影响了双端接收信号的同步性。时间上的误差,导致查找相邻节点相似性出现误差。通过三种方法的对比,本文算法的的实验测试结果最优,连通度的误差也在可接受范
15、围之内,不会影响正常的传感器网络运行。不同算法的耗时情况对比要想达到高质、高效的无线传感器的连通覆盖保持,要求算法在较强的随机通信时延下也能保证有效性。本次实验将以算法的执行时间作为参考指标,判定三种算法在保持同等数量的传感器节点时需要的时间,仿真实验结果如图 所示。图 不同算法的耗时对比从图 可以看出,在相同的节点数量下,本文方法比其他两种方法耗时更短。较短的执行时间可以减少节点连通时受到的外界时延干扰,提高同步能力。另外两种方法执行时间过长。这是因为:文献算法只优先考虑了节点的连通覆盖能力,忽略了环境因素影响,导致在同等周期内,存在不同时延情况的节点。并且随着时间的变化,传感器网络拓扑结构
16、也会发生细微变化,导致覆盖度和连通度逐渐脱离正常的更新周期,时间的不同步又影响了覆盖度的判定,二次计算增加了时间耗用。采用本文方法可以有效平衡传感器网络的内部关联,使网络能量精准覆盖至每一个节点,节点之间互相协调,提高运行的稳定性。结论提出一种随机通信时延环境下传感器连通覆盖保持方法。对随机通讯的时延环境及影响参数进行分析,利用线性规划选取检测区域汇总节点的时延情况。利用二维平面分析法计算传感器感知范围内每个节点的覆盖率、覆盖度、连通度参数,根据这三个参数对每个节点建立有向关系图,后续保持算法就可根据关系图进行代入分析,得到在随机时延环境下适应度最高、效果最佳的保持算法。分析覆盖度、覆盖面积以
17、及覆盖概率之间的定向关系,采用感知部署分析法得出单节点的覆盖范围与整个区域的覆盖范围之间存在串联覆盖的分布特点,给出适应度最高的覆盖路径。仿真实验证明,所提方法有效实现了传感器在随机时延环境下的连通及覆盖问题,时间耗用较少,实际应用时可使传感器网络达到负载平衡,应用优势明显。参考文献:王洁,王瑞欣,范兴刚,等 一种连通有向传感器网络的目标覆盖增强算法 浙江工业大学学报,():,:董鑫,李晓丽,富锦芸 具有盲区的有向视觉传感器网络连通保持覆盖控制 计算机应用研究,():石拓,李建中,高宏 多等级通信半径的无源传感器网络中的覆盖问题 软件学报,():李蕾,方明科 基于证据理论加权融合的无线传感器网络路由算法 吉林大学学报(理学版),():,():,:王振东,刘燔桃,胡中栋,等 改进差分进化算法下的无线传感器网络覆盖优化 小型微型计算机系统,():,():传 感 技 术 学 报第 卷 章海宁,乔富强 单自由度结构监测传感器布置优化仿真 计算机仿真,():朱正航,贾建鑫,郦振红,等 一种应用于 非授权频段通信的低时延随机接入机制 电子与信息学报,():张士兵,陈超,李业 基于能效和时延的多跳中继通信系统功率控制算法 南京邮电大学学报(自然科学版),():郭彩萍(),女,汉族,山西文水人,博士研究生,副教授,研究方向:信息与通信工程、电路设计等,。