Minimum delay routing for wireless networks with STDMA

STDMA emerges as a promising channel access technique for providing Quality of Service (QoS) guarantees in multi-hop ad hoc networks such as community mesh and sensor networks. The contention-free channel access combined with spatial reuse of the channel provide significant benefits in the energy/throughput trade-off. On the other hand, the time-multiplexed communication introduces extra delay on the packets when relayed by intermediate nodes. Hence in large wireless sensor networks or mesh networks, where data is routed over several hops before reaching the data sink, STDMA protocols may introduce high end-to-end latency due to the reservation-based access policy. We argue that a suitable routing protocol specifically designed for reservation-based Medium Access Control (MAC) protocols can alleviate their high-latency drawback. Following this argument, we propose first such routing algorithms working on top of a generic STDMA MAC protocol. First, we consider routing with data fusion and present our GreenWave routing idea. We show that our algorithm significantly reduces the end-to-end delay when compared to routing over the shortest-hop paths. Second, we consider routing without data fusion, by taking into account the effect of congestion along the paths on the end-to-end delays. We provide a QIP formulation of the problem, and present a lower bound and a heuristic algorithm to bound the optimal solution. Based on the centralized heuristic algorithm, we propose a distributed, dynamic routing protocol GreenWave routing with Congestion and Flow control (GWCF), which uses a novel congestion and flow control technique utilizing the underlying contention-free protocol. We show by simulations that GWCF routing significantly improves the end-to-end delay while increasing the network throughput when compared to routing over shortest paths.

基于相遇紧密程度估测的延迟容忍网络路由

针对延迟容忍网络中节点运动状态变化频繁、通信路径不完整,使得转发消息仅能通过节点相遇而获得连接机会来完成,以及在不知节点间相关性的延迟容忍网络中盲目转发消息易导致其转发成功率较低等问题,提出了基于相遇紧密程度动态估测的延迟容忍网络路由策略。通过设计节点间的条件相遇时间间隔和连接持续时间的计算模型,来确定节点间关系的紧密程度;定义延迟容忍网络模型,构造最短路径择取机制,动态地选出条件最短路径,对消息进行转发。仿真数据对比显示,所提策略可有效改善网络性能,提高消息成功投递率,降低传输时延和负载率。     

容迟网络中基于复制策略的单播路由算法研究

容迟/容延网络(Delay Tolerant Network/DTN)泛指由于节点移动、能量管理、调度等原因而出现频繁中断、甚至长时间处于中断状态的一类网络。针对DTN具有的时延高、割裂频繁、节点能量受限、以及节点移动性等特点,通过对DTN中基于复制策略的单播路由策略进行分类和比较,提出了如何优化DTN单播路由算法、提高网络传输率的建议。     

Threshold based locking routing strategy for delay tolerant network

Delay tolerance network probabilistic routing protocols forward message to a node by observing its predictability value to meet the message destination. However, it is vital to predict the ability of node to carry the transmitted message. For instance, the traffic confluence on the high probable nodes can produce congestion that results in the drop of previously stored messages. These drops diminish the delivery ratio because the dropped message lost its opportunity to be delivered. Since, there exist multiple copies of each message; therefore, the same node invariably receives the dropped messages from other parts of the network and causes the highest number of transmissions. Additionally, the replication from source node continues on the high probable peers even the previous copies were transmitted on the better predictable neighbors than the current. In this paper, we have proposed a novel routing method called as the adaptive threshold based locking method that maintains the contemporary status of the node based on its activity in the network. We have used the adaptive status measuring metrics such as transmit factor, drop factor and hop away count. Moreover, a threshold based locking method has been introduced to control the diffusion of messages. We have performed the comparison of existing and proposed routing methods with real time mobility traces. The proposed strategy has bolstered the delivery ratio and minimizes hop count, end-to-end delay and number of transmission.     

Mobile ad hoc network proactive routing with delay prediction using neural network

Existing MANET routing protocols rely heavily on hop count evaluation. Although this is simple and efficient, it sacrifices the potential performance gains obtainable by considering other dynamic routing metrics. In this paper, we propose a delay prediction mechanism and its integration with a MANET proactive routing protocol. We demonstrate our approach of predicting mean queuing delay as a nonstationary time series using appropriate neural network models: Multi-Layer Perceptron or Radial Basis Function. To support MANET proactive routing, our delay prediction mechanism is devised as a distributed, independent, and continuous neural network training and prediction process conducted on individual nodes. We integrated our delay prediction mechanism with a well-known MANET proactive routing protocol—OLSR. The essential part of this integration is our TierUp algorithm, which is a novel node-state routing table computation algorithm. The structure and the key parameters of the resulting extended OLSR, called OLSR_NN, are also discussed. Our simulation shows that because of its capability of balancing the traffic, OLSR_NN is able to increase data packet delivery ratio and reduce average end-to-end delay in scenarios with complex traffic patterns and wide range of node mobility, compared to OLSR.     

Minimum delay algorithm based on time aggregated graph in DTN network

The DTN network has the characteristics of dynamic topology change,thus the routing algorithm of static network can not solve the routing problem of time-varying network,and can not support fast transmission of given tasks.The existing time-variant routing algorithm CGR (contact graph routing) uses the earliest contact to obtain the shortest path,but because of the influence of the order of the connectivity period,the CGR algorithm has low link utilization.To solve this problem,the method of finding the shortest path was proposed.Besides,in order to characterize the relation between the different connect periods of the same link,the time series of node cache was added to the time aggregated graph.Based on this,the end-to-end multi-path shortest delay routing algorithm for the known task requirements was proposed.Finally,the feasibility of the algorithm was proved by an example.     

Resource refrain quota based routing protocol for delay tolerant network

Wireless Networks - The delay tolerant network Spray and Wait routing protocol minimizes resource consumption by defining the ‘n’ number of message transmission quota. However, with...     

Towards a reputation-based routing protocol to contrast blackholes in a delay tolerant network

A Delay Tolerant Network (DTN) relies on the implicit assumption that nodes cooperate towards message forwarding. However, this assumption cannot be satisfied when there are malicious nodes acting as blackholes and voluntarily attracting and dropping messages.In this paper we propose a reputation-based protocol for contrasting blackholes. Every node locally maintains the reputation of forwarding nodes it comes in touch with and, then, upon selecting the next forwarding node, the node chooses among those having the highest reputation. The proposed reputation protocol is composed of three basic mechanisms—acknowledgments, node lists, and aging—that make communication efficient and capable of adapting to the changing operating conditions of a DTN.The protocol has been used to extend CAR [1]. The resulting protocol RCAR (reputation-based CAR) has been compared with T-ProPHET [2], a state-of-the-art reputation-based DTN routing protocol, from several standpoints. As it turns out, RCAR is more effective than T-ProPHET and outperforms it in most cases.     

Some reliability routing problems in an acyclic directed network with stochastic terminal node

This paper considers a stochastic acyclic directed network in which the origin and the final destination nodes are fixed but the process may terminate at random on any intermediate node. Nodes are perfect but the links are assumed to be in one of the two states-good or bad. Problems concerning expected maximum reliability routes have been considered.     

基于社会环境的一种优化Prophet延迟容忍网络路由算法

在移动智能终端普及的今天,延迟容忍网络作为数据的补充传输方案具有重要的意义。在社会环境中,节点移动规律具有明显周期性,Prophet路由算法在该类场景中效果较好。因此文章提出了一种基于加强传统概率的路由算法,其在工作日模型下对E Prophet算法进行了仿真实验。实验结果表明,所提出的E Prophet算法在该场景下优于传统的Prophet算法。     

Minimum price inter-domain routing algorithm

We show a minimum price (MP) inter-domain routing algorithm that selects the cheapest paths among a number of independent domains, used for supplying end users with application services. The price of the network service is determined by the so-called service parameters and network parameters. The former represents the negotiable quality of service (QoS) parameters, summarized by the so-called virtual end-to-end delay, and the latter characterizes the intrinsic quality of the network     

Design of efficient lightweight strategies to combat DoS attack in delay tolerant network routing

Delay tolerant networks (DTNs) are characterized by delay and intermittent connectivity. Satisfactory network functioning in a DTN relies heavily on co-ordination among participating nodes. However, in practice, such co-ordination cannot be taken for granted due to possible misbehaviour by relay nodes. Routing in a DTN is, therefore, vulnerable to various attacks, which adversely affect network performance. Several strategies have been proposed in the literature to alleviate such vulnerabilities—they vary widely in terms of throughput, detection time, overhead etc. One key challenge is to arrive at a tradeoff between detection time and overhead. We observe that the existing table-based reactive strategies to combat Denial-of-service (DoS) attacks in DTN suffer from two major drawbacks: high overhead and slow detection. In this paper, we propose three secure, light-weight and time-efficient routing algorithms for detecting DoS attacks (Blackhole and Grey-hole attacks) in the Spray & Focus routing protocol. The proposed algorithms are based on use of a small fraction of privileged (trusted) nodes. The first strategy, called TN, outperforms the existing table-based strategy with 20–30 % lesser detection time, 20–25 % higher malicious node detection and negligible overhead. The other two strategies, CTN_MI and CTN_RF explore the novel idea that trusted nodes are able to utilize each others’ information/experience using their long range connectivity as and when available. Simulations performed using an enhanced ONE simulator reveals that investing in enabling connectivity among trusted nodes (as in CTN_RF) can have significant performance benefits.     

Multicast routing with end-to-end delay and delay variationconstraints

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session     

Minimum flow maximum residual routing in LEO satellite networks using routing set

Satellite networks are used as backup networks to the terrestrial communication systems. In this work, we tried to find a routing strategy over dynamic satellite systems to better utilize the capacity of the network. The satellite networks are not affected by natural disasters, therefore they can be used widely during and after disasters. The Minimum Flow Maximum Residual (MFMR) routing algorithm over the Routing Set boundaries is proposed in order to better utilize the capacity of the system by distributing the load over the shortest path alternatives of the system. We assumed the satellite network as having finite states and formulated the problem by using Finite State Automation concept along with earth-fixed cell strategy by using a virtual satellite network model. The routing problem in satellite networks is previously studied in the literature and it is conjectured that the problem is NP-Hard. The online and offline problems are stated and the MFMR algorithm is described in detail. The algorithm is compared with alternatives by simulating the network on Opnet Modeler. Finally, the performance analysis of different scenarios is given in this work. Roy Kucukates received his BS, MS and PhD degrees in computer engineering from Bogazici University, Istanbul, in 1993, 1995 and 2002, respectively. He worked as teaching assistant in Bogazici University between 1993 and 1995. Currently, he is a part time instructor in the Computer Engineering Department of Koc University and Dogus University. He is the co-founder and manager of Gordion Bilgi Hizmet Ltd Sti. LEO satellite networks, wireless networks, simulation and performance evaluationl, routing protocols can be stated among his research areas. Cem Ersoy received his BS and MS degrees in electrical engineering from Bogazici University, Istanbul, in 1984 and 1986, respectively. He worked as an R&D engineer in NETAS A.S. between 1984 and 1986. He received his PhD in electrical engineering from Polytechnic University, Brooklyn, New York in 1992. Currently, he is a professor and department head in the Computer Engineering Department of Bogazici University. His research interests include performance evaluation and topological design of communication networks, wireless communications and mobile applications. Wireless sensor networks. Dr. Ersoy is a Senior Member of IEEE.     

Cross-layer selective routing for cost and delay minimization in IEEE 802.11ac wireless mesh network

Wireless Networks - A Wireless Internet-access Mesh NETwork (WIMNET) provides scalable and reliable internet access through the deployment of multiple access points (APs) and gateways (GWs). In...     

RSPEED:无线传感器网络中基于不确定延迟的可靠实时路由

基于不可靠的链路,综合考虑了链路的质量与链路的延时,提出了一种新的转发可靠性概念,并在此基础上,设计了一种新的实时路由协议(RSPEED)。利用转发可靠性表示节点在给定的延迟阈值下成功将数据分组转发到邻居节点的概率,并以此保证路由的实时性和可靠性,提供一定的QoS服务。另外,当环境中链路质量比较差时,还能在满足实时性的基础上通过权衡传输延时与传输可靠性,从而获得更高的传输成功率。实验结果表明,提出的方法能够显著地提高分组的传输成功率和减少超过给定延迟阈值分组的数量,特别是当信道非常差时,提出的方法在满足实时性上比SPEED高出20%左右。     

容延容断网络路由算法及其存在问题的探析

容延容断网络(delay/disruption tolerant network,简称DTN)是一种新型网络体系结构.在这一类网络中,节点与节点之间不存在端到端的路径,因此节点之间的通信一般使用"存储-携带-转发"的模式来进行,也就是节点需要先将信息存储起来再携带信息,直到遇到能够将消息转发到目的节点的时候才将消息转发出去.因此在容延容断网络中路由算法的关键性问题是如何以较高的发送成功率和较低的延迟将消息转发到目的节点.DTN网络的应用场景通常由手机、蓝牙设备以及具备WiFi功能的手持电子设备等组成的移动自组网络.本文主要研究DTN路由算法及其存在的问题.     

QoS multicast routing with delay constraints

Proliferation of group-based real-time applications, such as online games and video conferencing has motivated research into QoS multicast routing. These types of applications require consideration of both source-to-destination delay (i.e., packet delay from the source to all destinations) and inter-destination delay variation (i.e., the difference in packet delay from the source to different destinations) constraints. In this paper, we formulate a new combined problem for delay partitioning and multicast routing with source-to-destination delay and inter-destination delay variation constraints in a QoS framework, where a delay dependent cost function is associated with each network link. After identifying the problem asnp-complete, we introduce a Genetic Algorithm (ga) based algorithm that computes a source-based multicast tree which satisfies both constraints with near-optimal cost. We compare differentga schemes using different selection operators and find that the combination of Steady Statega and Remainder Stochastic Sampling selection operator works best for our problem. Simulation results also show that ourga heuristic consistently perfornis better than several other simple heuristics.