Localized Techniques for Broadcasting in Wireless Sensor Networks

In this paper we tackle the problem of designing simple, localized, low energy consuming, reliable protocols for one-to-all communication in large scale wireless sensor networks. Our first proposed technique, called the Irrigator protocol, relies on the idea to first build a sparse overlay network, and then flood over it. The overlay network is set up by means of a simple, distributed, localized probabilistic protocol and spans all the sensor nodes with high probability. Based on the algorithmic ideas of the Irrigator protocol we then develop a second protocol, dubbed Fireworks, with similar performance that does not require any overlay network to be set up in advance. Asymptotic analytical results are provided which assess the reliability of the Irrigator and Fireworks techniques. The theoretical analysis of the proposed protocols is complemented and validated by a (simulation based) comparative performance evaluation that assesses several advantages of our new protocols with respect to gossiping and simple flooding. Differently from previous studies, we analyze and demonstrate the performance of our protocols for two different node distributions: The typical uniform distribution and a newly defined “hill” distribution, here introduced to capture some of the important and more realistic aspects of node deployment in heterogeneous terrain. Simulation results show that the proposed schemes achieve very good trade-offs between low overhead, low energy consumption and high reliability. In particular, the Irrigator and Fireworks protocols are more reliable than gossiping, and significantly reduce the number of links along which a message is sent over both flooding and gossiping.     

无线移动自组织网络中的定向广播算法

在无线自组织网络(MANET)中,收集可靠的全局拓扑信息是不可行的。因此,在网络拓扑信息未知的前提下,广播成为Ad Hoc网络必不可少的通信方式。然而,由于无线信号在同一区域内很可能会重叠,直接用洪泛法进行广播将孚致分组的过多转发、信道竞争和冲突,即广播风暴问题。为解决这个问题,现阶段提出的许多路由协议要么可到达性低,要么计算开销量大。本文提出了．一种新型广播算法;定向广播算法,该算法减少了．重传,获得了．较高的可到达性,具有较低的能量和带宽消耗性能。     

The Minimum Range Assignment Problem on Linear Radio Networks

Abstract. Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN ASSIGNMENT problem consists in finding a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem are only known when h=|S|-1 or in the uniform chain case (i.e., when the stations are equally spaced). As for the first case, Kirousis et al. [7] provided a polynomial-time algorithm while, for the second case, they derive a polynomial-time approximation algorithm. This paper presents the first polynomial-time, approximation algorithm for the MIN ASSIGNMENT problem. The algorithm guarantees a 2-approximation ratio and runs in O(hn ³ ) time. We also prove that, for fixed h and for ``well spaced' instances (a broad generalization of the uniform chain case), the problem admits a polynomial-time approximation scheme . This result significantly improves over the approximability result given by Kirousis {et al}. Both our approximation results are obtained via new algorithms that exactly solve two natural variants of the MIN ASSIGNMENT problem: the problem in which every station must reach a fixed one in at most h hops and the problem in which the goal is to select a subset of bases such that all the other stations must reach one base in at most h-1 hops. Finally, we show that for h=2 the MIN ASSIGNMENT problem can be exactly solved in O(n ³ ) time.     

高效的分布式最小连通支配集近似算法

在Alzoubi and Wan’s算法的基础上,利用2跳局部网络拓扑信息选择连通点,提出一个高效的分布式最小连通支配集算法EDMCDS。理论分析表明,EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2,时间复杂度为 ,信息复杂度为 。与TFA和Alzoubi and Wan’s算法相比,该算法生成的连通支配集更小,时间复杂度和信息复杂度也有所降低。     

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。     

移动Ad hoc网络中基于拓扑控制的节能算法

如何降低节点能耗,延长节点生存时间是移动Ad hoc网络的一个研究热点,对此提出了一种基于拓扑控制的节能算法ECA/TC（Energy Conservation Algorithm with Topology Control）。该算法在RNG图的基础上,采用邻节点消除机制,有效降低了节点的传输功率及广播消息在网络中的转发次数。仿真结果显示该算法具有较好性能,能够提高网络能效。     

移动模型对Ad hoc网络路由协议能耗的影响

Ad hoc网络节点能量受限的路由协议的研究是目前的一个热点,IETF的MANET小组提出的几种经典的路由协议,属于最短路由,即最小跳数路由,没有考虑能量因素。由于Ad hoc网络中的节点是由电池供电,整个网络是一个能量受限系统,如何节省节点的能量,尽可能延长网络的可操控时间成为衡量路由协议性能的重要指标。目前针对这几种路由协议基于节点能量约束的评估很少。基于移动模型,该文以能量消耗程度为指标,对Ad hoc 4种典型的路由协议在不同的运动场景下进行了比较系统的仿真研究,得出了一些有益的结论,为进一步研究基于能耗的Ad hoc网络路由协议提供一些参考。     

移动Ad Hoc网络跨层能量保护的系统构架

移动 Ad Hoc网络作为没有基础设施的网络 ,在军事和民用方面具有广阔的应用前景 .由于移动 Ad Hoc网络的大多数节点是由有限寿命的电池来提供的 ,因此能量保护策略成为该网络所有协议层的关键问题 .结合跨层设计思想给出了一种基于跨层协同的能量保护构架     

Energy efficient multicast routing in ad hoc wireless networks

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. Each node in the network is assumed to have a fixed level of transmission power. The problem of our concern is: given an ad hoc wireless network and a multicast request, how to find a multicast tree such that the total energy cost of the multicast tree is minimized. We first prove this problem is NP-hard and it is unlikely to have an approximation algorithm with a constant performance ratio of the number of nodes in the network. We then propose an algorithm based on the directed Steiner tree method that has a theoretically guaranteed approximation performance ratio. We also propose two efficient heuristics, node-join-tree (NJT) and tree-join-tree (TJT) algorithms. The NJT algorithm can be easily implemented in a distributed fashion. Extensive simulations have been conducted to compare with other methods and the results have shown significant improvement on energy efficiency of the proposed algorithms.     

无线自组网的拓扑控制策略研究进展

拓扑控制是无线自组网中最重要的技术之一,主要用来降低能量消耗和无线干扰,其目标是在降低能量消耗和无线干扰的前提下,控制网络节点间的通信串路和节点的传输范围,以提高全网的生命周期和效率,如连通性和对称性等。本文首先介绍了拓扑控制模型;然后给出了拓扑控制策略的分类,回顾了无线自组网拓扑控制策略的研究进展,并对有关策略进行了分析;最后给出了该领域的一些研究方向。     

Opportunistic resource utilization networks—A new paradigm for specialized ad hoc networks

We present opportunistic resource utilization networks or oppnets, a novel paradigm of specialized ad hoc networks. We believe that applications can benefit from using specialized ad hoc networks that provide a natural basis for them, the basis more efficient and effective than what general-purpose ad hoc networks can offer. Oppnets constitute the subcategory of ad hoc networks where diverse systems, not employed originally as nodes of an oppnet, join it dynamically in order to perform certain tasks they have been called to participate in. Oppnets have a significant potential to improve a variety of applications, and to create new application niches. We categorize opportunistic networks currently known in the literature as class 1opportunistic networks that use opportunistically only communication resources, and class 2opportunistic networks or oppnets that use opportunistically all kinds of resources, including not only communication but also computation, sensing, actuation, storage, etc. After describing the oppnets and the basics of their operation, we discuss the Oppnet Virtual Machine (OVM)—a proposed standard implementation framework for oppnet applications. It is followed by a discussion of an example application scenario using the OVM primitives. Next, we discuss the design and operations of a small-scale oppnet, named MicroOppnet, originally developed as a proof of concept. MicroOppnet is now being extended to serve as a testbed for experimentation and pilot implementations of oppnet architectures and their components. We conclude with a summary and a list of some open issues for oppnets.     

Repetition-based cooperative broadcasting for vehicular ad-hoc networks

In vehicular ad hoc networks, most of critical applications involved with safety rely on reliable broadcast communications with low latency. Recently, repetition-based protocols have been proposed to meet the requirements of timeliness and reliability for broadcasting. In these protocols, a sender repeatedly retransmits the broadcast message during the lifetime of the message. However, existing protocols face serious problems such as deterioration of the signal quality caused by wireless fading. In particular, since excessive repetitions might cause network congestion and waste channel resources, reliability of broadcasting should be achieved with as small a number of repetitions as possible. In this paper, we therefore propose a novel repetition-based broadcast protocol which exploits a cooperative diversity technique (called RB-CD) making a small number of repetitions robust for wireless fading. To support this cooperative diversity, neighboring nodes transmit the same message almost simultaneously (that is, using the same repetition pattern for each other) in order to form a virtual antenna array. The virtual antenna array achieves a diversity gain at the receivers. In the RB-CD protocol, the virtual antenna array consists of the source and some of its neighbors (called relays) which participate in repeating the transmission of a broadcast message. In addition, a new distributed relay selection algorithm is introduced in the RB-CD protocol. From the ns-2 simulation results, we verified that RB-CD provides a more reliable broadcasting service due to its capability of exploiting cooperative diversity.     

自适应波束天线自组网拓扑控制算法

定向天线能显著提高无线系统的性能和容量,但采用定向天线的自组网拓扑构建问题比全向天线网络复杂。拓扑控制是一种保证网络连通和性能优化的有效手段。基于自适应波束定向天线模型提出一种拓扑控制算法,确定天线的主波束朝向,调整节点的发射功率构建拓扑。算法在保证网络连通的基础上,利用主波束的高增益,降低了节点的发射功率,从而降低节点能耗;同时利用定向天线方向性强的特点,减少了节点间干扰,提高了网络吞吐量。仿真结果表明,算法显著提高了网络性能。     

一种改进的蓝牙分散网形成算法

当前的蓝牙规范对微微网的形成、调度和路由选择问题进行了规定，而多个微微网组成的分散网只做了简要的描述，没有对分散网的形成问题加以论述，针对这一问题，提出了许多分散网的形成算法，但有些算法没有考虑设备的移动性，本文就设备的移动性问题，对已提出的算法加以改进，改进后的算法提高了系统的性能，节省了有限的系统资源。     

移动Ad hoc网络中路由协议的能耗-性能联合比较

移动Adhoc网络是一种完全由移动主机构成的网络,网络拓扑易变,带宽,能源有限是其的突出特点。因此,高效路由协议的设计是Adhoc网络的基本问题之一。目前提出的各种路由协议各有它们的特点和优点。但是对这些路由协议的评价仅仅局限于单纯的网络性能或者能量消耗。该文在引入一种性能—能耗联合度量的基础上,对常见的DSR、AODV、TORA和DSDV四种路由协议进行了比较和评价。     

An Optimal Algorithm for the Minimum Disc Cover Problem

The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general α-hull problem. In spite of being a special case, the disc cover problem is not easier than the general α-hull problem. In addition to applying the existing α-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the α-hull approach would fail.     

移动Ad hoc网络的一种安全路由协议

移动ad hoc网络的开放、动态、分布式特性对网络安全问题提出了巨大挑战。本文指出了几种典型安全路由协议的缺陷,并提出了一种新的安全路由协议AMDSR。它采用对路由请求消息进行逐跳认证、端-端完整性检查和监听的方法来扩展DSR协议的安全功能,并确保建立最快速的路径。AMDSR监听邻居结点广播的路由消恩而不似传统协议混杂收听所有消息,具有更好的适用性。     

Ad Hoc网络中基于能源节省的单向QoS路由协议

针对阿ad hoc网络中节点能源受限，隐藏终端和QoS需求等问题，提出了一种基于能源节省的单向QoS路由协议。该协议利用网络中存在的单向链路，采用QoS策略，通过在最短路由集中选取能源较多的路径承担较多传输任务以延长网络生存时间。仿真结果表明，该协议比相关路由算法具有更好的网络性能，能有效支持单向ad hoc网络中具有QoS需求的信息传输。