Uniform leader election protocols for radio networks

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f∈e^O(n), in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+Ω(√f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice     

Research on multicast routing protocols for mobile ad-hoc networks

A mobile ad-hoc network (MANET) is composed of mobile nodes without any infrastructure. Mobile nodes self-organize to form a network over radio links. The goal of MANETs is to extend mobility into the realm of autonomous, mobile and wireless domains, where a set of nodes form the network routing infrastructure in an ad-hoc fashion. The majority of applications of MANETs are in areas where rapid deployment and dynamic reconfiguration are necessary and wired network is not available. These include military battlefields, emergency search, rescue sites, classrooms and conventions, where participants share information dynamically using their mobile devices. These applications lend themselves well to multicast operations. In addition, within a wireless medium, it is crucial to reduce the transmission overhead and power consumption. Multicasting can improve the efficiency of the wireless link when sending multiple copies of messages by exploiting the inherent broadcast property of wireless transmission. Hence, reliable multicast routing plays a significant role in MANETs. However, to offer effective and reliable multicast routing is difficult and challenging. In recent years, various multicast routing protocols have been proposed for MANETs. These protocols have distinguishing features and employ different recovery mechanisms. To provide a comprehensive understanding of these multicast routing protocols and better organize existing ideas and work to facilitate multicast routing design for MANETs, we present the taxonomy of the multicast routing protocols, their properties and design features. This paper aims to aid those MANETs researchers and application developers in selecting appropriate multicast routing protocols for their work.     

Survey of multipath routing protocols for mobile ad hoc networks

This survey investigates multipath routing protocols for mobile ad hoc networks (MANETs). The main objectives of multipath routing protocols are to provide reliable communication and to ensure load balancing as well as to improve quality of service (QoS) of MANETs. These multipath protocols are broadly classified into five categories based on their major goals. The goals are to improve delay, provide reliability, reduce overhead, maximize network life and support hybrid routing. Multipath routing protocols address issues such as multiple paths discovery and maintaining these paths. Issues, objectives, performances, advantages and disadvantages of these protocols are investigated and summarized. A checklist is provided as a guideline so that a network designer can choose an appropriate multipath routing protocol to meet the network's application objectives.     

An analysis on decentralized adaptive MAC protocols for cognitive radio networks

The scarcity of bandwidth in the radio spectrum has become more vital since the demand for more and more wireless applications has increased. Most of the spectrum bands have been allocated although many studies have shown that these bands are significantly underutilized most of the time. The problem of unavailability of spectrum and inefficiency in its utilization has been smartly addressed by the cognitive radio (CR) technology which is an opportunistic network that senses the environment, observes the network changes, and then uses knowledge gained from the prior interaction with the network to make intelligent decisions by dynamically adapting their transmission characteristics. In this paper, some of the decentralized adaptive medium access control (MAC) protocols for CR networks have been critically analyzed, and a novel adaptive MAC protocol for CR networks, decentralized non-global MAC (DNG-MAC), has been proposed. The results show the DNG-MAC outperforms other CR-MAC protocols in terms of time and energy efficiency.     

Bandwidth-based routing protocols in mobile ad hoc networks

In this paper, we propose a high performance routing protocol and a long lifetime routing protocol by considering the fact that the bandwidth between two mobile nodes should be different when distances are different. In the high performance routing protocol, to reduce the number of rerouting times, we take the bandwidth issue into account to choose the path with the capability to transmit the maximum amount of data with the help of the GPS. With exchanging the moving vectors and the coordinates of two adjacent mobile nodes, the possible link lifetime of two adjacent mobile nodes can be predicted. Subsequently, a path with the maximal amount of data transmission can be found. With regard to our proposed long lifetime routing protocol, to maximize the overall network lifetime, we find a path with the maximal remaining power after data transmission. With the link bandwidth and the desired amount of data transmitted, the consumption power is computed to obtain the remaining power of a mobile node. Accordingly, we can choose the path with the maximal predicted remaining power to maximize the overall network lifetime. In the simulation, we compare our high performance routing protocol with the AODV and LAWS in terms of throughput, rerouting (path breakage), and route lifetime. With respect to power consumption, we compare our proposed power-aware routing protocol with the POAD and PAMP in terms of the overall network lifetime and the ration of survival nodes to the all nodes.     

移动Ad hoc网络多径路由协议*

给出移动Ad hoc网络多径路由的分类方法,系统地描述了当前各种典型的MANETs多径路由协议,并比较和分析了这些协议的特点及适用情况.最后结合该领域当前的研究现状,指出多径路由协议存在的问题和未来的研究重点.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Search: A routing protocol for mobile cognitive radio ad-hoc networks

Recent research in the emerging field of cognitive radio (CR) has mainly focussed on spectrum sensing and sharing, that allow an opportunistic use of the vacant portions of the licensed frequency bands by the CR users. Efficiently leveraging this node level channel information in order to provide timely end-to-end delivery over the network is a key concern for CR based routing protocols. In addition, the primary users (PUs) of the licensed band affect the channels to varying extents, depending on the proportion of the transmission power that gets leaked into the adjacent channels. This also affects the geographical region, in which, the channel is rendered unusable for the CR users. In this paper, a geographic forwarding based SpEctrum Aware Routing protocol for Cognitive ad-Hoc networks (SEARCH), is proposed that (i) jointly undertakes path and channel selection to avoid regions of PU activity during route formation, (ii) adapts to the newly discovered and lost spectrum opportunity during route operation, and (iii) considers various cases of node mobility in a distributed environment by predictive Kalman filtering. Specifically, the optimal paths found by geographic forwarding on each channel are combined at the destination with an aim to minimize the hop count. By binding the route to regions found free of PU activity, rather than particular CR users, the effect of the PU activity is mitigated. To the best of our knowledge, SEARCH takes the first steps towards a completely decentralized, CR routing protocol for mobile ad-hoc networks and our approach is thoroughly evaluated through analytical formulations and simulation study.     

认知无线电网络组播路由算法和协议综述

认知无线电网络（CRN）在实现更好的无线带宽利用率和提高无线应用质量方面发挥着至关重要的作用。由于认知用户可用频谱机会的动态特性,认知无线电网络中的组播是一个具有挑战性的问题。研究者们已经提出了多种在认知无线电网络中进行有效组播的方案,包括基于优化理论、网络编码、机器学习、博弈论的方案等。总结了解决组播问题有效的算法和技术,并对已有的无线电网络中的组播协议进行了全面的综述,最后给出了未来的研究方向。     

Dynamic radio resource allocation for 3G and beyond mobile wireless networks

Next generation of wireless cellular networks aim at supporting a diverse range of multimedia services to mobile users with guaranteed quality of service (QoS). Resource allocation and call admission control (CAC) are key management functions in future 3G and 4G cellular networks, in order to provide multimedia applications to mobile users with QoS guarantees and efficient resource utilization. There are two main strategies for radio resource allocations in cellular wireless networks known as complete partitioning (CP) and complete sharing (CS). In this paper, theses strategies are extended for operation in 3G and beyond network. First, two CS-based call admission controls, referred to herein as queuing priority call admission control (QP-CAC) and hybrid priority call admission control (HP-CAC), and one CP-based call admission control referred to as complete partitioning call admission control (CP-CAC) are presented. Then, this study proposes a novel dynamic procedure, referred to as the dynamic prioritized uplink call admission control (DP-CAC) designed to overcome the shortcomings of CS and CP-based CACs. Results indicate the superiority of DP-CAC as it is able to achieve a better balance between system utilization, revenue, and quality of service provisioning. CS-based algorithms achieve the best system utilization and revenue at the expense of serious unfairness for the traffic classes with diverse QoS requirements. DP-CAC manages to attain equal system utilization and revenue to CS-based algorithms without the drawbacks in terms of fairness and service differentiation.     

支持发射功率控制的多信道自组网MAC协议

无线自组网的介质访问控制(MAC)协议是与物理层密切相关的,大多数MAC协议都要求物理层具备载波感知能力.但在一些以小型手持设备为终端的自组网应用系统中物理层无法提供载波感知.为此,在MACA和DCA-PC的基础上,提出了一种不需要载波感知的支持功率控制的自组网多信道MAC协议,通过调整发射功率实现节能,并在一定程度上支持实时传输.     

Searching for a black hole in arbitrary networks: optimal mobile agents protocols

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ(n ²), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n ²); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.A preliminary version of this paper appeared in the Proceedings of the 21st ACM Symposium on Principles of Distributed Computing [21].     

A detailed review of energy-efficient medium access control protocols for mobile sensor networks

This article reviews the state-of-the-art energy-efficient contention-based and scheduled-based medium access control (MAC) protocols for mobile sensor networks (MSNs) by first examining access schemes for wireless sensor networks (WSNs). Efficient and proper mobility handling in sensor networks provides a window of opportunity for new applications. Protocols, such as S-MAC, reduce energy consumption by putting nodes to sleep after losing to channel contention or to prevent idling. Sleeping is a common method for energy-efficient MAC protocols, but delay depends on sleep duration or frame time, and longer delays lead to higher packet lost rate when nodes are unsynchronized due to network mobility. MS-MAC extends S-MAC to include mobility-awareness by decreasing this sleep duration when mobility is detected. S-MAC with extended Kalman filter (EKF) reduces mobility-incurred losses by predicting the optimal data frame size for each transmission. MMAC utilizes a dynamic mobility-adaptive frame time to enhance TRAMA, a scheduled-based protocol, with mobility prediction. Likewise, G-MAC utilizes TDMA for cluster-based WSNs by combining the advantages of contention and contention-free MACs. Z-MAC also combines both methods but without clustering and allows time slot re-assignments during significant topology changes. All of the above MAC protocols are reviewed in detail.     

Erratum to: An analysis on decentralized adaptive MAC protocols for cognitive radio networks

正Erratum to:International Journal of Automation and Computing DOI:10.1007/s11633-013-0695-z The original version of this article unfortunately contained a mistake.The received date and revised date were incorrect.The corrected received date and revised date are given below.     

Adaptive radio resource management for interactive user-centric IPTV services in mobile WiMAX networks

Interactive Internet Protocol Television (IPTV), a user-centric service, uses bidirectional transmissions to facilitate viewer requests for accessing various services, a feature applied within a multicast environment. This paper proposes a joint multi-guard band-based call admission policy and dynamic resource reservation management (DRRM) mechanism for radio resource management in mobile WiMAX networks. Distinguishing features of the proposed method are that it takes into account the delivery requirement of interactive IPTV services, admits calls by simultaneously considering uplink and downlink capacities, and adaptively adjusts the thresholds based on the influence curve of mobility to predict the handoff probability. Specifically, through simulations of the outage probability, the impact of the lack of required two-way bandwidth is studied.     

Performance study of multiple route dynamic source routing protocols for mobile ad hoc networks

Design and analysis of routing protocols are the key issues for a mobile ad hoc network (MANET). The Dynamic Source Routing (DSR) protocol is one of the important on-demand routing protocols. In this paper, we develop a comprehensive analytic model for the performance study of the DSR protocol with multiple routes. Two performance metrics, called probability of a successful data transmission and probability that the multiple routes can support the next data transmission, are introduced. We derive both of the two probabilities for the general case over n multiple routes for the DSR protocol. These analytic results provide insights into the mechanics of the multiple DSR routing protocol. It is also useful for the design and implementation of the on-demand routing for MANET.     

机会网络路由协议

在机会网络中由于网络稀疏、节点移动和通信范围等因素的影响,有可能出现网络分裂或节点脱网,源节点和目的节点之间不一定存在完整的端到端路径,这为路由协议的设计带来巨大挑战,此问题近年来引起了研究人员越来越多的关注。首先介绍了机会网络的基本概念、体系结构和特点等;然后阐述了机会网络路由协议研究的进展,概括了机会网络路由协议中的新机制,对现有路由协议进行分类并详述它们的基本原理;通过比较对各种协议的特点进行分析阐述,最后给出未来研究的方向。     

A survey on event-driven and query-driven hierarchical routing protocols for mobile sink-based wireless sensor networks

The Journal of Supercomputing - The sink mobility in wireless sensor networks (WSNs) brings new challenges specifically while designing the routing protocols. The advertisement of the mobile sink...