Information efficiency of multihop packet radio networks with channel-adaptive routing

This paper analyzes the benefit of adaptive routing based on knowledge of the channel state information in multihop, ad hoc wireless networks that use direct-sequence code-division multiple access. Cross-layer, channel-adaptive routing exploits the inherent spatial diversity of multihop wireless networks to select links with favorable channel conditions. The information efficiency, an extension of a previously used measure called expected progress, is used to evaluate performance. Results show that, combined with adaptive modulation, adaptive routing can improve performance in ad hoc networks by a factor of four to five in channels with Rayleigh fading and lognormal shadowing. The lack of position information in the routing decision would reduce performance by 25%. New approaches to channel-adaptive routing that enable rapid adaptivity to channel conditions are discussed.     

A distributed link scheduling algorithm for CDMA packet radio networks

A distributed algorithm for the conflict-free channel allocation in CDMA (code division multiple access) networks is presented. Dynamic adjustment to topological changes is also considered. Though the schedules produced by our algorithm are not optimal with respect to link schedule length, the algorithm is simple and practical. The link schedule length minimization problem is NP-complete. Here the length of a link schedule is the number of time slots it uses. The algorithm guarantees a bound 2 — 1 time slots on the TDMA cycle length, where is the maximum degree of a station (i.e., maximum number of stations that a station can reach by radio links) in the network. The message complexity of a station isO().     

Topology control for multihop packet radio networks

A distributed topology-control algorithm has been developed for each node in a packet radio network (PRN) to control its transmitting power and logical neighbors for a reliable high-throughput topology. The algorithm first constructs a planar triangulation from locations of all nodes as a starting topology. Then, the minimum angles of all triangles in the planar triangulation are maximized by means of edge switching to improve connectivity and throughput. The resulting triangulation at this stage, the Delaunay triangulation, can be determined locally at each node. The topology is modified by negotiating among neighbors to satisfy a design requirement on the nodal degree parameter. Simulations show that the final topology is degree-bounded, has a rather regular and uniform structure, and has throughput and reliability that are greater than that of a number of alternative topologies     

Spatial reuse in multihop packet radio networks

Multihop packet radio networks present many challenging problems to the network analyst and designer. The communication channel, which must be shared by all of the network users, is the critical system resource. In order to make efficient use of this shared resource, a variety of channel access protocols to promote organized sharing have been investigated. Sharing can occur in three domains: frequency, time, and space. This paper is mostly concerned with sharing and channel reuse in the spatial domain. A survey of results on approaches to topological design and associated channel access protocols that attempt to optimize system performance by spatial reuse of the communication channel is presented.     

Diversity reception in a multihop packet radio network

The performance improvement which results from the use of multiple antennas at each node in a multihop packet radio network is examined. Four transmission strategies based on three previously proposed routing schemes and one new routing scheme, MTP, are studied. It is found that the use of two antennas can improve the performance of all four transmission strategies by about 25% in a Rayleigh fading environment. The transmission strategy based on the MTP routing scheme is shown to be generally superior to those based on the other three routing schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Jamming in slotted ALOHA multihop packet radio networks

The properties of a packet radio network in the presence of active interference are discussed. Both the jammer and the network nodes are subject to an average power constraint. The network uses slotted ALOHA multiple access schemes and some simple fixed routing strategies with constant transmitter power. By using a game-theoretic approach the situation is considered as a two-person constant-sum game. The author defines network performance as the values of the game in terms of the expected forward progress of a packet. Both the performance and the optimum strategies for access and jamming are investigated     

Modeling and performance analysis of multihop packet radio networks

The design of packet radio networks involves a large number of issues which interact in a very complex fashion. Many of these pertain to the RF channel and its use, others pertain to the operational protocols. Clearly, no single model can be formulated which incorporates all the necessary parameters and leads to the optimum solution. The one essential element which complicates matters is that, contrary to point-to-point networks in which each channel is utilized by a single pair of nodes, the radio channel in packet radio networks is a multiaccess broadcast resource: i) in a given locality determined by radio connectivity, the channel is shared by many contending users, hence the need for channel access protocols; ii) radio is a broadcast medium and thus the action taken by a node has an effect on the actions taken by neighboring nodes and their outcome. Despite the complexity of the problem, there has been significant progress worth reporting on. The work accomplished so far has been either the analysis of specific examples of networks or an attempt to create models that would be useful in the design of general networks. The purpose of this paper is to survey the various modeling techniques that have been used for the performance analysis of packet radio networks, and to discuss the assumptions underlying these models, their scope of applicability, and some of the results obtained.     

Diversity reception in a multihop packet radio network

The performance improvement which results from the use of multiple antennas at each node in a multihop packet radio network is examined. Four transmission strategies based on three previously proposed routing schemes and one new routing scheme, MTP, are studied. It is found that the use of two antennas can improve the performance of all four transmission strategies by about 25% in a Rayleigh fading environment. The transmission strategy based on the MTP routing scheme is shown to be generally superior to those based on the other three routing schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

A distributed network coded control channel for multihop cognitive radio networks

Designing a solution for multihop cognitive radio networks poses several challenges such as the realization of the control channel, the detection of primary users, and the coordination of secondary users for dynamic spectrum access purposes. In this article we discuss these challenges and propose a solution that aims to meet most of them. The proposed solution is completely distributed, and does not need dedicated spectrum resources for control purposes, but rather leverages on a virtual control channel that is implemented by having users exchange control information whenever they meet in a particular channel, using network coding techniques for better dissemination performance. Due to these aspects, our proposal represents a significant improvement over existing dynamic spectrum access and multichannel MAC solutions. We discuss the effectiveness of our scheme in multihop cognitive ad hoc networks, where secondary users need to opportunistically access the spectrum at those locations and times at which it is not used by primary users. Finally, we report the results of an evaluation study assessing the performance of the proposed scheme with respect to different system and scenario parameters.     

The strongly connecting problem on multihop packet radio networks

The problem of strongly connecting a multihop packet radio network by using a minimal total amount of transmission power is investigated. This problem is shown to be NP-complete. An approximation algorithm with the same computational complexity as that of finding a minimum spanning tree is given. It is also shown that the approximation algorithm can find a solution no greater than twice that of the optimal solution. Experimental results show that the approximation solution may be close to the optimal solution     

Slotted ALOHA multihop packet radio networks with directional antennas

The use of directional antennas in multihop packet radio networks using slotted ALOHA access is considered. Tractable approximations to the network performance in terms of expected forward progress are derived. Results show that packet collisions can be strongly reduced already with moderate gain antennas to allow for a substantial increase in network performance.<>     

Design algorithms for multihop packet radio networks with multipledirectional antennas stations

A protocol called the simple tone sense (STS) protocol is designed for multihop packet radio networks (PRNs) with multiple directional antennas stations. The protocol can minimize transmission interference by using a group of tones to identify the active neighbors. A variation of the STS protocol called the variable power tone sense (VPTS) protocol is also designed to further reduce interference. Algorithms for assigning tones and for determining the orientation and broadcasting angles of the directional antennas are designed. Design examples are given. Simulation result shows that the STS protocol gives better throughput-delay performance than the busy-tone multiple access protocol, especially when the traffic is heavy. The VPTS protocol gives still better throughput-delay performance than the STS protocol     

A distributed algorithm for delay-constrained unicast routing

We study the NP-hard delay-constrained least cost (DCLC) path problem. A solution to this problem is needed to provide real-time communication service to connection-oriented applications, such as video and voice. We propose a simple, distributed heuristic solution, called the delay-constrained unicast routing (DCUR) algorithm, DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is O(|V|²) messages, where |V| is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least delay path algorithm. Our results show that DCUR's path costs are within 10% of those of the optimal solution     

一种分布式延迟受限路由算法

本文提出了一种分布式点到延迟受限路由算法（UDCR）在满足给定时延要求的路径存在的条件下，该算法总能找到满足边界限制条件的优化路径。对于每一个网络节点，算法只需要存储有限的网络状态信息和运算量。文中证明了算法的正确性，给出了量坏情况下的消息复杂性是O（|V|^2)其中|V|是顶点的数量。仿真结果显示，与其它延迟受限的启发式算法相比，本文提出的算法在适中的消息复杂性下取得了最好的代价性能。     

一种适合于认知无线传感网络的路由算法

路由设计是认知无线传感网络（CRSNs）中目前受到较少关注却很重要的一个领域。在CRSN中,由于主用户（PUs）对可用信道资源的随机占用行为,路由算法的设计不仅需要考虑如何延长网络寿命,还要考虑网络内数据传输的可靠性。本文研究了具有频谱可感知特性,且对能量消耗敏感的 CRSN路由问题,揭示了 CRSN路由问题的独特性,并将这类问题表述为在能量约束和变化的网络拓扑环境下的网络寿命优化问题。在回顾传感器网络的典型算法之后,提出一种新的路由度量来克服 CRSN的路由设计挑战,即认知能量度量（CE）。在此基础上,提出一种分布式路由算法以延长网络寿命,同时提高数据传输的可靠性。仿真结果表明,所提路由算法能很好地适应 CRSN中可用信道资源及网络拓扑的随机变化。     

TDMA scheduling design of multihop packet radio networks based onlatin squares

Many transmission scheduling algorithms have been proposed to maximize spatial reuse and minimize the time division multiple access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. The proposed algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of this algorithm and examine the topology-transparent characteristics and the sensitivity on design parameters by analytical and simulation techniques     

A distributed routing algorithm for mobile wireless networks

We present a loop-free, distributed routing protocol for mobile packet radio networks. The protocol is intended for use in networks where the rate of topological change is not so fast as to make flooding the only possible routing method, but not so slow as to make one of the existing protocols for a nearly-static topology applicable. The routing algorithm adapts asynchronously in a distributed fashion to arbitrary changes in topology in the absence of global topological knowledge. The protocol's uniqueness stems from its ability to maintain source-initiated, loop-free multipath routing only to desired destinations with minimal overhead in a randomly varying topology. The protocol's performance, measured in terms of end-to-end packet delay and throughput, is compared with that of pure flooding and an alternative algorithm which is well-suited to the high-rate topological change environment envisioned here. For each protocol, emphasis is placed on examining how these performance measures vary as a function of the rate of topological changes, network topology, and message traffic level. The results indicate the new protocol generally outperforms the alternative protocol at all rates of change for heavy traffic conditions, whereas the opposite is true for light traffic. Both protocols significantly outperform flooding for all rates of change except at ultra-high rates where all algorithms collapse. The network topology, whether dense or sparsely connected, is not seen to be a major factor in the relative performance of the algorithms.The work of A. Ephremides was supported in part by the National Science Foundation under grants D-CDR-8803012 and EEC94-02384.     

A heuristic wavelength assignment algorithm for multihop WDMnetworks with wavelength routing and wavelength re-use

Presents a heuristic algorithm for effectively assigning a limited number of wavelengths among the access stations of a multihop network wherein the physical medium consists of optical fiber segments which interconnect wavelength-selective optical switches. Such a physical medium permits the limited number of wavelengths to be re-used among the various fiber links, thereby offering very high aggregate capacity. Although the optical connectivity among the access station can be altered by changing the states of the various optical switches, the resulting optical connectivity pattern is constrained by the limitation imposed at the physical level. The authors also study two routing schemes, used to route requests for virtual connections. The heuristic is tested on a realistic traffic model, and the call blocking performance of new requests for virtual connections is studied through extensive simulations and compared against the blocking performance of an ideal infinite capacity centralized switch (lowest possible call blocking caused exclusively by congestion on the finite capacity user input/output links, never by the switch fabric itself). Surprisingly, the authors find that, for a wide range of parameters, the blocking performance of the lightwave network is almost the same as that of the ideal centralized switch. From these results, they conclude that the heuristic algorithm is effective and the routing scheme is efficient     

Optimum transmission ranges in multihop packet radio networks inthe presence of fading

The evaluation of optimum transmission ranges in a packet radio network in a fading and shadowing environment is considered. It is shown that the optimal probability of transmission of each user is independent of the system model and is p_o≃0.271. The optimum range should be chosen so that on the average there are χ(G/b)²η/ terminals closer to the transmitter than the receiver, where G is the spread spectrum processing gain, b is the outage signal-to-noise ratio threshold, η is the power loss factor and χ depends on the system parameters and the propagation model. The performance index is given in terms of the optimal normalized expected progress per slot, given by ϑ(G/b)¹η/ where ϑ is proportional to the square root of χ. A comparison with the results obtained by using deterministic propagation models shows, for typical values of fading and shadowing parameters, a reduction up to 40% of the performance index