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

13th ACM International Conference on Mobile Computing and Networking

作者： Chen, Ai Kumar, Santosh Lai, Ten H. Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

ISBN: (纸本)9781595936813

Global barrier coverage that requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not always guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called localized Barrier Coverage Protocol (LBCP). We show that LBCP provides close to optimal enhancement in network lifetime, while providing global barrier coverage most of the time. It outperforms an existing algorithm called Randomized Independent Sleeping (RJS) by up to 6 times.

关键词： Wireless sensor networks local barrier coverage coverage network topology localized algorithms

来源：评论

学校读者我要写书评

暂无评论

ANALYSIS OF THREE localized algorithms FOR CONSTRUCTING DOMINATING SETS IN NETWORKS

ANALYSIS OF THREE LOCALIZED ALGORITHMS FOR CONSTRUCTING DOMI...

引用

作者： Mohammed Ali, Kovan A Kent State University

学位级别：master

A dominating set is a set where every vertex is in the set or adjacent to at least one vertex in the set. Dominating sets have enormous number of applications. A connected dominating set that is widely used in wireless ad-hoc networks is one of many applications of dominating set. Due to the significant usage of this field many kinds of algorithms have been proposed to compute a dominating set. These algorithms are divided into two types: centralized and decentralized algorithms. The decentralized algorithms are also divided into two types: distributed and localized. Modern day graphs are large in size, which causes centralized algorithms to become an undesirable choice. Also, all the non-localized distributed algorithms are slow to compute a dominating set in these big graphs. Therefore, all the attention has shifted toward localized algorithms were vertices can communicate with a constant rounds of *** this thesis, we compare three localized algorithms, namely, Maximal Independent Set (MIS, for short) algorithm, One-hop greedy algorithm, and Two-hop greedy algorithm. We use five different artificial graph models and four real world graphs. For each graph, we compared three different metrics, which are dominating set size, number of iterations, and number of dominators for each dominatee. As we expected, the Two-hop greedy algorithm has a better dominating set size and more iterations than the other two algorithms. In some cases, the MIS algorithm would take more iterations than the One-hop algorithm such as in Power Law, Small World, PPI, and DutchElite graphs. The MIS algorithm, applied to unit disk graphs, does not produce any dominatee that has more than five dominators, which is a well-known fact. Advisors/Committee Members: Dragan, Feodor (Advisor)

关键词： Computer Science Dominating Set localized algorithms

来源：评论

学校读者我要写书评

暂无评论

localized and configurable topology control in lossy wireless sensor networks

引用

AD HOC NETWORKS 2013年第4期11卷 1345-1358页

作者： Xing, Guoliang Lu, Chenyang Jia, Xiaohua Pless, Robert Michigan State Univ E Lansing MI 48824 USA Washington Univ St Louis MO 63130 USA City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Wireless sensor networks (WSNs) introduce new challenges to topology control due to the prevalence of lossy links. We propose a new topology control formulation for lossy WSNs. In contrast to previous deterministic models, our formulation captures the stochastic nature of lossy links and quantifies the worst-case path quality in a network. We develop a novel localized scheme called configurable topology control (CTC). The key feature of CTC is its capability of flexibly configuring the topology of a lossy WSN to achieve desired path quality bounds in a localized fashion. Furthermore, CTC can incorporate different control strategies (per-node/per-link) and optimization criteria. Simulations using a realistic radio model of Mica2 motes show that CTC significantly outperforms an representative traditional topology control algorithm called LMST in terms of both communication performance and energy efficiency. Our results demonstrate the importance of incorporating lossy links of WSNs in the design of topology control algorithms. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Lossy sensor networks Topology control Link quality Dilation of transmission count localized algorithms

来源：评论

学校读者我要写书评

暂无评论

localized Geographic Routing to a Mobile Sink with Guaranteed Delivery in Sensor Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2012年第9期30卷 1719-1729页

作者： Li, Xu Yang, Jiulin Nayak, Amiya Stojmenovic, Ivan Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Tsinghua Univ TNList Sch Software Beijing 100084 Peoples R China

We propose a novel localized Integrated Location Service and Routing (ILSR) scheme, based on the geographic routing protocol GFG, for data communications from sensors to a mobile sink in wireless sensor networks. The objective is to enable each sensor to maintain a slow-varying routing next hop to the sink rather than the precise knowledge of quick-varying sink position. In ILSR, sink updates location to neighboring sensors after or before a link breaks and whenever a link creation is observed. Location update relies on flooding, restricted within necessary area, where sensors experience (next hop) change in GFG routing to the sink. Dedicated location update message is additionally routed to selected nodes for prevention of routing failure. Considering both unpredictable and predictable (controllable) sink mobility, we present two versions. We prove that both of them guarantee delivery in a connected network modeled as unit disk graph. ILSR is the first localized protocol that has this property. We further propose to reduce message cost, without jeopardizing this property, by dynamically controlling the level of location update. A few add-on techniques are as well suggested to enhance the algorithm performance. We compare ILSR with an existing competing algorithm through simulation. It is observed that ILSR generates routes close to shortest paths at dramatically lower (90% lower) message cost.

关键词： Geographic routing location service localized algorithms mobile sink wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

localized fault-tolerant topology control in wireless ad hoc networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第4期17卷 307-320页

作者： Li, N Hou, JC Univ Illinois Dept Comp Sci Urbana IL 61801 USA

Topology control algorithms have been proposed to maintain network connectivity while improving energy efficiency and increasing network capacity. However, by reducing the number of links in the network, topology control algorithms actually decrease the degree of routing redundancy. As a result, the derived topology is more susceptible to node failures or departures. In this paper, we resolve this problem by enforcing k-vertex connectivity in the topology construction process. We propose a fully localized algorithm, Fault-tolerant Local Spanning Subgraph ( FLSS), that can preserve k-vertex connectivity and is min-max optimal among all strictly localized algorithms ( i.e., FLSS minimizes the maximum transmission power used in the network, among all strictly localized algorithms that preserve k-vertex connectivity). It can also be proved that FLSS outperforms two other existing localized algorithms in terms of reducing the transmission power. We also discuss how to relax several widely used assumptions in topology control to increase the practical utility of FLSS. Simulation results indicate that, compared with existing distributed/localized fault-tolerant topology control algorithms, FLSS not only has better power-efficiency, but also leads to higher network capacity. Moreover, FLSS is robust with respect to position estimation errors.

关键词： algorithm design and analysis fault tolerance localized algorithms topology control wireless ad hoc networks

来源：评论

学校读者我要写书评

暂无评论

localized broadcasting with guaranteed delivery and bounded transmission redundancy

引用

IEEE TRANSACTIONS ON COMPUTERS 2008年第8期57卷 1072-1086页

作者： Khabbazian, Majid Bhargava, Vijay K. Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

The common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on one round of information exchange. Using the proposed algorithm, each node determines its forwarding status in O(Delta(G) log Delta(G)), where Delta(G) is the maximum node degree of the network. By extending the proposed algorithm, we show that localized broadcast algorithms can achieve both full delivery and a constant approximation ratio to the optimum solution with message complexity O(N), where N is the total number of nodes in the network and each message contains a constant number of bits. We also show how to save bandwidth by reducing the size of piggybacked information. Finally, we relax several system-model assumptions, or replace them with practical ones, in order to improve the practicality of the proposed broadcast algorithm.

关键词： wireless ad hoc networks broadcasting localized algorithms minimum connected dominating set approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Strictly localized Sensor Self-Deployment for Optimal Focused Coverage

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2011年第11期10卷 1520-1533页

作者： Li, Xu Frey, Hannes Santoro, Nicola Stojmenovic, Ivan Univ Waterloo Dept Elect & Comp Engn 200 Univ Ave W Waterloo ON N2L 3G1 Canada Univ Paderborn Elect Engn & Math Dept Fac Comp Sci D-33098 Paderborn Germany Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Univ Novi Sad FTN Dept Elect Energet & Telecommun Novi Sad 21000 Serbia

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, H-polygon and C-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph to surround POI. In GA, nodes greedily proceed as close to POI as they can;in GRG, when their greedy advance is blocked, nodes rotate around POI along locally computed H-or C-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

关键词： Coverage self-deployment localized algorithms mobile sensor networks

来源：评论

学校读者我要写书评

暂无评论

localized sensor area coverage with low communication overhead

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2008年第5期7卷 661-672页

作者： Gallais, Antoine Carle, Jean Simplot-Ryl, David Stojmenovic, Ivan Univ Lille 1 CNRS INRIA Fururs IRCICALIFLPOPS Res GrpUMR 8022 F-59655 Villeneuve Dascq France Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Univ Birmingham Dept Elect Elect & Comp Engn Birmingham B15 2TT W Midlands England

We propose several localized sensor area coverage protocols for heterogeneous sensors, each with arbitrary sensing and transmission radii. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random time out and listens to messages sent by other nodes before the time out expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round and transmit an activity message announcing it. There are four variants in our approach, depending on whether or not withdrawal and retreat messages are transmitted. Covered nodes decide to sleep, with or without transmitting a withdrawal message to inform neighbors about the status. After hearing from more neighbors, active sensors may observe that they became covered and may decide to alter their original decision and transmit a retreat message. Our simulations show a largely reduced message overhead while preserving coverage quality for the ideal MAC/physical layer. Compared to an existing method (based on hello messages followed by retreat ones and where excessive message loss contributed to excessive coverage holes), our approach has shown robustness in a model with collisions and/or a realistic physical layer.

关键词： sensor networks area coverage network connectivity localized algorithms

来源：评论

学校读者我要写书评

暂无评论

localized Distance-Sensitive Service Discovery in Wireless Sensor and Actor Networks

引用

IEEE TRANSACTIONS ON COMPUTERS 2009年第9期58卷 1275-1288页

作者： Li, Xu Santoro, Nicola Stojmenovic, Ivan Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Novi Sad FTN Dept Elect Energet & Telecommun Novi Sad 21000 Serbia

We formalize the distance-sensitive service discovery problem in wireless sensor and actor networks, and propose a novel localized algorithm, iMesh. Unlike existing solutions, iMesh uses no global computation and generates constant per-node storage load. In iMesh, new service providers (i.e., actors) publish their location information in four directions, updating an information mesh. Information propagation for relatively remote services is restricted by a blocking rule, which also updates the mesh structure. Based on an extension rule, nodes along mesh edges may further advertise newly arrived relatively near service by backward distance-limited transmissions, replacing previously closer service location. The final information mesh is a planar structure constituted by the information propagation paths. It stores locations of all the service providers and serves as service directory. Service consumers (i.e., sensors) conduct a lookup process restricted within their home mesh cells to discover nearby services. We analytically study the properties of iMesh including construction cost and distance sensitivity over a static network model. We evaluate its performance in static/dynamic network scenarios through extensive simulation. Simulation results verify our theoretical findings and show that iMesh guarantees nearby (closest) service selection with very high probability, > 99 percent (respectively, > 95 percent).

关键词： Service discovery distance sensitivity localized algorithms sensor networks wireless networks

来源：评论

学校读者我要写书评

暂无评论

localized broadcast incremental power protocol for wireless ad hoc networks

引用

WIRELESS NETWORKS 2008年第3期14卷 309-319页

作者： Ingelrest, Francois Simplot-Ryl, David Univ Lille 1 INRIA IRCICA LIFLCNRSUMR 8022 Futurs France

We investigate broadcasting and energy preservation in ad hoc networks. One of the best known algorithm, the Broadcast Incremental Power (BIP) protocol, constructs an efficient spanning tree rooted at a given node. It offers very good results in terms of energy savings, but its computation is centralized and it is a real problem in ad hoc networks. Distributed versions have been proposed, but they require a huge transmission overhead for information exchange. Other localized protocols have been proposed, but none of them has ever reached the performances of BIP. In this paper, we propose and analyze an incremental localized version of this protocol. In our method, the packet is sent from node to node based on local BIP trees computed by each node in the broadcasting chain. Local trees are constructed within the k-hop neighborhood of nodes, based on information provided by previous nodes, so that a global broadcasting structure is incrementally built as the message is being propagated through the network. Only the source node computes an initially empty tree to initiate the process. Discussion and results are provided where we argue that k = 2 is the best compromise for efficiency. We also discuss potential conflicts that can arise from the incremental process. We finally provide experimental results showing that this new protocol obtains very good results for low densities, and is almost as efficient as BIP for higher densities.

关键词： ad hoc networks broadcasting protocols energy efficiency localized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：