无线传感器网络中的连通支配集求解算法

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。     

基于连通度的分布式加权多维尺度节点定位算法

研究了迭代优化方法在无线传感器网络节点定位中的应用,针对多维尺度分析定位技术和传统的梯度迭代优化方法,根据数值实验确定了迭代步长和网络连通度之间的函数关系,提出了一种基于连通度的分布式多维尺度分析节点定位算法(a connectivity-based distributed weighted multidimensional scaling algorithm,简称dwMDS(C)).该算法首先根据网络的平均连通度确定迭代步长,然后对每个未知节点的局部代价函数进行优化求解.实验表明该迭代算法收敛快速且稳定,比基于SMACOF算法的dwMDS(G)算法在定位精度上有明显的提高.     

WSN中多重目标覆盖度和连通度的研究

覆盖度和连通度是无线传感器网络中密不可分的关键性研究问题。求解覆盖度和连通度问题的传统方法之一为整数规划算法,其研究背景为同构无线传感器网络和单覆盖度。该方法在实际的高精度目标检测中已不能满足要求。建立了一种随机生成的网络模型并对其进行模型抽象。此外实现了大量的仿真实验,得出了多重覆盖感知概率与节点数量的关系和单连通、重连通的概率曲线,可以为节点的布置提供参考价值。     

OTIS网络的支配集问题算法研究

图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用,计算上它们都属于NP难问题。OTIS网络是一类可以任意图为因子网络的复合网络,它能继承因子网络的良好特性,因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一。研究如何构建OTIS网络的较小支配集和连通支配集。基于OTIS网络构图规则,分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法。从理论上分析了这些算法的性能,并通过实例进行了验证。     

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段.由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期.现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点.提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点.仿真结果表明,新算法能以较小消息开销,有效延长网络寿命.     

带跳数限制的抗毁性网络设计

在网络设计中,为了保证网络服务质量,需要对网络节点间的跳数进行限制.同时网络设计还必须考虑一定的抗毁性要求.提出了使用生成树优化算法来求解某些抗毁性网络设计的难题.生成树优化算法较圆满地解决了既有连通度要求又有跳数限制的抗毁性网络设计问题.该算法不仅具有较强的实际应用价值,也对推动抗毁性网络的研究有十分重要的意义.     

基于改进生成树优化算法的抗毁性网络设计研究

针对当前通信网络抗毁性设计问题,以连通度和跳数作为评价指标,建立了满足指标约束条件且成本开销最小化的网络优化设计模型,并在此基础上提出了改进生成树优化算法求解该模型。仿真结果表明,该算法与生成树优化算法相比,能够更好地权衡各项指标,在确保抗毁性条件下可有效降低成本开销。对于通信网络,特别是大型网络的规划及优化设计,该算法具有实际应用价值和可操作性。     

无线传感器网络中四面体三维质心定位算法

在研究普通三维质心定位算法和APIT-3D定位算法的基础上,提出了一种新无线传感器网络定位算法,即四面体三维质心定位算法。为降低计算复杂度,该算法用三维质心迭代算法代替了APIT-3D定位算法中的网格扫描算法,并在节点分布不均匀和低连通度的情况下,使用RSSI均值加权质心定位算法以提高节点覆盖率。仿真实验表明:该算法在无线传感器网络连通度低或节点分布不均匀时能获得较好的定位精度和定位覆盖率,并且与APIT-3D定位算法相比有效降低了计算复杂度。     

一种基于 PageRank 的微博用户影响度评估算法

微博已成为主流的在线社交网络平台,用户的影响力已成为衡量用户价值的一个重要指标。本文基于PageRank算法,通过分析用户之间的兴趣相似度、相对发帖活跃度、相互反馈互动程度来计算一个用户对其所关注的用户的关注程度,提出一个能够评估用户在微博上实际影响度WeiboRank算法。实验数据分析表明,该算法得到的用户影响度值能较客观地反映用户在其所处的虚拟社交网络中的实际影响度。     

能量优化的无线传感器网络LEACH算法

针对无线传感器网络(WSNs)的经典路由算法LEACH中存在簇头节点选举不合理,导致节点加速死亡、网络寿命缩短的问题,提出了基于能量和连通度的LEACH(LEACH-EC)算法.该算法主要在簇头选举时,同时引入节点的剩余能量和连通度两个因子,采用修改阈值的方法,优化簇头选举,从而避免低能量和低连通度节点担任簇头的可能性.仿真实验结果表明:该算法均衡了整个网络能量消耗的比例,延长了节点和网络的寿命.     

新颖的无线传感器网络组网算法

为有效解决无线传感器网络的网络维护困难性问题,研究性能更好的网络组网算法是一种有效的解决手段．本文给出了无线传感器网络体系结构模型及其连通性定义,在此基础上本文提出了一个具有网络连通性能好的无线传感器网络组网算法并进行了仿真分析,由该算法构成的无线传感器网络不仅具有连通性能好,而且具有保护网络节点能量和控制网络功率的优良特点,所以在传感器网络实际应用中有着光明的前景．     

复杂无向网络连通性的一种高效判定算法

通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往, 各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计, 而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证, 而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题, 本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度, 且便于计算机实现, 因而具有重要的理论意义和广泛的实用价值.     

基于代数连通度的域内节能路由算法

通过节能路由算法减少网络能耗是网络中需要解决的一个关键性的科学问题。如今已有的节能方案都是在已知流量矩阵的前提下研究网络节能,由于实时流量难以获取,使得这些方案都难以在实际中部署。因此,文中提出一种基于代数连通度的域内节能方案(Intra-domain Energy Efficient Routing Scheme Based on Algebraic Connectivity,EERSBAC)。EERSBAC不需要网络中的实时流量矩阵,仅依靠网络中的拓扑结构就可以实现节能。首先,提出链路关键度模型,利用链路关键度模型计算出网络中所有链路的重要程度;然后,提出代数连通度模型,利用代数连通度模型可以定量的衡量网络的连通性能。实验结果表明,EERSBAC不仅能够降低网络能耗,而且具有较小的路径拉伸度。     

一种自适应的基于流言机制的AODV路由算法

多跳的无线连接、动态的网络拓扑和有限的带宽是移动Adhoc网络的主要特点,这些特点对移动Adhoc网络的路由协议提出了诸多挑战。在Adhoc路由算法中使用流言(gossip)机制不仅可以减少路由开销,同时还能提高路由效率和可靠性。文章提出了一种自适应的基于流言机制的AODV路由算法,并将其与原来的基于流言机制的AODV路由算法进行了仿真性能比较。     

一种传感器网络容错拓扑控制算法

基于对局部最小生成树拓扑控制算法的研究,提出了对该算法改进的容错拓扑控制算法。通过广播来收集节点的局部信息构造局部最小生成树,并通过深度优先搜索算法使得任意两节点间至少存在K（K=2,3）条内部节点互不相交的路径,保证网络的K连通和容错特性。仿真结果表明：该算法降低了网络的功耗,提高例了网络的容量,网络的容错性能和生存能力都有了较大的提高。     

Distributed extremum seeking and formation control for nonholonomic mobile network

In this paper, an integrated control and optimization problem is studied in the context of formation and coverage of a cluster of nonholonomic mobile robots. In particular, each communication channel is modeled by its outage probability, and hence, connectivity is maintained if the outage probability is less than a certain threshold. The objective of the communication network is to not only maintain resilient communication quality but also extend the network coverage. An information theory based performance index is defined to quantify this control objective. Unlike most of the existing results, the proposed cooperative control design does not assume the knowledge of any gradient (of the performance index). Rather, a distributed extremum seeking algorithm is designed to optimize the connectivity and coverage of the mobile network. The proposed approach retains all the advantages of cooperative control, and it can not only perform extremum seeking individually, but also ensures a consensus of estimates between any pair of connected systems. Simulation results demonstrate effectiveness of the proposed methodology.     

无线传感器网络中覆盖控制算法研究及改进

通过分析经典的无线传感器网络节点调度算法——CPNSS算法,针对其利用率低、能量不均衡的问题,提出了一种高效节能的无线传感器网络覆盖优化算法(ECPNSS),该算法对中心角计算法进行了扩展改进,提高了冗余节点判定效率,同时考虑了网络的连通性,均衡了网络能量。通过对算法的仿真,验证了ECPNSS算法在保持网络初始覆盖的前提下,极大地提高了冗余节点判定效率,降低了网络冗余。     

Energy-efficient communication in wireless cable sensor networks

In this paper, we introduce a new type of sensor: cable sensor. Unlike traditional point sensors, this type of sensor has a rectangular sensing region with a processor installed on it to do processing and communication. The wireless network formed by this kind of sensor is called wireless cable sensor network (WCSN). We study energy-efficient communication algorithms in WCSNs. We address it in two ways: one is through reducing the total transmission power of processors while maintaining the connectivity of the network and the other is through scheduling cable sensors to let them take turns to go to sleep without affecting the coverage and connectivity of the network. In the first approach, we initially develop a distributed algorithm called DTRNG based on the relative neighbourhood graph. Later we enhance it to Algorithm determine the transmission power by removing the largest edge in CYCles (DTCYC). Mathematical proofs show that Algorithm DTCYC provides an optimal solution that can not only minimise the total processor transmission power but maintain the connectivity of the network as well. In the second approach, we propose a cable mode transition algorithm which determines the minimum number of active sensors to maintain K-coverage as well as K-connectivity required by the application. We discuss the relationship between coverage and connectivity and prove the theorems that lay the foundation for our algorithm. Simulation results demonstrate that our algorithm is efficient in saving energy.     

A connectivity-preserving flocking algorithm for multi-agent systems based only on position measurements

Most existing flocking algorithms rely on information about both relative position and relative velocity among neighbouring agents. In this article, we investigate the flocking problem with only position measurements. We propose a provably-stable flocking algorithm, in which an output vector is produced by distributed filters based on position information alone but not velocity information. Under the assumption that the initial interactive network is connected, the flocking algorithm not only can steer a group of agents to a stable flocking motion, but also can preserve the connectivity of the interactive network during the dynamical evolution. Moreover, we investigate the flocking algorithm with a virtual leader and show that all agents can asymptotically attain a desired velocity even if only one agent in the team has access to the information of the virtual leader. We finally show some numerical simulations to illustrate the theoretical results.