检索结果-内蒙古大学图书馆

localized construction of bounded degree and planar spanner for wireless ad hoc networks

MOBILE NETWORKS & APPLICATIONS 2006年第2期11卷 161-175页

作者： Wang, Yu Li, Xiang-Yang Univ N Carolina Dept Comp Sci Charlotte NC 28223 USA IIT Dept Comp Sci Chicago IL 60616 USA

We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method applies the Yao structure on the local Delatmay graph [1] in an ordering that are computed locally. This new structure has the following attractive properties: (1) it is a planar graph;(2) its node degree is bounded from above by a positive constant 19 + [2 pi/alpha];(3) it is a t-spanner (given any two nodes u and v, there is a path connecting them in the structure such that its length is no more than t <= max{pi/2, pi sin alpha/2 + 1}. C-del times of the shortest path in the unit disk graph);(4) it can be constructed locally and is easy to maintain when the nodes move around;(5) moreover, we show that the total communication cost is O(n log n) bits, where n is the number of wireless nodes, and the computation cost of each node is at most O(d log d), where d is its 2-hop neighbors in the original unit disk graph. Here C-del is the spanning ratio of the Delaunay triangulation, which is at most 4 root 3/9 pi. And the adjustable parameter alpha satisfies 0 < alpha < pi/3.

关键词： wireless ad hoc networks topology control bounded degree planar spanner localized algorithm

来源：评论

学校读者我要写书评

暂无评论

Using β-skeletons for localized topology control in wireless ad hoc networks

Using β-skeletons for localized topology control in wireles...

引用

24th IEEE International Performance, Computing and Communications Conference

作者： Bhardwaj, M Misra, S Xue, GL Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

ISBN: (纸本)0780389913

We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as beta-skeletons. Two efficient algorithms are presented in this paper for creating a connected topology from an underlying beta-skeleton. One algorithm is a localized algorithm that uses two-hop neighborhood information to generate a connected topology, with a running time of O(n). The other is a distributed algorithm that runs on each component of the beta-skeleton creating a connected structure from the disconnected beta-skeleton graph, the running time is O(nlogn). Simulations show consistent decrease in node degree in the resulting topology. The observed decrease is greater than 33% in comparison to the Relative Neighborhod Graph (RNG) and greater than 50% in comparison to other topology structures such as, the Gabriel Graph (GG) and the Yao construction on GG.

关键词： wireless ad hoc networks topology control bounded degree localized algorithm topolog control structure distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

3-D localized position-based routing with nearly certain delivery in mobile ad hoc networks

3-D localized position-based routing with nearly certain del...

引用

2nd International Symposium on Wireless Pervasive Computing

作者： Kao, George Fevens, Thomas Opatrny, Jaroslav Concordia Univ Dept Comp Sci & Software Engn 1455 Maisonneuve Blvd W Montreal PQ H3G 1M8 Canada

ISBN: (纸本)9781424405220

We present a novel 3-D routing algorithm, Adaptive Least-Squares Projective FACE routing algorithm, for wireless mobile ad hoc networks. This algorithm is based on three heuristics, least-squares projection (LSP) plane, adaptive behavior scale (ABS) and multi-projection-plane strategy, as well as the algorithm of Projective FACE routing on two orthogonal planes proposed in [5]. The resultant algorithm of Adaptive Least-Squares Projective FACE routing with 16 or more projection planes available gives nearly certain delivery, e.g. a 100% delivery rate shown by our simulations, on the unit disk graph (UDG). We also provide a comparison of performance for routing in 2-D and in 3-D. Two randomized versions, half-space partition and quadrant-space partition, of certain deterministic routing algorithms are also proposed to accommodate randomized routing in 3-D.

关键词： three-dimension position-based routing ad hoc network localized algorithm MANET wireless network routing algorithm

来源：评论

学校读者我要写书评

暂无评论

A Hop Count Based Greedy Face Greedy Routing Protocol on localized Geometric Spanners

A Hop Count Based Greedy Face Greedy Routing Protocol on Loc...

引用

21st International Joint Conference on Artificial Intelligence (IJCAI-09)

作者： Du, Jingzhe Kranakis, Evangelos Nayak, Amiya Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada

ISBN: (纸本)9781424454686

We describe a Fast Delivery Guaranteed Face Routing (FDGF) in ad hoc wireless networks. Since it is expensive for wireless nodes to get the whole network topology information, geometric routing decisions should be made locally by nodes using location information of neighboring nodes which are at most k hops away. In this paper, we first define k-local algorithm and obtain two local geometric graphs, i.e., k-Local Delauany Triangulation Graph (k-LDTG) and k-Local Minimum Weight Spanning Tree (k-LMWST), which are more efficient than existing definitions. We present problems with existing face routing protocols and propose FDGF to counter possible long delivery delay with high probability. The performance of face routing differs on different planar graphs. We compare face routing characteristics of four different underlying routing graphs which include k-LDTG, Gabriel Graph (GG), Relative Neighbor Graph (RNG) and k-LMWST. Due to different attributes of these graphs, the message delivery delay, routing hop and minimum energy consumption differ greatly. Through experimentation in the NS-2 simulator, we have shown that the proposed face routing protocol achieves 100% delivery ratio on Unit Disk Graph (UDG) when source to destination connection path exists. Face routing on k-LDTG is fast with less relay hops and face routing on k-LMWST is energy efficient. RNG achieves desirable minimum energy consumption attribute, better than all the others when the propagation model is free space and close to k-LMWST when the propagation model is Two Ray Ground.

关键词： face routing localized algorithm Delaunay triangulation minimum spanning tree relative neighbor graph Gabriel graph

来源：评论

学校读者我要写书评

暂无评论

Coverage and Exposure Paths in Wireless Sensor Networks

引用

Journal of Computer Science & Technology 2006年第4期21卷 490-495页

作者：黄刘生徐宏力汪炀吴俊敏李虹 Department of Computer Science and Technology University of Science & Technology of China Hefei 230027 P.R. China Anhui Province-Most Co-Key Laboratory of High Performance Computing and Its Application Hefei 230027 P.R. China

Wireless sensor networks have posed a number of challenging problems such as localization, deployment and tracking, etc. One of the interesting problems is the calculation of the coverage and exposure paths for the sensor networks. This paper presents a fully localized algorithm to solve the worst coverage problem first introduced by Meguerdichian et al. The nodes of the sensor network cooperate to construct the worst coverage path only by the one-hop neighbor＇s information, thus avoiding the massive communication and conserving the energy. The correctness of the proposed algorithm is proved formally under the sensing diminishing model. Moreover, this algorithm can be easily extended to solve the minimal exposure problem with local information as well.

关键词： coverage wireless sensor networks localized algorithm exposure

来源：评论

学校读者我要写书评

暂无评论

Energy optimization under informed mobility

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第9期17卷 947-962页

作者： Tang, Chiping McKinley, Philip K. Microsoft Corp Redmond WA 98052 USA Michigan State Univ Dept Comp Sci E Lansing MI 48824 USA

Energy optimization is important in wireless ad hoc networks, where node battery power is usually limited. Research results show that such a network can exploit controlled node mobility to reduce communication-related energy consumption. However, node movement itself usually consumes energy. In this paper we study the energy optimization problem that accounts for energy costs associated with both communication and physical node movement. We refer to this model as informed mobility. We first review the theoretical foundations on how to reduce total communication energy consumption, as well as increase system lifetime, by combining node movement and transmission power adaptation. Next, we describe and analyze the informed mobility optimization problem. Based on this analysis, we introduce localized algorithms and protocols for informed mobility. We propose iMobif, a flow-based informed mobility framework that collects network information for mobility decision making. We demonstrate how to use iMobif to minimize total communication energy consumption as well as to maximize system lifetime. We compare the performance of iMobif to that of systems with no mobility or only cost-unaware mobility. Simulation results show iMobif is effective in reducing energy consumption relative to such systems.

关键词： mobile ad hoc network energy optimization informed mobility localized algorithm routing protocol node position system lifetime

来源：评论

学校读者我要写书评

暂无评论

Carrier Sense Adaptation with Enhanced Fairness in IEEE 802.15.4 WPAN

引用

EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS 2011年第5期22卷 179-184页

作者： Park, Kyung-Joon Jeong, Kwanhee Lim, Hyuk Park, Daeyoung Gwangju Inst Sci & Technol Dept Informat & Commun Kwangju South Korea Gwangju Inst Sci & Technol WCU Dept Nanobio Mat & Elect Kwangju South Korea Seoul Natl Univ Sch Elect Engn & Comp Sci Seoul South Korea Inha Univ Sch Informat & Commun Engn Inchon 402751 South Korea

We propose an adaptive carrier sense ( CS) scheme with enhanced fairness based on an observation that the conventional adaptive CS mechanism may lead to significant unfairness. Our experimental study with an IEEE 802.15.4 WPAN testbed shows that the proposed algorithm significantly improves fairness compared to the conventional mechanism while providing competitive throughput performance. Copyright (C) 2011 John Wiley & Sons, Ltd.

关键词： physical carrier sense 802.15.4 WPAN fairness localized algorithm

来源：评论

学校读者我要写书评

暂无评论

An SPT-based topology control algorithm for wireless ad hoc networks

引用

COMPUTER COMMUNICATIONS 2006年第16期29卷 3092-3103页

作者： Wang, Szu-Chi Wei, David S. L. Kuo, Sy-Yen Natl Taiwan Univ Dept Elect Engn Taipei 10764 Taiwan Fordham Univ Dept Comp & Informat Sci Bronx NY 10458 USA

In this paper, we present a localized Shortest-Path-Tree (SPT) based algorithm that copes with the topology control problem in wireless ad hoc networks. Each mobile node determines its own transmission power based only on its local information. The proposed algorithm first constructs local SPTs from the initial graph, after which the total power consumption is further reduced by allowing each mobile node to search the replaceable links individually. The constructed topology ensures network connectivity, and possesses the following desirable energy-efficient features: (i) the power stretch factor is bounded and can be predetermined, (ii) the power consumption is evenly distributed among the mobile nodes, and (iii) the total power consumption is lower than that obtained by the best known algorithms. The performance improvements of the proposed algorithm are demonstrated through extensive simulations. We conclude our work with a discussion of future research directions toward more integrated mobile network architectures. (c) 2005 Elsevier B.V. All rights reserved.

关键词： ad hoc networks energy efficiency localized algorithm topology control

来源：评论

学校读者我要写书评

暂无评论

Geometric spanners for wireless ad hoc networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2003年第4期14卷 408-421页

作者： Alzoubi, K Li, XY Wang, Y Wan, PJ Frieder, O IIT Dept Comp Sci Chicago IL 60616 USA

We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.

关键词： connected dominating set clustering Delaunay triangulation spanner unit disk graph localized algorithm wireless ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

The r-neighborhood graph:: An adjustable structure for topology control in wireless ad hoc networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2007年第4期18卷 536-549页

作者： Jeng, Andy An-Kai Jan, Rong-Hong Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 300 Taiwan

In wireless ad hoc networks, constructing and maintaining a topology with lower node degrees is usually intended to mitigate excessive traffic load on wireless nodes. However, keeping lower node degrees often prevents nodes from choosing better routes that consume less energy. Therefore, the trade-off is between the node degree and the energy efficiency. In this paper, an adjustable structure, named the r-neighborhood graph, is proposed to control the topology. This structure has the flexibility to be adjusted between the two objectives through a parameter r, 0 <= r <= 1. More explicitly, for any set of n nodes, the maximum node degree and power stretch factor can be bounded from above by some decreasing and increasing functions of r, respectively. Specifically, the bounds can be constants in some ranges of r. Even more, the r-neighborhood graph is a general structure of both RNG and GG, two well-known structures in topology control. Compared with YGk, another famous adjustable structure, our method always results in a connected planar with symmetric edges. To construct this structure, we investigate a localized algorithm, named PLA, which consumes less transmitting power during construction and executes efficiently in O(n log n) time.

关键词： wireless ad hoc networks topology control energy-efficient localized algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：