Analysis of tree‐based multicast routing in wireless sensor networks with varying network metrics

Wireless ad hoc and sensor networks are emerging with advances in electronic device technology, wireless communications and mobile computing with flexible and adaptable features. Routing protocols act as an interface between the lower and higher layers of the network protocol stack. Depending on the size of target nodes, routing techniques are classified into unicast, multicast and broadcast protocols. In this article, we give analysis and performance evaluation of tree‐based multicast routing in wireless sensor networks with varying network metrics. Geographic multicast routing (GMR) and its variations are used extensively in sensor networks. Multicast routing protocols considered in the analytical model are GMR, distributed GMR, demand scalable GMR, hierarchical GMR, destination clustering GMR and sink‐initiated GMR. Simulations are given with comparative analysis based on varying network metrics such as multicast group size, number of sink nodes, average multicast latency, number of clusters, packet delivery ratio, energy cost ratio and link failure rate. Analytical results indicate that wireless sensor network multicast routing protocols operate on the node structure (such as hierarchical, clustered, distributed, dense and sparse networks) and application specific parameters. Simulations indicate that hierarchical GMR is used for generic multicast applications and that destination clustering GMR and demand scalable GMR are used for distributed multicast applications. Copyright © 2012 John Wiley & Sons, Ltd.     

移动自组织网络中基于树结构的优化组播路由算法(英)

Mobile Ad hoc Networks(MANETs) play an important role in emergency communications where network needs to be constructed temporarily and quickly.Since the nodes move randomly,routing protocols must be highly effective and reliable to guarantee successful packet delivery.Based on the data delivery structure,most of the existing multicast routing protocols can be classified into two folders:tree-based and mesh-based.We observe that tree-based ones have high forwarding efficiency and low consumptions of bandwidth,and they may have poor robustness because only one link exists between two nodes.As a treebased multicast routing protocol,MAODV(Multicast Ad hoc On-demand Vector) shows an excellent performance in lightweight ad hoc networks.As the load of network increases,QoS(Quality of Service) is degraded obviously.In this paper,we analyze the impact of network load on MAODV protocol,and propose an optimized protocol MAODV-BB(Multicast Ad hoc On-demand Vector with Backup Branches),which improves robustness of the MAODV protocol by combining advantages of the tree structure and the mesh structure.It not only can update shorter tree branches but also construct a multicast tree with backup branches.Mathematical analysis and simulation results both demonstrate that the MAODV-BB protocol improves the network performance over conventional MAODV in heavy load ad hoc networks.     

An implementation framework for trajectory-based routing in ad hoc networks

Routing in ad hoc networks is a complicated task because of many reasons. The nodes are low-memory, low-powered, and they cannot maintain routing tables large enough for well-known routing protocols. Because of that, greedy forwarding at intermediate nodes is desirable in ad hoc networks. Also, for traffic engineering, multi-path capabilities are important. So, it is desirable to define routes at the source like in source based routing (SBR) while performing greedy forwarding at intermediate nodes.We investigate trajectory-based routing (TBR) which was proposed as a middle-ground between SBR and greedy forwarding techniques. In TBR, source encodes trajectory to be traversed and embeds it into each packet. Upon the arrival of each packet, intermediate nodes decode the trajectory and employ greedy forwarding techniques such that the packet follows its trajectory as much as possible.In this paper, we address various issues regarding implementation of TBR. We also provide techniques to efficiently forward packets along a trajectory defined as a parametric curve. We use the well-known Bezier parametric curve for encoding trajectories into packets at source. Based on this trajectory encoding, we develop and evaluate various greedy forwarding algorithms     

Explicit Multicasting for Mobile Ad Hoc Networks

In this paper we propose an explicit multicast routing protocol for mobile ad hoc networks (MANETs). Explicit multicasting differs from common approaches by listing destination addresses in data packet headers. Using the explicit destination information, the multicast routing protocol can avoid the overhead of employing its own route construction and maintenance mechanisms by taking advantage of unicast routing table. Our protocol – termed Differential Destination Multicast (DDM) – is an explicit multicast routing protocol specifically designed for MANET environment. Unlike other MANET multicasting protocols, instead of distributing membership control throughout the network, DDM concentrates this authority at the data sources (i.e. senders) thereby giving sources knowledge of group membership. In addition, differentially-encoded, variable-length destination headers are inserted in data packets which are used in combination with unicast routing tables to forward multicast packets towards multicast receivers. Instead of requiring that multicast forwarding state to be stored in all participating nodes, this approach also provides the option of stateless multicasting. Each node independently has the choice of caching forwarding state or having its upstream neighbor to insert this state into self-routed data packets, or some combination thereof. The protocol is best suited for use with small multicast groups operating in dynamic MANET environment.     

A Power-Aware Multicast Routing Protocol for Mobile Ad Hoc Networks With Mobility Prediction

A mobile ad hoc network (MANET) is a dynamically reconfigurable wireless network that does not have a fixed infrastructure. Due to the high mobility of nodes, the network topology of MANETs changes very fast, making it more difficult to find the routes that message packets use. Because mobile nodes have limited battery power, it is therefore very important to use energy in a MANET efficiently. In this paper, we propose a power-aware multicast routing protocol (PMRP) with mobility prediction for MANETs. In order to select a subset of paths that provide increased stability and reliability of routes, in routing discovery, each node receives the RREQ packet and uses the power-aware metric to get in advance the power consumption of transmitted data packets. If the node has enough remaining power to transmit data packets, it uses the global positioning system (GPS) to get the location information (i.e., position, velocity and direction) of the mobile nodes and utilizes this information to calculate the link expiration time (LET) between two connected mobile nodes. During route discovery, each destination node selects the routing path with the smallest LET and uses this smallest link expiration time as the route expiration time (RET). Each destination node collects several feasible routes and then selects the path with the longest RET value as the primary routing path. Then the source node uses these routes between the source node and each destination node to create a multicast tree. In the multicast tree, the source node will be the root node and the destination nodes will be the leaf nodes. Simulation results show that the proposed PMRP outperforms MAODV (Royer, E. M. & Perkins, C. E. (1999). In Proceedings of the ACM MOBICOM, pp. 207–218, August 1999.) and RMAODV (Baolin, S. & Layuan, L. (2005). In Proceeding of the 2005 IEEE International symposium on microwave antenna, propagation and EMC technologies for wireless communications, Vol. 2, pp. 1514–1517, August 2005.).     

Minimum-energy all-to-all multicasting in wireless ad hoc networks

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.     

Maximizing multicast lifetime in unreliable wireless ad hoc network

Multicast is an efficient method for transmitting the same packets to a group of destinations. In energy-constrained wireless ad hoc networks where nodes are powered by batteries, one of the challenging issues is how to prolong the multicast lifetime. Most of existing work mainly focuses on multicast lifetime maximization problem in wireless packet loss-free networks. However, this may not be the case in reality. In this paper, we are concerned with the multicast lifetime maximization problem in unreliable wireless ad hoc networks. To solve this problem, we first define the multicast lifetime as the number of packets transmitted along the multicast tree successfully. Then we develop a novel lifetime maximization genetic algorithm to construct the multicast tree consisting of high reliability links subject to the source and destination nodes. Simulation results demonstrate the efficiency and effectiveness of the proposed algorithm.     

QoS multicast routing by using multiple paths/trees in wireless ad hoc networks

In this paper, we investigate the issues of QoS multicast routing in wireless ad hoc networks. Due to limited bandwidth of a wireless node, a QoS multicast call could often be blocked if there does not exist a single multicast tree that has the requested bandwidth, even though there is enough bandwidth in the system to support the call. In this paper, we propose a new multicast routing scheme by using multiple paths or multiple trees to meet the bandwidth requirement of a call. Three multicast routing strategies are studied, SPT (shortest path tree) based multiple-paths (SPTM), least cost tree based multiple-paths (LCTM) and multiple least cost trees (MLCT). The final routing tree(s) can meet the user’s QoS requirements such that the delay from the source to any destination node shall not exceed the required bound and the aggregate bandwidth of the paths or trees shall meet the bandwidth requirement of the call. Extensive simulations have been conducted to evaluate the performance of our three multicast routing strategies. The simulation results show that the new scheme improves the call success ratio and makes a better use of network resources.     

LSCR:一种Mobile Ad hoc网络链路状态分组路由算法

本文提出了一种Mobile Ad hoc网络(Manet)链路状态分组路由算法(Link State-hased Cluster Routing Algo-rithm-LSCR)，该算法对Manet节点进行动态分组，每一组选举出一个具有最大度数的头结点(CH-Cluster Header)，该cH负责本组信息的管理、组内结点与组外结点之间的通信以及与其他组的CH之间交换链路状态信息等工作．本算法将改进的链路状态协议与分组路由协议有机结合，有效提高了Manet网络的路由效率．分析和实验结果表明，这种算法具有路由收敛速度快、维护成本相对较低，数据包发送成功率高，发送等待时间短等特点。     

On‐demand flow regulated routing for ad hoc wireless networks

In this paper, we present an on‐demand flow regulated routing algorithm (OFRA) for ad hoc wireless networks. The OFRA consists of two parts: an intermediate node load evaluation process and a routing path selection process. The intermediate node load evaluation process evaluates the load efficiency of the intermediate nodes according to bandwidth, data packets and computing capability. The routing path selection process selects the routing path with lower flow and fewer intermediate nodes. The OFRA can prevent intermediate nodes to be overcrowded and distribute traffic load over routing paths more evenly. The simulation result shows that the percentage of blocked routing paths is reduced and the total flow is more balanced and distributed. Copyright © 2006 John Wiley & Sons, Ltd.     

Family ACK tree (FAT): supporting reliable multicast in mobile ad hoc networks

A new protocol, called family ACK tree (FAT), is proposed to support a reliable multicast service for mobile ad hoc networks. For each reliable multicast protocol, a recovery scheme is used to ensure end-to-end delivery of unreliable multicast packets for all group members. FAT employs a tree-based recovery mechanism that localizes ACKs and retransmissions to avoid feedback implosion. To cope with node movements, FAT constructs an ACK tree on which each node maintains reachability information to three generations of nodes on the ACK tree. When a tree is fragmented due to a departed node, the fragments are glued back to the tree using the underlying multicast routing protocol. FAT then adopts an adaptive scheme to recover missed packets that have been multicast to the group during fragmentation and are not repaired by the new reliability agent. We have conducted simulations to compare the performance of FAT with existing solutions. The results show that FAT achieves better performance for the provision of reliable service in ad hoc networks, in terms of reliability, scalability, and delivery efficiency.     

基于灰狼算法的无线网络组播路由优化

针对无线网络中资源受限的组播路由问题,考虑网络节点的节点度限制和网络链路的带宽约束,以最小化组播路由开销为目标,提出了一种二进制编码方式的基于灰狼优化算法的组播路由策略.在给定的网络拓扑下,基于灰狼优化算法的组播路由策略可以迅速找到一棵包含源和目的节点的最小开销组播树.仿真结果表明,相比于遗传算法,所提出的基于灰狼优化...     

Ad hoc mobile multicast routing using the concept of long‐lived routes

Mobile ad hoc networks are recognized by their abilities to form, sustain, and deform networks on‐the‐fly without the need for any pre‐established and fixed infrastructures. This wireless multi‐hop technology requires adaptive networking protocols with low control overhead and low power consumption to operate efficiently. Existing research so far are mainly concerned with unicast routing for ad hoc mobile networks. There is a growing interest in supporting multicast communication in an ad hoc mobile environment. In this paper, the associativity‐based ad hoc multicast (ABAM) routing protocol is proposed. The concept of association stability is utilized during multicast tree discovery, selection, and reconfiguration. This allows routes that are long‐lived to be selected, thereby reducing the frequency of route reconstructions. ABAM employs a localized route reconstruction strategy in response to migrations by source, receiver, and tree nodes. It can repair an affected subtree via a single route reconstruction operation. ABAM is robust since the repair can be triggered by a node in the tree or by the migrated node itself. ABAM is also capable of handling multicast group dynamics when mobile hosts decide to join and leave an existing multicast group. Our simulation results reveal that under different mobility scenarios and multicast group size, ABAM has low communication overhead and yields better throughput performance. Copyright © 2001 John Wiley & Sons, Ltd.     

Opportunistic media access control and routing for delay-tolerant mobile ad hoc networks

In delay-tolerant mobile ad hoc networks, motion of network nodes, network sparsity and sporadic density can cause a lack of guaranteed connectivity. These networks experience significant link delay and their routing protocols must take a store-and-forward approach. In this paper, an opportunistic routing protocol is proposed, along with its compatible media access control, for non-real-time services in delay-tolerant networks. The scheme is mobility-aware such that each network node needs to know its own position and velocity. The media access control employs a four-fold handshake procedure to probe the wireless channel and cooperatively prioritize candidate nodes for packet replication. It exploits the broadcast characteristic of the wireless medium to utilize long-range but unreliable links. The routing process seizes opportunities of node contacts for data delivery. It takes a multiple-copy approach that is adaptive with node movements. Numerical results in mobile ad hoc networks and vehicular ad hoc networks show superior performance of the proposed protocol compared with other routing protocols. The mobility-aware media access control and routing scheme exhibits relatively small packet delivery delay and requires a modest amount of total packet replications/transmissions.     

AMRoute: Ad Hoc Multicast Routing Protocol

The Ad hoc Multicast Routing protocol (AMRoute) presents a novel approach for robust IP Multicast in mobile ad hoc networks by exploiting user-multicast trees and dynamic logical cores. It creates a bidirectional, shared tree for data distribution using only group senders and receivers as tree nodes. Unicast tunnels are used as tree links to connect neighbors on the user-multicast tree. Thus, AMRoute does not need to be supported by network nodes that are not interested/capable of multicast, and group state cost is incurred only by group senders and receivers. Also, the use of tunnels as tree links implies that tree structure does not need to change even in case of a dynamic network topology, which reduces the signaling traffic and packet loss. Thus AMRoute does not need to track network dynamics; the underlying unicast protocol is solely responsible for this function. AMRoute does not require a specific unicast routing protocol; therefore, it can operate seamlessly over separate domains with different unicast protocols. Certain tree nodes are designated by AMRoute as logical cores, and are responsible for initiating and managing the signaling component of AMRoute, such as detection of group members and tree setup. Logical cores differ significantly from those in CBT and PIM-SM, since they are not a central point for data distribution and can migrate dynamically among member nodes. Simulation results (using ns-2) demonstrate that AMRoute signaling traffic remains at relatively low level for typical group sizes. The results also indicate that group members receive a high proportion of data multicast by senders, even in the case of a highly dynamic network.     

SMORT: Scalable multipath on-demand routing for mobile ad hoc networks

Increasing popularity and availability of portable wireless devices, which constitute mobile ad hoc networks, calls for scalable ad hoc routing protocols. On-demand routing protocols adapt well with dynamic topologies of ad hoc networks, because of their lower control overhead and quick response to route breaks. But, as the size of the network increases, these protocols cease to perform due to large routing overhead generated while repairing route breaks. We propose a multipath on-demand routing protocol (SMORT), which reduces the routing overhead incurred in recovering from route breaks, by using secondary paths. SMORT computes fail-safe multiple paths, which provide all the intermediate nodes on the primary path with multiple routes (if exists) to destination. Exhaustive simulations using GloMoSim with large networks (2000 nodes) confirm that SMORT is scalable, and performs better even at higher mobility and traffic loads, when compared to the disjoint multipath routing protocol (DMRP) and ad hoc on-demand distance vector (AODV) routing protocol.     

Moralism: mobility prediction with link stability based multicast routing protocol in MANETs

In recent research, link stability is getting tremendous attention in mobile adhoc networks (MANETs), because of several impediments that occur in a reliable and robust network. Link stability metric is used to improve network performance in terms of end-to-end delay, data success delivery ratio (DSDR) and available route time (ART). Energy consumption, bandwidth and communication delay of major concern in ad hoc networks. A high mobility of MANET nodes reduces the reliability of network communication. In a dynamic networks, high mobility of the nodes makes it very difficult to predict the dynamic routing topology and hence cause route/link failures. Multicast in MANETs is an emerging trend that effectively improves the performance while lowering the energy consumption and bandwidth usage. Multicast routing protocol transmits a packet to multicast a group at a given time instant to achieve a better utilization of resources. In this paper, node mobility is considered to map better their movement in the network. So, the links with long active duration time can be identified as a stable link for route construction. Variation in signal strength is used to identify whether the direction of the node is towards or away from estimating node. We consider signal strength as QoS metric to calculate link stability for route construction. Efforts are made to identify the link with highly probable longer lifetime as the best suitable link between two consecutive nodes. We predict the movement time of nodes that define the route path to the node destination. Exata/cyber simulator is used for network simulation. The simulation results of the proposed routing protocol are compared with on-demand multicast routing protocol and E-ODMRP, which works on minimum hop count path. Analysis of our simulation results has shown improvement of various routing performance metrics such as DSDR, ART, routing overhead and packet drop ratio.     

一种基于跨层设计和蚁群优化的自组网负载均衡路由协议

针对大部分现有替代路径共同存在的替代路径老化和构建效率问题,本文提出了一种基于跨层设计和蚁群优化的负载均衡路由协议(CALRA),利用蚁群优化算法特有的信息素挥发方法实现对替代路径的老化问题,将蚁群优化和跨层优化方法结合起来解决自组网中的负载均衡问题,通过双向逐跳更新的方式较好的解决了替代路径构建效率问题,并将蚂蚁在所经过的各中间节点为路由表带来的信息素增量映射为蚂蚁离开源节点的距离、移动过程中所遇到的节点拥塞程度、节点当前信息素浓度和节点移动速度等各协议层的统计信息的函数,通过对各种信息所对应的参数赋予不同加权值的方法对概率路由表进行控制,改善了自组网中现有基于蚁群优化的路由协议中普遍存在的拥塞问题、捷径问题、收敛速度问题和引入的路由开销问题.仿真表明,CALRA在分组成功递交率、路由开销、端到端平均时延等方面具有优良性能,能很好地实现网络中的业务负载均衡.     

Scalable Routing Protocol for Ad Hoc Networks

In this paper we present a scalable routing protocol for ad hoc networks. The protocol is based on a geographic location management strategy that keeps the overhead of routing packets relatively small. Nodes are assigned home regions and all nodes within a home region know the approximate location of the registered nodes. As nodes travel, they send location update messages to their home regions and this information is used to route data packets. In this paper, we derive theoretical performance results for the protocol and prove that the control packet overhead scales linearly with node speed and as N ^3/2 with increasing number of nodes. These results indicate that our protocol is well suited to relatively large ad hoc networks where nodes travel at high speed. Finally, we use simulations to validate our analytical model.     

QoS multicast routing in cognitive radio ad hoc networks

In this paper, we discussed the issues of QoS multicast routing in cognitive radio ad hoc networks. The problem of our concern was: given a cognitive radio ad hoc network and a QoS multicast request, how to find a multicast tree so that the total bandwidth consumption of the multicast is minimized while the QoS requirements are met. We proposed two methods to solve it. One is a two‐phase method. In this method, we first employed a minimal spanning tree‐based algorithm to construct a multicast tree and then proposed a slot assignment algorithm to assign timeslots to the tree links such that the bandwidth consumption of the tree is minimized. The other is an integrated method that considers the multicast routing together with the slot assignment. Extensive simulations were conducted to show the performance of our proposed methods. Copyright © 2011 John Wiley & Sons, Ltd.