DTN-Balance: A Forwarding-Capacity and Forwarding-Queue Aware Routing for Self-organizing DTNs

In delay-tolerant networks (DTNs), intermittent network connectivity and lack of global system information pose serious challenges to achieve effective data forwarding. Most state-of-the-art DTN routing algorithms are based on hill-climbing heuristics in order to select the best available next hop to achieve satisfactory network throughput and routing efficiency. An adverse consequence of this approach is that a small subset of good users take on most of the forwarding tasks. This can quickly deplete scarce resources (e.g. storage, battery, etc.) in heavily utilized devices which degrades the network reliability. A system with a significant amount of traffic carried by a small number of users is not robust to denial of service attacks and random failures. To overcome these deficiencies, this paper proposes a new routing algorithm, DTN-Balance, that takes the forwarding capacity and forwarding queue of the relay nodes into account to achieve a better load distribution in the network. For this, we defined a new routing metric called message forwarding utility combining nodal available bandwidth and forwarding workload. Applying small world theory, we impose an upper bound on the end-to-end hop count that results in a sharp increase in routing efficiency. Queued messages in a forwarding node are arranged by DTN-Balance based on message dropping utility metric for a more intelligent decision in the case of a message drop. The performance of our method is compared with that of the existing algorithms by simulations on real DTN traces. The results show that our algorithm provides outstanding forward efficiency at the expense of a small drop in the throughput.

     

Modeling and analyzing the correctness of geographic face routing under realistic conditions

Geographic protocols are very promising for wireless ad hoc and sensor networks due to the low state storage and low message overhead. Under certain idealized conditions, geographic routing – using a combination of greedy forwarding and face routing – has been shown to work correctly and efficiently. In this work we model and analyze the correctness of geographic routing under non-ideal realistic conditions. We present a systematic methodology for micro-level behavioral analysis that shows that conditions that violate the unit-graph assumption of network connectivity, such as location errors, obstacles and radio irregularity, cause failure in planarization and consequently face routing. We then discuss the limitations of fixing these failures and prove that local algorithms that use only information up to a limited number of hops are not sufficient to guarantee face routing delivery under arbitrary connectivity. In addition, we analyze the effect of location errors in more detail to identify the possible protocol error scenarios and their conditions. We present results from an extensive simulation study about the effects of location errors on GPSR and GHT to quantify their performance degradation at different error ranges, distributions and error models. Based on our analysis we present a potential fix based on local information sharing that improves the performance significantly but does not remove all failures. Finally, we conclude that in order to avoid all failures under arbitrary connectivity, we need a non-local algorithm that can search or propagate information for an unlimited number of hops.     

On energy efficiency of geographic opportunistic routing in lossy multihop wireless networks

Geographic opportunistic routing (GOR) is an emerging technique that can improve energy efficiency in lossy multihop wireless networks. GOR makes local routing decision by using nodes?? location information, and exploits the broadcast nature and spatial diversity of the wireless medium to improve the packet forwarding reliability. In this paper, our goal is to fully understand the principles and tradeoffs in GOR, thus provide insightful analysis and guidance to the design of more efficient routing protocols in multihop wireless networks. We propose a local metric, one-hop energy efficiency (OEE), to balance the packet advancement, reliability and energy consumption in GOR. We identify and prove important properties about GOR on selecting and prioritizing the forwarding candidates in order to maximize the expected packet advancement. Leveraging the proved properties, we then propose two localized candidate selection algorithms with O(N ³) running time to determine the forwarding candidate set that maximizes OEE, where N is the number of available next-hop neighbors. Through extensive simulations, we show that GOR applying OEE achieves better energy efficiency than the existing geographic routing and blind opportunistic routing schemes under different node densities and packet sizes.     

The Impact of Deployment Pattern and Routing Scheme on the Lifetime in Multi-Sink Wireless Sensor Network

Extensive use of sensor and actuator networks in many real-life applications introduced several new performance metrics at the node and network level. Since wireless sensor nodes have significant battery constraints, therefore, energy efficiency, as well as network lifetime, are among the most significant performance metrics to measure the effectiveness of given network architecture. This work investigates the performance of an event-based data delivery model using a multipath routing scheme for a wireless sensor network with multiple sink nodes. This routing algorithm follows a sink initiated route discovery process with the location information of the source nodes already known to the sink nodes. It also considers communication link costs before making decisions for packet forwarding. Carried out simulation compares the network performance of a wireless sensor network with a single sink, dual sink, and multi sink networking approaches. Based on a series of simulation experiments, the lifetime aware multipath routing approach is found appropriate for increasing the lifetime of sensor nodes significantly when compared to other similar routing schemes. However, energy-efficient packet forwarding is a major concern of this work; other network performance metrics like delay, average packet latency, and packet delivery ratio are also taken into the account.

     

Localized energy efficient routing in mobile ad hoc networks

We consider the problem of localized energy aware routing in mobile ad hoc networks. In localized routing algorithms, each node forwards a message based on the position of itself, its neighbors and the destination. The objective of energy aware routing algorithms is to minimize the total power for routing a message from source to destination or to maximize the total number of routing tasks that a node can perform before its battery power depletes. In this paper we propose new localized energy aware routing algorithms called OLEAR. The algorithms have very high packet delivery rate with low packet forwarding and battery power consumption. In addition, they ensure good energy distribution among the nodes. Finally, packets reach the destination using smaller number of hops. All these properties make our algorithm suitable for routing in any energy constrained environment. We compare the performance of our algorithms with other existing energy and non‐energy aware localized algorithms. Simulation experiments show that our algorithms present comparable energy consumption and distribution to other energy aware algorithms and better packet delivery rate. Copyright © 2006 John Wiley & Sons, Ltd.     

基于链路质量的WSN代价均衡路由选择算法

该文针对无线传感器网络中不可靠链路通信耗能过大的问题,基于链路质量进行路由代价函数构建,并为各条路径分配适当的选择概率,采用最小跳数转发策略设计了代价均衡的路由选择算法CBLQ;为了进一步降低和均衡路由代价,分析同跳节点的备选转发条件,又扩展形成了新的路由选择算法CBLQ-E。仿真实验结果证明,两种算法均使网络的能量利用率得到有效提高,同时还降低了网络的数据传输时延。     

Poisson's probability‐based Q‐Routing techniques for message forwarding in opportunistic networks

Opportunistic Networks (OppNets) are intermittently connected infrastructure less wireless networks. There is no continuous end‐to‐end connection between the sender and the receiver, and hence nodes follow a store‐carry‐forward mechanism. The routing algorithm is required to be adaptive to the changing topology of the network. In this work, Q‐Routing technique has been used with forwarding probability and incorporated using Poisson's probability for decision making and controlling transmission energy. The algorithm refines the forwarding decision of finding the next suitable hop by exploiting the characteristics of nodes such as daily routines, mobility pattern, etc. In simulations, the performance of PBQ‐Routing is compared with Q‐Routing, Epidemic Routing, PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity), and HBPR (History Based Prediction Routing) for OppNets. The use of Poisson's distribution improves the effectiveness of the probabilistic forwarding decision. The findings show that the delivery probability of PBQ‐Routing almost gets doubled and overhead ratio reduces to half in comparison with that of Q‐Routing when used in OppNets. PBQ‐Routing outperforms other Q‐Routing based algorithms over Poisson's distribution. As there is less replication in case of PBQ‐Routing, it also saves the transmission energy.     

Energy‐aware geographic routing in wireless sensor networks with anchor nodes

Energy efficiency has become an important design consideration in geographic routing protocols for wireless sensor networks because the sensor nodes are energy constrained and battery recharging is usually not feasible. However, numerous existing energy‐aware geographic routing protocols are energy‐inefficient when the detouring mode is involved in the routing. Furthermore, most of them rarely or at most implicitly take into account the energy efficiency in the advance. In this paper, we present a novel energy‐aware geographic routing (EAGR) protocol that attempts to minimize the energy consumption for end‐to‐end data delivery. EAGR adaptively uses an existing geographic routing protocol to find an anchor list based on the projection distance of nodes for guiding packet forwarding. Each node holding the message utilizes geographic information, the characteristics of energy consumption, and the metric of advanced energy cost to make forwarding decisions, and dynamically adjusts its transmission power to just reach the selected node. Simulation results demonstrate that our scheme exhibits higher energy efficiency, smaller end‐to‐end delay, and better packet delivery ratio compared to other geographic routing protocols. Copyright © 2011 John Wiley & Sons, Ltd.     

A Connectivity-Based Multi-Lane Routing Optimization Algorithm in Vehicular Communication

This paper proposed a connectivity-based multi-lane geographic routing protocol (CGRP) for vehicular ad hoc networks. The proposed CGRP is based on an effective selection of road intersections through which a package must pass from source to destination. The cooperative connectivity probability and delay are taken into consideration when choosing the most suitable path for delay-sensitive safety traffic. Analytical expressions for cooperative connectivity probability is derived based on a three-lanes path model. Geographical forwarding is used to transfer packets between any two intersections on the path, reducing the path sensitivity to individual node movements. Furthermore, forwarding packets between two adjacent intersections also depend on geographic location information. Neighbor nodes’ priority are assigned according to position, speed, direction and other factors. Node with the highest priority will be selected as the next hop. Numerical and simulation results show that the proposed algorithm outperforms the exsiting routing protocols in terms of the end-to-end delay and the number of hops with a little cost of routing overhead in city environments.     

Design of Dead-End-Avoidance Method for Geographic Forwarding in MANET

Geographic forwarding is part of geographic routing in that each node only needs to know the location of its neighbors and the destination. This method can reduce the cost of table-driven routing which needs to maintain the whole path, even if the path is not in use. It also saves time when searching the path, as compared with reactive routing. When using geographic forwarding, it usually happens that the local maximum cannot forward the packet directly to the destination; this fundamental problem is called Dead End. We use the A star (A*) algorithm, which is usually used in role-playing or strategic games, to detour around terrain that cannot be passed through directly. Nodes must vote on an agent in a specific area to be a decision-maker and find a reference route for the source node. When the route is decided, geographic forwarding is used according to this reference path to the destination to avoid the dead end.     

Hop-distance based addressing and routing for dense sensor networks without location information

One of the most challenging problems in wireless sensor networks is the design of scalable and efficient routing algorithms without location information. The use of specialized hardware and/or infrastructure support for localization is costly and in many deployment scenarios infeasible. In this study, the wave mapping coordinate (WMC) system to address the localization problem is introduced for dense sensor networks and a highly efficient routing algorithm applicable to WMC systems is proposed. The performance of the WMC system is evaluated through simulations and compared with the performance of geographic routing without location information (GWL). The WMC system is found to be highly scalable and efficient with a simple system set-up procedure. Simulation studies confirm the high routing performance of WMC systems which is comparable to the performance of greedy geographic routing with the availability of location information.     

GeoSVR: A map-based stateless VANET routing

Compared with traditional routing techniques, geographic routing has been proven to be more suitable for highly mobile environments like Vehicular Ad-Hoc Networks (VANETs) because of enhanced scalability and feasibility. These routings use greedy modes or forwarding paths to forward packets. However, the dynamic nature of vehicular network such as frequently changed topology, vehicles density and radio obstacles, could create local maximum, sparse connectivity and network partitions. We propose GeoSVR, a geographic stateless routing combined with node location and digital map. The proposed GeoSVR scheme enhances forwarding path to solve local maximum and sparse connectivity problem, and the proposed restricted forwarding algorithm overcomes unreliable wireless channel issues. In our study, simulations and real world experiments were conducted to evaluate the efficacy and efficiency of the proposed solution. Our results show GeoSVR can provide higher packet delivery ratio with comparable latency to other geographic routing schemes.     

Minimizing Recovery State in Geographic Ad Hoc Routing

Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, node elevation ad-hoc routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic ad-hoc routing solutions.     

一种面向高速路车联网场景的自适应路由方法

车载自组织网络中节点的高速移动性使得网络拓扑频繁变化,造成路由效率低下.本文提出了一种面向高速路车联网场景的自适应路由方法.本方法采用了贪婪机会转发（GOF）算法,在选择下一跳转发节点时,同时考虑到目的节点的距离计算、节点间的链路状态以及下一跳的有效节点度状况来找出最优转发节点,并提出新的计算连通概率的方法.仿真实验和实际道路场景的测试表明,与相关算法相比在路由稳定性方面表现出较好的效果.     

Cross‐layer optimized routing in wireless sensor networks with duty cycle and energy harvesting

In this paper, we propose a cross‐layer optimized geographic node‐disjoint multipath routing algorithm, that is, two‐phase geographic greedy forwarding plus. To optimize the system as a whole, our algorithm is designed on the basis of multiple layers' interactions, taking into account the following. First is the physical layer, where sensor nodes are developed to scavenge the energy from environment, that is, node rechargeable operation (a kind of idle charging process to nodes). Each node can adjust its transmission power depending on its current energy level (the main object for nodes with energy harvesting is to avoid the routing hole when implementing the routing algorithm). Second is the sleep scheduling layer, where an energy‐balanced sleep scheduling scheme, that is, duty cycle (a kind of node sleep schedule that aims at putting the idle listening nodes in the network into sleep state such that the nodes will be awake only when they are needed), and energy‐consumption‐based connected k‐neighborhood is applied to allow sensor nodes to have enough time to recharge energy, which takes nodes' current energy level as the parameter to dynamically schedule nodes to be active or asleep. Third is the routing layer, in which a forwarding node chooses the next‐hop node based on 2‐hop neighbor information rather than 1‐hop. Performance of two‐phase geographic greedy forwarding plus algorithm is evaluated under three different forwarding policies, to meet different application requirements. Our extensive simulations show that by cross‐layer optimization, more shorter paths are found, resulting in shorter average path length, yet without causing much energy consumption. On top of these, a considerable increase of the network sleep rate is achieved. Copyright © 2014 John Wiley & Sons, Ltd.     

TPGF: geographic routing in wireless multimedia sensor networks

In this paper, we propose an efficient Two-Phase geographic Greedy Forwarding (TPGF) routing algorithm for WMSNs. TPGF takes into account both the requirements of real time multimedia transmission and the realistic characteristics of WMSNs. It finds one shortest (near-shortest) path per execution and can be executed repeatedly to find more on-demand shortest (near-shortest) node-disjoint routing paths. TPGF supports three features: (1) hole-bypassing, (2) the shortest path transmission, and (3) multipath transmission, at the same time. TPGF is a pure geographic greedy forwarding routing algorithm, which does not include the face routing, e.g., right/left hand rules, and does not use planarization algorithms, e.g., GG or RNG. This point allows more links to be available for TPGF to explore more routing paths, and enables TPGF to be different from many existing geographic routing algorithms. Both theoretical analysis and simulation comparison in this paper indicate that TPGF is highly suitable for multimedia transmission in WMSNs.     

HVE-mobicast: a hierarchical-variant-egg-based mobicast routing protocol for wireless sensornets

In this paper, we propose a new mobicast routing protocol, called the HVE-mobicast (hierarchical-variant-egg-based mobicast) routing protocol, in wireless sensor networks (WSNs). Existing protocols for a spatiotemporal variant of the multicast protocol called a “mobicast” were designed to support a forwarding zone that moves at a constant velocity, \(\stackrel{\rightarrow}{v}\), through sensornets. The spatiotemporal characteristic of a mobicast is to forward a mobicast message to all sensor nodes that are present at time t in some geographic zone (called the forwarding zone) Z, where both the location and shape of the forwarding zone are a function of time over some interval (t _start ,t _end ). Mobicast routing protocol aims to provide reliable and just-in-time message delivery for a mobile sink node. To consider the mobile entity with the different moving speed, a new mobicast routing protocol is investigated in this work by utilizing the cluster-based approach. The message delivery of nodes in the forwarding zone of the HVE-mobicast routing protocol is transmitted by two phases; cluster-to-cluster and cluster-to-node phases. In the cluster-to-cluster phase, the cluster-head and relay nodes are distributively notified to wake them up. In the cluster-to-node phase, all member nodes are then notified to wake up by cluster-head nodes according to the estimated arrival time of the delivery zone. The key contribution of the HVE-mobicast routing protocol is that it is more power efficient than existing mobicast routing protocols, especially by considering different moving speeds and directions. Finally, simulation results illustrate performance enhancements in message overhead, power consumption, needlessly woken-up nodes, and successful woken-up ratio, compared to existing mobicast routing protocols.     

Lightweight opportunistic routing forwarding strategy based on Markov chain

A lightweight opportunistic routing forwarding strategy (MOR) was proposed based on Markov chain.In the scheme,the execute process of network was divided into a plurality of equal time period,and the random encounter state of node in each time period was represented by activity degree.The state sequence of a plurality of continuous time period constitutes a discrete Markov chain.The activity degree of encounter node was estimated by Markov model to predict its state of future time period,which can enhance the accuracy of activity degree estimation.Then,the method of comprehensive evaluating forwarding utility was designed based on the activity degree of node and the average encounter interval.MOR used the utility of node for making a routing forwarding decision.Each node only maintained a state of last time period and a state transition probability matrix,and a vector recording the average encounter interval of nodes.So,the routing forwarding decision algorithm was simple and efficient,low time and space complexity.Furthermore,the method was proposed to set optimal number of the message copy based on multiple factors,which can effectively balance the utilization of network resources.Results show that compared with existing algorithms,MOR algorithm can effectively increase the delivery ratio and reduce the delivery delay,and lower routing overhead ratio.     

跳频分组无线网的路由算法分析

跳频分组无线网抗干扰性好,保密性强,广泛应用于战术通信系统。讨论了几种跳频分组无线网的路由选择算法,着重分析了针对传输多类型分组跳频网的ALR路由算法,并将此路由算法的性能与DAR算法的性能进行了比较,证实了该算法在吞吐量、端-端正确传输率等方面都优于传统的方法。     

Congestion Aware Geographic Routing Protocol for Wireless Ad Hoc and Sensor Networks

Geographic routing protocols forward packets according to the geographical locations of nodes. Thus, the criteria used to select a forwarding node impacts on the performance of the protocols such as energy efficiency and end-to-end transmission delay. In this paper, we propose a congestion aware forwarder selection (CAFS) method for a geographic routing protocol. To design CAFS, we devise a cost function by combining not only the forward progress made to a packet but also the amount of energy required for packet forwarding, forwarding direction, and congestion levels of potential forwarders. Among the potential forwarders, CAFS selects the next forwarder having the minimum cost. In our simulation studies, we compare the performance of CAFS with those of the maximum progress (MP) method and the cost over progress (CoP) method in various network conditions. The results show that compared with MP, the length of a routing path in terms of the number of hops becomes longer when CAFS is used. However, the shorter hop distance helps to avoid unnecessary retransmissions caused by packet loss in a wireless channel. In addition, since CAFS considers congestion levels of candidate forwarders, it reduces the queuing delay in each forwarder. Therefore, CAFS is superior to the MP and the CoP in terms of the energy consumption, end-to-end packet transfer delay, and the successful packet delivery rate.