共查询到20条相似文献,搜索用时 484 毫秒
1.
2.
3.
4.
WSNs中基于能量代价的最小权和支配集拓扑控制算法 总被引:1,自引:0,他引:1
该文针对无线传感器网络中最小连通支配集拓扑并非网络耗能最小拓扑的问题,定义由节点剩余能量,邻居个数和通信代价构建的能量代价函数综合反映支配节点的能量效率以及对降低网络整体能耗的贡献,进而以其作为拓扑权值,提出一种基于能量代价的最小权和连通支配集拓扑控制算法。算法选取局部最小权值节点担负支配任务,搭建整体权和最小的支配集,最小化网络整体能耗。实验结果表明,算法不仅具有节能的特点,还确保了通信链路的可靠性,有效延长了网络生命周期。 相似文献
5.
6.
介绍了连通支配集的基本概念,提出了一种改进型分布式连通支配集DRN算法。该算法可在一个节点u的N1(u)不能直接连通、但能通过一个编号比节点u大的节点连通时去除节点u的冗余,因而具有保留编号大的节点的支配集性质,可在不增加支配集节点数和通信开销的基础上,减少支配集节点的尺寸并保证网络的连通性。 相似文献
7.
8.
全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源. 相似文献
9.
10.
基于定向扩散的最小连通支配集构造算法 总被引:1,自引:0,他引:1
针对区域覆盖算法未考虑节点的通信梯度问题,利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列,提出了一种基于定向扩散的最小连通支配集构造算法.在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集,然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来,最终得到一个近似的最小连通支配集.理论及仿真实验结果表明,该算法构造的连通支配集最小且计算耗时少,能多重有效覆盖热点区域,从而延长无线传感器网络的寿命. 相似文献
11.
无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法 总被引:1,自引:0,他引:1
采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期. 相似文献
12.
基于最小连通支配集的无线传感网拓扑构建研究 总被引:1,自引:0,他引:1
基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。 相似文献
13.
In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献
14.
15.
16.
Jaime Llorca Mehdi Kalantari Stuart D. Milner Christopher C. Davis 《Ad hoc Networks》2009,7(3):614-621
The use of directional wireless communications to form flexible mesh backbone networks, which provide broadband connectivity to capacity-limited wireless networks or hosts, promises to circumvent the scalability limitations of traditional homogeneous wireless networks. The main challenge in the design of directional wireless backbone (DWB) networks is to assure backbone network requirements such as coverage and connectivity in a dynamic wireless environment. This paper considers the use of mobility control, as the dynamic reposition of backbone nodes, to provide assured coverage-connectivity in dynamic environments. This paper presents a novel approach to the joint coverage-connectivity optimization problem by formulating it as a quadratic minimization problem. Quadratic cost functions for network coverage and backbone connectivity are defined in terms of the square distance between neighbor nodes, which are related to the actual energy usage of the network system. Our formulation allows the design of self-organized network systems which autonomously achieve energy minimizing configurations driven by local forces exerted on network nodes. The net force on a backbone node is defined as the negative energy gradient at the location of the backbone node. A completely distributed algorithm is presented that allows backbone nodes to adjust their positions based on information about neighbors’ position only. We present initial simulation results that show the effectiveness of our force-based mobility control algorithm to provide network configurations that optimize both network coverage and backbone connectivity in different scenarios. Our algorithm is shown to be adaptive, scalable and self-organized. 相似文献
17.
18.
In this paper, we explore end-to-end loss differentiation algorithms (LDAs) for use with congestion-sensitive video transport protocols for networks with either backbone or last-hop wireless links. As our basic video transport protocol, we use UDP in conjunction with a congestion control mechanism extended with an LDA. For congestion control, we use the TCP-Friendly Rate Control (TFRC) algorithm. We extend TFRC to use an LDA when a connection uses at least one wireless link in the path between the sender and receiver. We then evaluate various LDAs under different wireless network topologies, competing traffic, and fairness scenarios to determine their effectiveness. In addition to evaluating LDAs derived from previous work, we also propose and evaluate a new LDA, ZigZag, and a hybrid LDA, ZBS, that selects among base LDAs depending upon observed network conditions. We evaluate these LDAs via simulation, and find that no single base algorithm performs well across all topologies and competition. However, the hybrid algorithm performs well across topologies and competition, and in some cases exceeds the performance of the best base LDA for a given scenario. All of the LDAs are reasonably fair when competing with TCP, and their fairness among flows using the same LDA depends on the network topology. In general, ZigZag and the hybrid algorithm are the fairest among all LDAs. 相似文献
19.
C.S. Bonaventura K.W. Jablokow 《IEEE transactions on systems, man and cybernetics. Part C, Applications and reviews》2002,32(4):406-415
This paper presents an efficient modular algorithm for the dynamic simulation of robots constrained through a single contact. Such configurations include single robots with closed-loop topologies, as well as, multiple robots with simple series, parallel, and bracing topologies. The modular nature of the algorithm enables the incorporation of existing open-chain models for the individual robots without significant reprogramming, while a general contact model extends the range of possible contact conditions to include both holonomic and nonholonomic constraints. The algorithm is validated through the simulation of two robots cooperating in parallel. This paper establishes an accurate framework for simulating simple robot systems with single contacts, which can be extended to multi-robot, multi-contact systems performing general tasks. 相似文献
20.
Effect of Selfish Node Behavior on Efficient Topology Design 总被引:2,自引:0,他引:2
The problem of topology control is to assign per-node transmission power such that the resulting topology is energy-efficient and satisfies certain global properties such as connectivity. The conventional approach to achieve these objectives is based on the fundamental assumption that nodes are socially responsible. We examine the following question: if nodes behave in a selfish manner, how does it impact the overall connectivity and energy consumption in the resulting topologies? We pose the above problem as a non-cooperative game and use game-theoretic analysis to address it. We study Nash equilibrium properties of the topology control game and evaluate the efficiency of the induced topology when nodes employ a greedy best response algorithm. We show that even when the nodes have complete information about the network, the steady state topologies are suboptimal. We propose a modified algorithm based on a better response dynamic and show that this algorithm is guaranteed to converge to energy-efficient and connected topologies. Moreover, the node transmit power levels are more evenly distributed and the network performance is comparable to that obtained from centralized algorithms. 相似文献