一种战术网的分群算法及管理

利用最大连接度分群算法进行群首选举,并进行网关的确定,然后对形成的分群结构进行适当有效的管理.对群的管理主要通过对节点的管理实现,并在统计通信流量的基础上限制对群本身的过度操作,避免了群结构的频繁变动,使网络在保证通信质量的同时具有一定稳定性.本文意义在于提出了一种分群算法及其群的管理,是研究战术网路由协议的前提,作为相关研究工作的参考.     

一种基于最大连通度的双簇头分簇算法

针对最大连通度算法簇头节点负载过重,各簇头间负载极不均衡的问题,提出一种双簇头分簇算法。该算法根据节点度和剩余能量优化簇头选取,提高了网络体系的稳定性。同时剩余能量最大的网关节点作为另一簇头分担一部分节点,即保持了原算法分组投递时延少的优点,又减轻了负载过重簇头节点的负担。通过仿真试验验证,新算法显著延长了网络生命周期。     

基于图论聚合度的动态分层路由算法

讨论无线传感器网络簇的组成问题及其形式化描述,提出节点聚合度的概念并引入簇首的生成过程,给出一种新的优化路由算法。对算法的设计思想和工作过程,包括簇首的选举与簇建立、簇重组与自愈机制进行了分析与讨论。仿真结果显示,与传统的随机簇首生成算法和最小ID算法相比,该算法降低了簇内节点的重叠度,均衡了网络节点的能量消耗,延长了网络的生存时间。     

基于最大连通度分簇的负载均衡分簇算法

无线传感器网络中由最大连通度生成簇算法得到的簇结构,簇头节点往往负载过重,并且各簇头节点间负载极不均衡,这种不均衡性在传感器节点分布不均匀的场合尤为突出.针对上述问题,提出一种改进的负载均衡分簇算法.通过网关节点调整所属簇使簇间负载趋向均衡,并在调整后将负载依然较大的簇进行分裂,使分簇的逻辑结构适应节点拓扑分布,更加合理.通过仿真实验验证,改进算法在降低和均衡簇头节,占、负载方面比传统的最大连通度分簇算法有明显的提高.     

优化聚类分簇结合自适应中继策略的双簇首WSNs路由算法

针对无线传感器网络中分簇路由算法节点能量利用率低、能量消耗不均匀等问题,提出了一种优化聚类分簇结合自适应中继策略的双簇首无线传感器网络路由算法.该算法对分簇路由协议中的三个阶段分别进行优化设计.成簇阶段,首先对双簇首模型下最优成簇规模与网络能耗的关系进行理论分析,然后使用改进的算术优化算法计算模糊C均值算法的初始聚类中心,提高了模糊C均值算法聚类成簇的准确率和鲁棒性.簇首选举阶段,引入双簇首策略,以节点的位置、能量和中心度为影响因子,根据承担任务的不同分别为内外簇首设计独立的簇首评价函数,以评价值为依据由节点分布式动态选举簇首减少了广播数量,同时可以将整个簇的能量负载平均分配到每个簇成员节点中.数据传输阶段,设置了多跳中继策略的距离适用条件,并以能量消耗速率为依据选择中继节点,避免了节点提前过载.仿真结果表明：在多种规模的网络中,该算法相较于对比算法在均衡网络负载、提高能量利用效率方面效果更好,从而延长了网络的有效感测时间.     

基于聚合度的WSN分簇优化算法研究

针对无线传感器网络分簇问题,引入节点聚合度概念,以节点能量的均衡消耗为目标,提出一种有效簇头数优化方法,并设计出均衡网络负载的簇首动态更新和簇重组机制,进一步地优化分簇。算法包括基于能量消耗的有效簇头数计算,聚合度最大的簇首选举和簇建立,以及均衡网络负载的簇首动态更新和簇重组。仿真结果表明,算法能有效延长网络寿命,均衡网络消耗。     

基于HD分簇算法的仿真设计

针对最大连接度分簇算法的几个缺点,在成簇阶段引入新的簇分裂方案以及合并方案,采用样本统计地方法验证了分裂方案的收敛性;在簇维护阶段,运用加权的思想,根据场景不同,动态调整权重值,选举符合要求的节点作为备选簇首.根据上述改进,设计了一种新的分簇算法.仿真实验结果表明,新算法在网络拓扑稳定性及生命周期方面具有优势.     

一种能量均衡的WSN多级分簇路由算法

通过分析无线传感器网络分簇路由协议中簇首选择不合理和网络负载不均衡的问题,提出一种能耗均衡的多级分簇算法,簇首通过分析已学习到的周围网络数据作出较优决策。在簇首选举方面,综合考虑了节点剩余能量和相对节点密度,选择出合适的簇首;路由方面,运用贪婪算法选择较优簇内通信方案,为簇间数据转发预留能量;簇首对死亡节点能及时发现和广播死亡信息,更好地维护网络运行。仿真和分析结果表明,该算法能选出更为合理的簇首,更有效地均衡了网络负载,显著延长了网络寿命。     

能量负载均衡的无线传感网分组成簇协议

针对无线传感网（WSN）中分簇路由协议在簇首分布及节点能耗不均问题,提出了一种节点能量负载均衡的分组成簇算法。根据节点能量分组,并随着节点能量的减少动态调整分组个数,组内根据能量重心进行簇首选举,利用簇首轮转和簇间多跳路由进一步均衡节点能耗。仿真结果表明,该算法有效实现了负载均衡,并显著延长了网络的稳定期。     

一种可控簇规模的能耗均衡路由协议的设计

无线传感器网络路由研究的主要难点在于节点负载不均衡,容易导致某些节点能量提前耗尽,从而使得传感器网络过早死亡.针对这一难点,本文提出了一种可控簇规模的能量均衡路由协议(CCERP).该协议综合考虑节点的剩余能量、节点与邻居节点的链路质量、节点的度选择簇首节点,然后根据节点距离Sink节点的最短跳数控制簇首竞争半径,从而控制簇规模,接着利用虚拟力模型进行普通节点成簇,最后簇首通过多跳路由将采集的数据发送至Sink节点.该协议在簇首选举、簇规模控制和簇首间路由都充分考虑了负载均衡,实验结果验证了该协议具有较好的能耗均衡性.     

基于代理群的网络管理中群首选举算法的研究

基于代理群的网络管理是一种动态的分布式管理模式,群首在代理群中是最关键的节点,群首的选举则是动态群管理中的最关键问题之一。针对选举问题,本文在建立的部分同步系统模型基础上,提出了一种三段式的群首选举算法,该算法具有较高的效率和一定的容错能力;同时应用故障检测器相关理论解决了选举的触发问题,并对相关参数的确定进行了讨论。     

A note on leader election in directed split-stars and directed alternating group graphs

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.     

Leader election for anonymous asynchronous agents in arbitrary networks

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done.     

Leader election problem on networks in which processor identitynumbers are not distinct

In the networks considered in this paper, processors do not have distinct identity numbers. On such a network, we discuss the leader election problem and the problem of counting the number of processors having the same identity number. As the communication mode, we consider port-to-port, broadcast-to-port, port-to-mail box, and broadcast-to-mailbox. For each of the above communication modes, we present: an algorithm for counting the number of processors with the same identity number; an algorithm for solving the leader election problem; and a graph theoretical characterization of the solvable class for the leader election problem     

分层Ad Hoc网络中同步领导者选举算法的研究

近年来,Ad Hoc网络以其方便、快捷、不受网络基础设施制约等特点得到了广泛的研究和应用。然而,在分层Ad Hoc网络进行视频信息传输的过程中,由于节点移动及网络状况等原因有可能出现簇头节点缺失的情况,影响网络的正常通信。针对分层Ad Hoc网络中高层节点移动性差这一特点设计并实现了基于分层Ad Hoc网络高层网络同步领导者选举算法,解决了上述问题。系统还引入了副主席机制,并通过实验证明,当网络中存在着上一轮选举后产生的副主席节点时,选举时间将显著缩短。算法也可应用于小型临时视频会议系统中以解决视频会议中主持人缺失及更替的问题。     

A Self-Stabilizing Leader Election Algorithm in Highly Dynamic Ad Hoc Mobile Networks

The classical definition of a self-stabilizing algorithm assumes generally that there are no faults in the system long enough for the algorithm to stabilize. Such an assumption cannot be applied to ad hoc mobile networks characterized by their highly dynamic topology. In this paper, we propose a self-stabilizing leader election algorithm that can tolerate multiple concurrent topological changes. By introducing the time interval-based computations concept, the algorithm ensures that a network partition can within a finite time converge to a legitimate state even if topological changes occur during the convergence time. Our simulation results show that our algorithm can ensure that each node has a leader over 99$\%$ of the time. We also give an upper-bound on the frequency at which network components merge to guarantee the convergence.     

How much memory is needed for leader election

We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state “infeasible” when the election of a unique leader fails, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for both strong and weak leader election in the class of arbitrary connected graphs. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Δ using only O(log log Δ) bits of memory, thus proving an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs.     

Model checking mobile ad hoc networks

Modeling arbitrary connectivity changes within mobile ad hoc networks (MANETs) makes application of automated formal verification challenging. We use constrained labeled transition systems as a semantic model to represent mobility. To model check MANET protocols with respect to the underlying topology and connectivity changes, we introduce a branching-time temporal logic. The path quantifiers are parameterized by multi-hop constraints over topologies, to discriminate the paths over which the temporal behavior should be investigated; the paths that violate the multi-hop constraints are not considered. A model checking algorithm is presented to verify MANETs that allow arbitrary mobility, under the assumption of reliable communication. It is applied to analyze a leader election protocol.     

A Distributed Election Protocol for Unreliable Networks

This paper presents a broadcast-based election protocol for distributed systems implemented on unreliable networks. The protocol is highly robust, tolerating failures such as message loss and network partitioning. Our protocol is different from others in that it effectively detects events that may possibly make the election results inconsistent, aborts the election, and causes the nodes to execute another election round. When the election completes, there is guaranteed to be agreement on a single leader. When the network is partitioned, groups with a consistent view and a single leader are formed in each partition. Compared to other broadcast-based election protocols, which use a group-merging mechanism to fix the problem of several groups independently electing different leaders, the number of election rounds needed to arrive at a single leader is on average considerably fewer.     

Flocking coordination using active leader and local information

In this paper coordination of a group of agents by a coordinator agent, called the leader‐agent (LA), is discussed. Agents have identical finite sensing radii and access only the local information. Inter‐agent interactions bring them together as a multi‐agent network system. In a recently proposed flocking algorithm using a virtual leader, it is proved that if a fraction of agents are informed then the center of mass of the multi‐agent system tracks the virtual leader. The minimum number of the fraction is always greater than one. In this paper the only informed agent is the LA. Interaction functions are defined to make the model of the multi‐agent system suitable for the design of the coordination control algorithm. The leader‐agent accesses its local data and actively plans its motions through a nonlinear control method. It is proven in this paper that the multi‐agent system tracks the virtual leader and a locally defined point near the LA converges to the position of the virtual leader. It is also shown that in this case, center of mass of the multi‐agent system follows the virtual leader but with a finite distance. We have also discussed positive effects of the LA on network connectivity. Finally illustrative examples are added as well. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society