DSERR: Delay Sensitive Energy Efficient Reliable Routing Algorithm

Routing strategies need to strike a balance between responsiveness and energy efficiency. Achieving this balance poses new challenges that do not coalesce either with infrastructure or ad hoc wireless networks performance requirements. Multiple strategies have emerged as a workable solution to the routing problem. Either of these solutions however cater to but one of the many constraints posed by the networks. To address this issue we propose a delay sensitive energy efficient reliable routing (DSERR) algorithm which achieves application specified soft delays with energy scavenging being the foremost concern. We try to provide soft end-to-end (e2e) delay guarantee that is proportional to the distance between the source and destination. Our algorithm uses the per hop greedy selection for soft real-time guarantees as it is impossible to provide hard guarantees in a dynamic network. DSERR presents a stateless architecture providing hop by hop reliability of data delivery to support desired delivery reliability across the sensor network.

     

Information routing and reliability issues in distributed sensornetworks

Communication issues and problems in information routing in distributed sensor networks (DSNs) are considered. Two important communication constraints, viz., the delay constraint and the reliability constraint, are identified, and their impact on information routing is discussed. It is shown that the maximum end-to-end delay in a network depends on the diameter of the network, and efficient distributed algorithms are presented to determine the diameter of asynchronous networks. A distributed algorithm that determines the diameter of an asynchronous tree network when an arbitrary node in the network initiates the algorithm is introduced. An efficient algorithm for determining the diameter when multiple nodes initiate the algorithm is presented. An algorithm to determine the diameter of arbitrary networks is presented, and its message complexity is shown. Effects of link/node failures on network delay are studied, and important network structure design criterion are discussed. The distributed, dynamic routing algorithms are reviewed, and their adaptation to DSN environments is discussed     

On the power efficiency of cooperative broadcast in dense wireless networks

A fundamental problem in large scale wireless networks is the energy efficient broadcast of source messages to the whole network. The energy consumption increases as the network size grows, and the optimization of broadcast efficiency becomes more important. In this paper, we study the optimal power allocation problem for cooperative broadcast in dense large-scale networks. In the considered cooperation protocol, a single source initiates the transmission and the rest of the nodes retransmit the source message if they have decoded it reliably. Each node is allocated an-orthogonal channel and the nodes improve their receive signal-to-noise ratio (SNR), hence the energy efficiency, by maximal-ratio combining the receptions of the same packet from different transmitters. We assume that the decoding of the source message is correct as long as the receive SNR exceeds a predetermined threshold. Under the optimal cooperative broadcasting, the transmission order (i.e., the schedule) and the transmission powers of the source and the relays are designed so that every node receives the source message reliably and the total power consumption is minimized. In general, finding the best scheduling in cooperative broadcast is known to be an NP-complete problem. In this paper, we show that the optimal scheduling problem can be solved for dense networks, which we approximate as a continuum of nodes. Under the continuum model, we derive the optimal scheduling and the optimal power density. Furthermore, we propose low-complexity, distributed and power efficient broadcasting schemes and compare their power consumptions with those-of-a traditional noncooperative multihop transmission     

Joint selection of source and channel rate for VBR videotransmission under ATM policing constraints

Variable bit-rate (VBR) transmission of video over ATM networks has long been said to provide substantial benefits, both in terms of network utilization and video quality, when compared with conventional constant bit-rate (CBR) approaches. However, realistic VBR transmission environments will certainly impose constraints on the rate that each source can submit to the network. We formalize the problem of optimizing the quality of the transmitted video by jointly selecting the source rate (number of bits used for a given frame) and the channel rate (number of bits transmitted during a given frame interval). This selection is subject to two sets of constraints, namely, (1) the end-to-end delay has to be constant to allow for real-time video display and (2) the transmission rate has to be consistent with the traffic parameters negotiated by user and network. For a general class of constraints, including such popular ones as the leaky bucket, we introduce an algorithm to find the optimal solution to this problem. This algorithm allows us to compare VBR and CBR under the same end-to-end delay constraints. Our results indicate that variable-rate transmission can increase the quality of the decoded sequences without increases in the end-to-end delay. Finally, we show that for the leaky-bucket channel, the channel constraints can be combined with the buffer constraints, such that the system is identical to CBR transmission with an additional, infrequently imposed constraint. Therefore, video quality with a leaky-bucket channel can achieve the same quality of a CBR channel with larger physical buffers, without adding to the physical delay in the system     

Variable Bit Rate Flow Routing in Wireless Sensor Networks

Since energy constraint is a fundamental issue for wireless sensor networks, network lifetime performance has become a key performance metric for such networks. In this paper, we consider a two-tier wireless sensor network and focus on the flow routing problem for the upper tier aggregation and forwarding nodes (AFNs). Specifically, we are interested in how to perform flow routing among the nodes when the bit rate from each source node is time-varying. We present an algorithm that can be used to construct a flow routing solution with the following properties: (1) If the average rate from each source node is known a priori, then flow routing solution obtained via such algorithm is optimal and offers provably maximum network lifetime performance; (2) If the average rate of each source node is unknown but is within a fraction (epsiv) of an estimated rate value, then network lifetime by the proposed flow routing solution is within 2epsiv/1-epsiv from the optimum. These results fill in an important gap in theoretical foundation for flow routing in energy-constrained sensor networks.     

无线传感器网络路由协议的设计与实现

针对传统路由协议端到端时延长、丢包率过高的现实问题,提出了一种基于贪婪转发的能量感知多路径路由协议(Greedy Forward Energy-aware Multipath Routing Protocol,GFEMRP)。GFEMRP从传感器起始结点出发,如果遇到网络黑洞则选择周边转发方式,否则将选择吞吐量大、且更接近于目的结点的结点作为下一跳结点。利用了OMNET++5.0和INET框架对包括无线自组网按需平面距离向量路由协议(Ad hoc on-demand distance vector routing protocol,AODV),动态按需无线自组织网络(Dynamic MANET On-demand,DYMO),贪婪周边无状态路由无线网络(Greedy Perimeter Stateless Routing for Wireless Networks,GPSR)和GFEMRP协议在内的四种路由协议进行了仿真和比较,实验结果表明GFEMRP协议具有良好的端到端时延、丢包率等性能。     

城市环境VANETS下的基于beacon控制的路由方案

车载网络(Vehicular ad hoc networks,VANETs)是一种特殊形式的网络,具有节点高速移动、拓扑频繁的变化的特性。这些特性为消息的传播带来挑战。路由机制是实现消息传递的关键因素。地理位置路由被广泛地应用于VANETS,要求节点周期广播beacon消息。然而,节点周期地广播beacon消息,降低了路由性能,特别是在城市区域,由于节点密集,每个节点均广播beacon消息,恶化了路由性能。为此,针对城市环境,提出基于beacon控制的路由协议RPBC(Routing protocol with beacon control)。在RPBC中,并非每个节点广播beacon消息,而设置有效的机制选择部分节点广播,从而降低了beacon冗余,同时,采用最短路径算法,减少数据传输跳数。仿真结果表明,提出的RBPC在分组投递率、端到端传输时延以及路由开销方面均有较好的性能。     

On the construction of maximum residual energy resource broadcast trees with minimum diameter in static ad hoc wireless networks

Each node in a wireless ad hoc network runs on a local energy source that has a limited energy life span. Thus, energy conservation is a critical issue in such networks. In addition, it is in general desirable to construct routes with low hop counts as a route with a high hop count is more likely to be unstable (because the probability that intermediate nodes will move away is higher). In this paper, we address these two issues concurrently with energy conservation as the primary objective and low hop count as the secondary objective. One way of addressing the energy conservation issue is to construct routes that maximize the minimum residual battery capacity available among all nodes in each route. A broadcast tree with all routes satisfying this condition is referred to as a maximum residual energy resource broadcast tree. A maximum residual energy resource broadcast tree with the least diameter is referred to as a minimum diameter maximum residual energy resource broadcast tree and the problem of constructing such a tree is referred to as the minimum diameter maximum residual energy resource broadcast routing problem (MDMRERBRP). We propose an algorithm for MDMRERBRP and prove that MDMRERBRP is optimally solvable in polynomial time using the proposed algorithm. Copyright © 2005 John Wiley & Sons, Ltd.     

An experimental switching-aware GMPLS-based lightpath provisioning protocol in wavelength-routed networks

In wavelength-routed optical networks, the high-delay introduced by the optical switching fabric for resource reservation increases critically the lightpath setup delay. In order to minimize the setup delay, Generalized Multi-protocol Label Switching (GMPLS) introduced the concept of Suggested Label Object (SL), which allows to start reserving and configuring the hardware with a proposed wavelength from the source node to the destination node. This solution is not optimal in wavelength selective networks (WSN) (i.e., without wavelengths converters). The need of guaranteeing the wavelength continuity constraint for end-to-end optical connections, combined with the lack of global wavelength-based link information (the source node is not aware of which wavelengths are available on each link), makes that the likelihood of establishing a lightpath using the proposed suggested label may be minimum. In this article, we propose an enhancement to the current GMPLS RSVP-TE signaling protocol with offset time-based provisioning that minimizes the lightpath setup, improving the overall network performance in terms of blocking probability and setup delay. Experimental performance evaluation has been carried out in ADRENALINE testbed, a GMPLS-based intelligent all-optical transport network.     

Cooperative Strategies and Achievable Rate for Tree Networks With Optimal Spatial Reuse

In this paper, a low-complexity cooperative protocol that significantly increases the average throughput of multihop upstream transmissions for wireless tree networks is developed and analyzed. A system in which transmissions are assigned to nodes in a collision free, spatial time division fashion is considered. The suggested protocol exploits the broadcast nature of wireless networks where the communication channel is shared between multiple adjacent nodes within interference range. For any upstream end-to-end flow in the tree, each intermediate node receives information from both one-hop and two-hop neighbors and transmits only sufficient information such that the next upstream one-hop neighbor will be able to decode the packet. This approach can be viewed as the generalization of the classical three node relay channel for end-to-end flows in which each intermediate node becomes successively source, relay and destination. The achievable rate for any regular tree network is derived and an optimal schedule that realizes this rate in most cases is proposed. Our protocol is shown to dramatically outperform the conventional scheme where intermediate nodes simply forward the packets hop by hop. At high signal-to-noise ratio (SNR), it yields approximately 66% throughput gain for practical scenarios.     

A cross-layer framework for optimal delay-margin,network lifetime and utility tradeoff in wireless visual sensor networks

For wireless multimedia sensor networks a distributed cross-layer framework is proposed, which not only achieves an optimal tradeoff between network lifetime and its utility but also provides end-to-end delay-margin. The delay-margin, defined as the gap between maximum end-to-end delay threshold and the actual end-to-end delay incurred by the network, is exploited by the application layer to achieve any desired level of delay quality-of-service. For optimal performance tradeoff an appropriate objective function for delay-margin is required, which is obtained by employing sensitivity analysis. Sensitivity analysis is performed by incorporating delay-margin in the end-to-end delay constraints while penalizing its price in the objective function. For distributed realization of proposed cross-layer framework, the optimal tradeoff problem is decomposed into network lifetime, utility and delay-margin subproblems coupled through dual variables. The numerical results for performance evaluation show that compromising network utility does not guarantee both lifetime and delay-margin improvement, simultaneously, for the set of operating points. Performance evaluation results also reveal that the fairness among different delay-margins, corresponding to different source–destination node pairs, can be improved by relaxing the end-to-end delay threshold.     

On-demand loop-free routing with link vectors

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request (RREQ) to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast RREQ to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform dynamic source routing, ad hoc on-demand distance vector, optimized link-state routing protocol, and topology broadcast based on reverse-path forwarding, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.     

Efficient network QoS provisioning based on per node trafficshaping

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We consider a network comprised of store-and-forward packet switches, in which a packet scheduler is available at each output link. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same “minimal” envelope. The main disadvantage of this class of service discipline is that the end-to-end delay guarantees are obtained as the sum of the worst-case delays at each node, but we show that this problem can be alleviated through “proper” reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform service disciplines that are based on generalized processor sharing (GPS). Furthermore, we show that we can restrict the space of “good” shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving and as a result reduce the average end-to-end delays     

On the Construction of a Strongly Connected Broadcast Arborescence with Bounded Transmission Delay

Energy conservation is an important concern in wireless networks. Many algorithms for constructing a broadcast tree with minimum energy consumption and other goals have been developed. However, no previous research work considers the total energy consumption and transmission delays of the broadcast tree simultaneously. In this paper, based on an (alpha, beta){hbox{-}}{rm tree}, a novel concept to wireless networks, we define a new Strongly connected Broadcast Arborescence with bounded Transmission delay (SBAT) problem and design the Strongly connected Broadcast Arborescence (SBA) algorithm with linear running time to construct a strongly connected broadcast tree with bounded total power, while satisfying the constraint that the transmission delays between the source and the other hosts are also bounded. We also propose the distributed version of the SBA algorithm. The theoretical analysis and simulation results show that the SBA algorithm gives a proper solution to the SBAT problem.     

Node delay assignment strategies to support end-to-end delay requirements in heterogeneous networks

In a complex, heterogeneous network environment, such as the Internet, packets traversing different networks may be subjected to different treatments and may face different traffic loads across the routing path. This paper addresses the key issue of how to assign delay budgets to each network node along the routing path so that the end-to-end delay requirements of the supported applications are met. First, we describe a methodology to compute for a given flow a set of feasible per-node delays for the class of delay-based servers. We then formalize an optimal per-node delay assignment problem which takes into consideration the workload across the routing path. The solution, for homogeneous and heterogeneous networks, is provided. The resulting solution is optimal, but its implementation overhead is relatively high. To overcome this shortcoming, we propose two heuristics, EPH() and LBH(), to approximate the optimal strategy. EPH() uses the equi-partition concept to compute initial delay values and adjust these delay values to meet the end-to-end delay requirements. LBH() uses a relaxation factor to distribute the load proportionally across all nodes on the routing path. A simulation-based comparative analysis shows that the heuristics perform closely to the optimal schemes.     

Energy efficient networking via dynamic relay node selection in wireless networks

Mobile wireless ad hoc networks need to maximize their network lifetime (defined as the time until the first node runs out of energy). In the broadcast network lifetime problem, all nodes are sending broadcast traffic, and one asks for an assignment of transmit powers to nodes, and for sets of relay nodes so that the network lifetime is maximized. The selection of a dynamic relay set consisting of a single node (the ‘master’), can be regarded as a special case, providing lower bounds to the optimal lifetime in the general setting. This paper provides a preliminary analysis of such a ‘dynamic master selection’ algorithm, comparing relaying to direct routing.     

Generalized quality-of-service routing with resource allocation

We present a general framework for the problem of quality-of-service (QoS) routing with resource allocation for data networks. The framework represents the QoS parameters as functions rather than static metrics. The formulation incorporates the hardware/software implementation and its relation to the allocated resources into a single framework. The proposed formulation allows intelligent adaptation of QoS parameters and allocated resources during a path search, rather than decoupling the path search process from resource allocation. We present a dynamic programming algorithm that, under certain conditions, finds an optimal path between a source and destination node and computes the amount of resources needed at each node so that the end-to-end QoS requirements are satisfied. We present jitter and data droppage analyzes of various rate-based service disciplines and use the dynamic programming algorithm to solve the problem of QoS routing with resource allocation for networks that employ these service disciplines.     

Adaptive per hop differentiation for end-to-end delay assurance in multihop wireless networks

As the rapid growth of smart hand-held devices, multihop wireless access networks have a lot of potential applications in a variety of fields in civilian and military environments. Many of these applications, such as realtime audio/video streaming, will require some form of end-to-end QoS assurance. In this paper, we present an adaptive per hop differentiation (APHD) scheme towards achieving end-to-end delay assurance in multihop wireless networks. Our scheme is based on EDCA technique which is proposed in 802.11e draft. In EDCA, data packets of different priorities will use different MAC contention parameter set, which translate into different delays. Our APHD scheme extends the capability of EDCA into multihop environment by taking end-to-end delay requirement into consideration at each intermediate hop. Following a cross-layer design approach, APHD is aimed to be a distributed and localized technique. Individual nodes keep track of the channel state independently without any intercommunication overhead. Data packets carry end-to-end delay requirement along with other important information in the packet header. At an intermediate node, based on data packet’s end-to-end requirement, its accumulative delay so far, and the current node’s channel status, APHD smartly adjusts data packet’s priority level in order to satisfy its end-to-end delay requirement. Simulation results show that APHD scheme can provide excellent end-to-end delay assurance while achieving much higher network utilization, compared to a pure EDCA scheme.     

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within $O(1)$ times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.      

Challenges for GMPLS lightpath provisioning in transparent optical networks: wavelength constraints in routing and signaling - [Topics in optical communications]

GMPLS has introduced several enhancements to the MPLS-TE routing and signaling control plane protocols to handle dynamic lightpath provisioning in wavelength-routed networks. Specifically, the GMPLS signaling protocol has been enhanced to support two new provisioning functionalities, namely, the minimization of the setup delay, and the setup of bidirectional connection requests. In both cases, the source node must perform a wavelength allocation for either minimizing the setup delay (i.e., the suggested label) or requesting a bidirectional connection (i.e., the upstream label). However, these GMPLS provisioning functionalities present important deficiencies when applied to wavelength-routed networks with the wavelength continuity constraint, degrading the network performance considerably. The reason is that the standard GMPLS routing protocols flood link attributes only at bandwidth granularity, that is, no per-wavelength channel granularity is disseminated. Therefore, the source node is unable to perform an optimal wavelength assignment that fulfils the wavelength continuity constraint along the complete route toward the destination. In this article we present and experimentally evaluate an enhanced routing-based solution in the ADRENALINE testbed to handle the wavelength continuity constraint.