传感器网络中基于Voronoi网格的快速覆盖判定算法

覆盖问题是传感器网络研究中的一个基础课题,判定感兴趣的区域是否被一组给定的传感器节点完全覆盖,在监控等传感器网络的许多应用领域中具有重要意义。提出了一种传感器网络中基于Voronoi网格的快速覆盖判定算法VT-RCDA(Voronoi Tessellation based Rapid Coverage Decision Algorithm)。算法首先将感兴趣的区域进行正方形网格剖分,然后采用Voronoi网格模型将复杂的区域覆盖问题转化为简单的顶点覆盖问题。理论分析与仿真实验表明,与已有算法相比,新算法具有较好的覆盖判定正确率,较低的计算复杂度,且针对具有n个节点的传感器网络,能在O(nlogn)的时间开销内快速判断出任意给定感兴趣区域能否被这n个传感器节点覆盖。     

无线传感器网络中一种关键节点集轮换算法

针对传感器网络多跳通信和多对一的流量特征,提出负载均衡的约束条件,将关键节点集选取问题转化为多目标优化问题,提出一种基于非支配遗传算法的关键节点集轮换算法.通过节点密度控制机制,从投放的节点池中选取关键节点集,以满足监测区域覆盖连通.在每轮网络工作的开始,激活不同的关键节点集,保证在每个时刻,有且仅有一个节点集完成对网络的充分覆盖.仿真结果表明该算法能够快速收敛于最优解,极大化网络关键节点集数目,有效延长网络的生存时间.     

传感器网络中与节点位置无关的覆盖算法

在不能获取节点精确位置信息的条件下,现有的基于分组的节点调度算法不能保证各个组内的传感器节点均匀分布在目标区域,导致传感器网络难以获得较好的覆盖性能.提出了两种调度算法:与节点位置无关的集中式覆盖算法和分布式覆盖算法,在定位设施缺失的条件下,使得各个组内的传感器节点较为均匀地分布在目标区域.算法分析和仿真实验证明了算法的有效性.     

基于虚拟力的无线传感器网络覆盖增强算法

为保证网络的覆盖功能,提出了一种在固定传感器节点中加入具有运动能力的移动节点的混合无线传感器网络模型.在此基础上,基于人工势场法的思想,提出了一种基于局部虚拟力的无线传感器网络覆盖增强算法,构造了节点与节点、移动节点与目标区域边界之间的相互作用力,并基于运动图式理论来共同控制移动节点的运动.为避免移动节点陷入局部极大覆盖陷阱,还引入了随机扰动作用力.最后通过仿真实验验证了算法的有效性.     

传感器网络中基于最小覆盖重叠的移动部署

为了优化随机部署的传感器网络的覆盖率,提出了基于最小覆盖重叠(MCO,Minimum Coverage Overlap)的分布式移动部署算法.算法执行时,每个节点根据获得的邻居节点位置信息,计算节点覆盖圆周上覆盖重叠的分布情况,并沿着最大程度减小覆盖重叠的方向移动.通过算法的迭代运行,使网络覆盖重叠程度尽量减小,从而最大限度的优化了网络的覆盖率.仿真结果表明,与基于Voronoi图的算法相比,MCO算法在覆盖率、移动效率、移动距离和部署时间等方面具有更高的性能.     

面向移动点的稳健动态Delaunay三角剖分技术

动态Delaunay三角剖分（Delaunay triangulation, DT）技术可应用于空中目标冲突检测领域,从而有效降低检测算法的计算复杂度。针对计算复杂度降低带来的检测可信度问题,提出一种面向移动点的Delaunay网格拓扑动态维护算法,通过实时维护网络拓扑结构确保检测可靠性,并利用局部优化技术（local optimization procedure, LOP）进一步降低计算复杂度。理论分析和实验结果都表明,算法有效地兼顾了计算复杂度和检测可靠性,是一种稳健的动态Delaunay三角剖分技术。     

网络节点重要度的快速评估方法

对网络节点进行重要性评估, 快速发掘重要性节点已经成为数据挖掘、复杂网络中的一个基本问题, 现有的节点重要度评估方法对于大型网络而言, 计算速度较慢. 基于电阻网络提出一种快速实用的节点重要度评估方法, 该方法利用节点对网络电能消耗的影响来评估节点的重要度, 如果由于一个节点的存在而导致网络平均电能消耗减少, 则该节点就越重要, 反之则该节点重要度就低. 该方法的时间复杂度为O(n³), 在分布式扩展的情况下可达到O(n), 实验分析证明了该方法的有效性, 而且运算速度快, 能处理大规模网络.     

基于共享最近邻探测社团结构的算法

针对经典重叠社团结构发现的派系过滤算法中派系定义过于严格、算法缺乏实用性、时间复杂度高等问题,提出了一种基于共享最近邻的社团结构发现算法. 该算法不仅可以对网络进行社团结构的划分, 而且可以很好地把网络中的桥点找出,算法的时间复杂 度约为O(nhk), 其中n为网络中的节点数,h为核心社团的数目, k为网络中节点的 最大节点度.为了验证该算法的正确率和性能, 把该算法应用到计算机生成网络和真实网络中, 并与著名的社团探测算法——GN算法和NF快速算法进行了比较.实验的结果表明所提出的算法是有效可行的.     

能力与权力:大规模复杂网络重要节点识别的二重异质指标及算法

为快速识别大规模复杂网络中的重要节点,本研究将人类社会普遍存在的两类不平等映射为节点在网络中的能力与权力的二重异质性,设计了评价复杂网络节点重要度的DH指标,构造了用于DH指标快速分布式计算的并行随机距离渐进(parallel random distance approach,简称PRDA)算法.通过网络最大连通率、网络均衡熵、算法有效性和算法效率的评价实验验证DH指标及PRDA算法的有效性,得出结论如下:DH指标在识别重要节点时能适应不同拓扑特征的复杂网络,识别性能优于或同于时间复杂度更高的介数;PRDA估计算法在最短路径获得概率p=1-10~(-1.5)的水平上得到的节点效率估计值■与真实值η_i的Pearson相关系数在0.975以上,且在大规模网络上进行节点效率估计结果更可靠;在Apache Spark并行内存计算环境中应用时间复杂度为O(n~2/l)的PRDA算法求解DH指标耗时远小于介数求解耗时,这表明算法的时间特性也适于大规模网络.     

基于网络权重的多社团网络结构划分算法

利用社团网络的统计特性,提出一种适于社团网络线性时间复杂度的多社团识别算法.构造复杂网络中节点的权重计算函数,进而生成计算序列,用迭代算法对复杂网络各种类型的节点进行集合分配.通过多个不同规模的网络结构数据对算法的性能进行测试,实验结果表明该算法时间复杂度为线性,能够在较短时间内对复杂网络中的社团数和社团结构进行发现,该算法还表现出对不同密度网络社团识别良好的适应性.     

多传感器优化部署下的机动目标协同跟踪算法

针对资源有限的传感器网络中目标动态跟踪问题,提出了一种能够自适应选择跟踪传感器的机动目标协同跟踪算法。首先,采用粒子群优化算法优化传感器网络能耗与有效覆盖率,进行传感器位置部署;然后,以最大化候选传感器的Rényi信息增量与最小化传感器间信息传递能耗为适应度函数,采用二进制粒子群优化算法自适应选择最佳跟踪传感器组;最后,利用交互多模型粒子滤波对机动目标位置进行估计并进行分布式融合。仿真结果表明,与现有方法相比,该方法可在非高斯非线性环境下自适应选择最优跟踪传感器,显著提高目标跟踪精度,降低网络能耗。     

基于虚拟传热的能耗均衡幂律重部署算法

针对大规模双层无线传感器网络自移动传感器节点覆盖控制的能耗均衡问题,提出一种基于虚拟传热的重部署算法。建立了以二次熵为基础的幂律熵模型,设计传感器节点与汇聚节点之间的绝对移动方法;利用邻居节点之间幂律熵流动的平衡关系,建立熵平衡方程,采用相对熵求得相对移动中参照节点选取概率的权重,设计相对移动方法。叠加两种自移动方法,进行迭代,达到网络熵平衡。实验表明,所提算法能够高效实现能耗均衡,及时避免能量空洞,延长了网络生命周期,并提升了覆盖率。     

基于改进d-Xdraw算法的起伏地形下异构多传感器分簇部署方法

为解决起伏地形环境下异构多传感器网络表面覆盖问题,提出了多传感器多阶段分簇部署方法。首先,考虑地形遮挡效应,给出了起伏地形环境下的传感器侦察与通信模型。其次,为快速获取传感器覆盖范围,构建了基于视线交点相似性判断的改进型d-Xdraw可视域求解算法。然后,为增强覆盖率,采用分簇部署策略,将传感器部署过程分为多个阶段,并结合各阶段特点分别采用微粒群和改进虚拟力算法进行求解。实验表明,改进d-Xdraw算法能够在牺牲少量精度的同时,有效提升可视域的求解速度;相较于传统的直接优化部署方法,多阶段分簇部署方法可节省最多26.7%的运算时间,覆盖率可提升10.9%。     

Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks

Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a 7△/log2｜s｜＋c, new approximation algorithm for this NP-hard problem with guaranteed performance ratio which significantly reduces the current best ratio of △- 1, where S is the set of sensors containing source data, A is the maximal number of sensors within the transmission range of any sensor, and e is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.     

Energy efficient target tracking algorithm using cooperative sensors

Target tracking is one of the applications of wireless sensor networks(WSNs).It is assumed that each sensor has a limited range for detecting the presence of the object,and the network is sufficiently dense so that the sensors can cover the area of interest.Due to the limited battery resources of sensors,there is a tradeoff between the energy consumption and tracking accuracy.To solve this problem,this paper proposes an energy efficient tracking algorithm.Based on the cooperation of dispatchers,sensors in the area are scheduled to switch their working mode to track the target.Since energy consumed in active mode is higher than that in monitoring or sleeping mode,for each sampling interval,a minimum set of sensors is woken up based on the select mechanism.Meanwhile,other sensors keep in sleeping mode.Performance analysis and simulation results show that the proposed algorithm provides a better performance than other existing approaches.     

传感器网络中高能效可靠通信的跨层优化策略

低能耗/高可靠通信问题是传感器网络应用中的一个重要研究课题,即如何在满足应用所设定的端到端可靠性要求的前提下实现能耗最小化,在物理层引入功率控制的策略,逐渐增加发送功率,直至满足可靠要求,从而降低不必要的能耗;在数据链路层提出了一种能量高效的组确认数据重传机制,尽量降低数据重传过程中冗余信息.并在此基础上,提出一种跨层联合优化算法,以解决低能耗/高可靠通信问题.最后通过NS-2仿真实验证明了该算法能够满足传感器网络低能耗/高可靠的应用需要。     

Distributed event region fault-tolerance based on weighted distance for wireless sensor networks

Event region detection is the important application for wireless sensor networks (WSNs), where the existing faulty sensors would lead to drastic deterioration of network quality of service. Considering single-moment nodes fault-tolerance, a novel distributed fault-tolerant detection algorithm named distributed fault-tolerance based on weighted distance (DFWD) is proposed, which exploits the spatial correlation among sensor nodes and their redundant information. In sensor networks, neighborhood sensor nodes will be endowed with different relative weights respectively according to the distances between them and the central node. Having syncretized the weighted information of dual-neighborhood nodes appropriately, it is reasonable to decide the ultimate status of the central sensor node. Simultaneously, readings of faulty sensors would be corrected during this process. Simulation results demonstrate that the DFWD has a higher fault detection accuracy compared with other algorithms, and when the sensor fault probability is 10%, the DFWD can still correct more than 91% faulty sensor nodes, which significantly improves the performance of the whole sensor network.     

多基地雷达传感器栅栏覆盖矩形区域的优化方法

为解决栅栏覆盖中多基地雷达传感器的优化布站问题,提出了一种基于最小化部署费用的优化布站方法。首先，针对多基地雷达覆盖区域的特点,通过理论证明提出了多基地雷达传感器栅栏覆盖的优化布站模式。接着，考虑到多基地雷达中发射器与接收器的费用差异,提出一种基于等分覆盖宽度的对称布站策略。然后，为求解优化布站问题,利用栅栏单位面积费用的特点降低算法计算量,进而确定最小布站费用以及对应的布站模式与数量。最后,通过仿真实验证明了所提优化布站方法的有效性。     

多基地雷达传感器栅栏覆盖矩形区域的优化方法

为解决栅栏覆盖中多基地雷达传感器的优化布站问题,提出了一种基于最小化部署费用的优化布站方法。首先，针对多基地雷达覆盖区域的特点,通过理论证明提出了多基地雷达传感器栅栏覆盖的优化布站模式。接着，考虑到多基地雷达中发射器与接收器的费用差异,提出一种基于等分覆盖宽度的对称布站策略。然后，为求解优化布站问题,利用栅栏单位面积费用的特点降低算法计算量,进而确定最小布站费用以及对应的布站模式与数量。最后,通过仿真实验证明了所提优化布站方法的有效性。