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

A scalable, power-efficient broadcast algorithm for wireless networks

WIRELESS NETWORKS 2006年第4期12卷 495-509页

作者： Li, Ning Hou, Jennifer C. Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Scalability and power-efficiency are two of the most important design challenges in wireless ad hoc networks. In this paper, we present a scalable, power-efficient broadcast algorithm for wireless ad hoc networks. We first investigate the trade-off between (i) reaching more nodes in a single hop using higher transmission power and (ii) reaching fewer nodes using lower transmission power and relaying messages through multiple hops. Our analysis indicates that multi-hop broadcast is more power-efficient if alpha >= 2.2, where alpha is the path loss exponent in the power consumption model P(r,alpha) = c(0) center dot r(alpha) +c(1). Based on the analysis, we then propose Broadcast over Local Spanning Subgraph (BLSS). In BLSS, an underlying topology is first constructed by a localized topology control algorithm, Fault-Tolerant Local Spanning Subgraph (FLSS). FLSS can preserve k-connectivity of the network, where the value of k determines the degree of fault tolerance. Broadcast messages are then simply relayed through the derived topology in a constrained flooding fashion. BLSS is fully localized, scalable, power-efficient, and fault-tolerant. Simulation results show that the performance of BLSS is comparable to that of centralized algorithms.

关键词： fault tolerance localized algorithm power-efficient broadcast wireless ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

Greedy anti-void routing protocol for wireless sensor networks

引用

IEEE COMMUNICATIONS LETTERS 2007年第7期11卷 562-564页

作者： Liu, Wen-Jiunn Feng, Kai-Ten Natl Chiao Tung Univ Dept Commun Engn Hsinchu Taiwan

The unreachability problem (i.e. the so-called void problem) which exists in the greedy routing algorithms has been studied for the wireless sensor networks. However, most of the current research work can not fully resolve the problem (i.e. to ensure the delivery of packets) within their formulation. In this letter, the Greedy Anti-void Routing (GAR) protocol is proposed, which solves the void problem by exploiting the boundary finding technique for the Unit Disk Graph (UDG). The proposed Rolling-ball UDG boundary Traversal (RUT) is employed to completely guarantee the delivery of packets from the source to the destination node. The proofs of correctness for the proposed GAR protocol are also given at the end of this letter.

关键词： greedy routing void problem unit disk graph localized algorithm wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient border intrusion detection using wireless sensors network

引用

EURASIP JOURNAL ON WIRELESS COMMUNICATIONS AND NETWORKING 2014年第1期2014卷 1页

作者： Yang, Tao Mu, Dejun Hu, Wei Zhang, HuiXiang Northwestern Polytech Univ Dept Automat Xian 710072 Peoples R China

Monitoring the illegal movement across national border effectively is a challenging problem. The emerging technology of wireless sensor network (WSN) is expected to provide a new way to realize energy-efficient border intrusion detection. We propose a scheme to measure and guarantee the coverage quality of WSN. We also design a new coverage model for detecting one-direction path. The simulation results shows that the new coverage model could not only detect the intrusion in border area well, but also extend the network lifetime in an efficient way.

关键词： Wireless sensor network Barrier coverage Quality localized algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient construction of low weighted bounded degree planar spanner

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2004年第1-2期14卷 69-84页

作者： Li, XY Wang, Y IIT Dept Comp Sci Chicago IL 60616 USA

Given a set V of n points in a two-dimensional plane, we give an O(n log n)-time centralized algorithm that constructs a planar t-spanner for V, for t = rho(alpha) max{pi/2, pi sin alpha/2 + 1}C-.(del), such that the degree of each node is bounded from above by 19 + [2pi/alpha], where 0 < alpha < pi/2 is an adjustable parameter. Here C-del is the spanning ratio of the Delaunay triangulation, which is at most (4root3)/(9)pi. We also show, by applying the greedy method in Ref. [14], how to construct a low weighted bounded degree planar spanner with spanning ratio rho(alpha)(2)(1 + epsilon) and the same degree bound, where epsilon is any positive real constant. Here, a structure is called low weighted if its total edge length is proportional to the total edge length of the Euclidean minimum spanning tree of V. Moreover, we show that our method can be extended to construct a planar bounded degree spanner for unit disk graphs with the adjustable parameter alpha satisfying 0 < alpha < pi/3. Previously, only centralized method(6) of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t similar or equal to 10.02. The distributed implementation of this centralized method takes O(n(2)) communications in the worst case, Our method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n).

关键词： spanner bounded degree low weight planar localized algorithm

来源：评论

学校读者我要写书评

暂无评论

The expected size of the Rule k dominating set

引用

algorithmICA 2006年第3-4期46卷 409-418页

作者： Hansen, Jennie C. Schmutz, Eric Sheng, Li Heriot Watt Univ Actuarial Math & Stat Dept Edinburgh EH14 4AS Midlothian Scotland Drexel Univ Dept Math Philadelphia PA 19104 USA

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an l(n) x l(n) square. We show that if k >= 3 and l(n) = o(root n), then for both versions of Rule k, the expected size of the Rule k dominating set is a Theta(l(n)(2)) as n > infinity. It follows that, for l(n) in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.

关键词： dominating set localized algorithm approximation algorithm performance analysis probabilistic analysis Rule k unit disk graph

来源：评论

学校读者我要写书评

暂无评论

C-kNN Query Processing in Object Tracking Sensor Networks

引用

3rd International Conference on Wireless algorithms, Systems and Applications

作者： Zhu, Jinghua Li, Jianzhong Luo, Jizhou Zhang, Wei Wang, Hongzhi Harbin Inst Technol Sch Comp Sci & Technol Harbin 150001 Peoples R China

ISBN: (纸本)9783540885818

Wireless sensor networks (WSNs) are being developed for a variety of applications. Continuous k nearest neighbors (C-kNN) query is an essential class of spatial query in object tracking applications. Due to the limited power of individual node, energy is the most critical resource in sensor networks. In order to always report the up-to-date results, a centralized solution requires the transmission of a large number of location update messages. Intuitively, current information is necessary only for objects that may influence some query results. Motivated by this observation. we propose a threshold-based C-kNN search algorithm with the minimal message transmissions. The key idea is to set thresholds for moving objects corresponding to each query so that only the location updates which affect the final results are transmitted. The proposed method can be used with multiple, static or moving queries. The experiments results show the effectiveness and efficiency of our approach in terms of energy and latency.

关键词： Wireless sensor networks Moving object tracking C-kNN query processing localized algorithm

来源：评论

学校读者我要写书评

暂无评论

Reactive Planar Spanner Construction in Wireless Ad Hoc and Sensor Networks

Reactive Planar Spanner Construction in Wireless Ad Hoc and ...

引用

32nd IEEE INFOCOM Conference

作者： Benter, Markus Neumann, Florentin Frey, Hannes Univ Paderborn Heinz Nixdorf Inst Paderborn Germany Univ Paderborn Comp Sci Dept Paderborn Germany Univ Koblenz Landau Inst Comp Sci Berlin Germany

ISBN: (纸本)9781467359467

Within reactive topology control, a node determines its adjacent edges of a network subgraph without prior knowledge of its neighborhood. The goal is to construct a local view on a topology which provides certain desired properties such as planarity. During algorithm execution, a node, in general, is not allowed to determine all its neighbors of the network graph. There are well-known reactive algorithms for computing planar subgraphs. However, the subgraphs obtained do not have constant Euclidean spanning ratio. This means that routing along these subgraphs may result in potentially long detours. So far, it has been unknown if planar spanners can be constructed reactively. In this work, we show that at least under the unit disk network model, this is indeed possible, by proposing an algorithm for reactive construction of the partial Delaunay triangulation, which recently turned out to be a spanner. Furthermore, we show that our algorithm is message-optimal as a node will only exchange messages with nodes that are also neighbors in the spanner. The algorithm's presentation is complemented by a rigorous proof of correctness.

关键词： Reactive topology control Euclidean spanner partial Delaunay triangulation localized algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed Distance Sensitive iMesh Based Service Discovery in Dense WSAN

Distributed Distance Sensitive iMesh Based Service Discovery...

引用

11th International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW)

作者： Lukic, Milan Mezei, Ivan Univ Novi Sad Fac Techhn Sci Novi Sad 21000 Serbia

ISBN: (纸本)9783642316388

We investigated performance of localized distance-sensitive service discovery algorithm iMesh, which generates information structure in static network, to store the information about nearby actors (service providers). In a network with grid structure, this is achieved by advertising service provider positions in four geographical directions. The propagation of information about remote service providers is restricted by a blocking rule, to reduce the message overhead and provide distance sensitivity. A node requiring service (service consumer) conducts lookup process to obtain information about nearby service providers from the iMesh structure. We modified iMesh to enable its use in dense networks with topologies other than grid by introducing iMesh areas instead of iMesh edges. Our simulations compare performance of modified iMesh with another localized service discovery scheme (quorum) in dense networks with random topologies. We show that iMesh finds the nearest service provider in > 95% of cases. It significantly decreases the message overhead compared to quorum, without compromising quality of service discovery.

关键词： service discovery localized algorithm wireless sensor and actor networks iMesh

来源：评论

学校读者我要写书评

暂无评论

Largest Forwarding Region Routing Protocol for Mobile Ad Hoc Networks

Largest Forwarding Region Routing Protocol for Mobile Ad Hoc...

引用

IEEE Global Telecommunications Conference (GLOBECOM 06)

作者： Liu, Wen-Jiunn Feng, Kai-Ten Natl Chiao Tung Univ Dept Commun Engn Hsinchu Taiwan

ISBN: (纸本)9781424403561

The design of routing protocols is crucial for mobile ad-hoc networks due to their fast-changing characteristics. Most of the ad-hoc routing algorithms are designed based on extensive flooding of control packets, which result in excessive overheads within the networks. The greedy routing algorithms employ localized information from the mobile nodes (e. g. relative distance or direction), which induce comparably less control packets in the networks. However, several problems (e. g voids, loops, or dead-ends) are encountered in most of the greedy algorithms due to the localized characteristics. In this paper, a Largest Forwarding Region (LFR) routing protocol is developed. The mobile node with the largest Extended Forwarding Region (EFR) is selected as the next hopping node for packet forwarding. The associated Backward Constraint (BC) and Dead-End Recovery (DER) mechanisms further alleviate the problems resulting from voids in the networks. The performance comparison between the proposed LFR algorithm and other existing greedy routing schemes is conducted via simulations. It is observed that the LFR scheme effectively increases the packet arrival rate without creating excessive control overheads.

关键词： Mobile Ad-Hoc Networks Position-based Routing Greedy Forwarding localized algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed topology control in wireless ad hoc networks using β-skeletons

Distributed topology control in wireless ad hoc networks usi...

引用

IEEE Workshop on High Performance Switching and Routing (HPSR 2005)

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

ISBN: (纸本)0780389247

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 distributed algorithm that runs on each component of the beta-skeleton. It creates a connected structure from the disconnected beta-skeleton graph using a distributed leader election algorithm. The running time of this algorithm is 0 (n log n). The other is a localized algorithm that uses two-hop neighborhood information to generate a connected topology, with a running time of 0(n). 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 distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：