A hierarchical approach to position-based multicast for mobile ad-hoc networks

In this paper we present Scalable Position-Based Multicast (SPBM), a multicast routing protocol for ad-hoc networks. SPBM uses the geographic position of nodes to provide a highly scalable group membership scheme and to forward data packets in a way that is very robust to changes in the topology of the network. SPBM bases the forwarding decision on whether or not there are group members located in a given direction, allowing a hierarchical aggregation of membership information. The farther away a region is from an intermediate node, the higher the level of aggregation for this region should be. Because of aggregation, the overhead for group membership management scales logarithmically with the number of nodes and is independent of the number of multicast senders for a given multicast group. Furthermore, we show that group management overhead is bounded by a constant if the frequency of membership updates is scaled down with the aggregation level. This scaling of the update frequency is reasonable since the higher the level of aggregation is, the lower the number of membership changes for the aggregate will be. The performance of SPBM is investigated by means of simulation, including a comparison with ODMRP, and through mathematical analysis. We also describe an open source kernel implementation of SPBM that has been successfully deployed on hand-held computers.     

A self-healing On-demand Geographic Path Routing Protocol for mobile ad-hoc networks

We present a self-healing On-demand Geographic Path Routing Protocol (OGPR) for mobile ad-hoc networks. OGPR is an efficient, stateless, and scalable routing protocol that inherits the best of the three well-known techniques for routing in ad-hoc networks, viz., greedy forwarding, reactive route discovery, and source routing. In OGPR protocol, source nodes utilize the geographic-topology information obtained during the location request phase to establish geographic paths to their respective destinations. Geographic paths decouple node ID’s from the paths and are immune to changes in the network topology. Further, they help nodes avoid dead-ends due to greedy forwarding. To utilize geographic paths even in sparser networks, OGPR uses a path-healing mechanism that helps geographic paths adapt according to the network topology. We present extensions to OGPR protocol to cope with networks containing unidirectional links. Further, we present results from an extensive simulation study using GloMoSim. Simulation results show that OGPR achieves higher percentage packet delivery and lower control overhead, compared to a combination of GPSR+GLS protocols, AODV, and DSR under a wide range of network scenarios.     

A framework for the multicast lifetime maximization problem in energy-constrained wireless ad-hoc networks

We consider the problem of maximizing the lifetime of a given multicast connection in wireless networks that use directional antennas and have limited energy resources. We provide a globally optimal solution to this problem for a special case of using omni-directional antennas. This graph theoretic approach provides us insights into more general case of using directional antennas, and inspires us to produce a group of heuristic algorithms. Experimental results show that our algorithms outperform other energy-aware multicast algorithms significantly in terms of multicast lifetime.

Distributed formation of core-based forwarding multicast trees in mobile ad hoc networks

A core-based forwarding multicast tree is a shortest path tree rooted at core node that distributes multicast packets to all group members via the tree after the packets are sent to the core. Traditionally, the bandwidth cost consumed by transmitting a packet from the core via the tree is evaluated by the total weights of all the edges. And, the bandwidth cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcast operation is used to multicast a packet, we found that the bandwidth cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum bandwidth cost only when the core is not a leaf, it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P = NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically reduce the number of non-leaves in the multicast tree. Experimental results show that the multicast tree after the execution of our method has smaller number of non-leaves than others in the geometrically distributed network model.     

Energy-saving scheduling for LTE multicast services

In the Long Term Evolution （LTE） downlink multicast scheduling, Base Station （BS） usually allocates transmit power equally among all Resource Blocks （RBs）, it may cause the waste of transmit power. To avoid it, this paper put forward a new algorithm for LTE multicast downlink scheduling called the Energy-saving based Inter-group Proportional Fair （EIPF）. The basic idea of EIPF is to calculate an appropriate transmitting power for each group according to its data rate respectively, and then follow the inter-group proportional fair principle to allocate RBs among multicast groups. The results of EIPF simulation show that the proposed algorithm not only can reduce the transmit power of BS effectively but also improve the utilization rate of energy.     

Topology based placement of multicast capable nodes for supporting efficient multicast communication in WDM optical networks

Most existing algorithms for the problem of optical signal splitter placement or multicast splitting-capable node placement in a WDM network are based on the performance of attempting a large set of randomly generated multicast sessions in the network. Experiments show that placement of multicast capable nodes based on their importance for routing one set of multicast sessions may not be a right choice for another set of multicast sessions. In this work, we propose placement algorithms that are based on network topology and the relative importance of a node in routing multicast sessions, which is measured by our proposed metrics. Since a network topology is fixed once given, the proposed algorithms are essentially network traffic independent. We evaluate the proposed placement algorithms given static sets of multicast sessions as well as under dynamic traffic conditions, which are routed using our splitter constrained multicast routing algorithm. Our results show that the proposed algorithms perform better, compared to existing algorithms.     

Quantified Cost-Balanced routing scheme for overlay multicast

This paper focuses on the quantitative analysis issue of the routing metrics tradeoff problem, and presents a Quantified Cost-Balanced overlay multicast routing scheme （QCost-Balanced） to the metric tradeoff problem between overlay path delay and access bandwidth at Multicast Server Nodes （MSN） for real-time applications over Internet. Besides implementing a dynamic priority to MSNs by weighing the size of its service clients for better efficiency, QCost-Balanced tradeoffs these two metrics by a unified tradeoff metric based on quantitative analysis. Simulation experiments demonstrate that the scheme achieves a better tradeoff gain in both two metrics, and effective performance in metric quantitative control.     

A mobile bazaar for wide-area wireless services

We introduce MoB, an infrastructure for collaborative wide-area wireless data services. MoB proposes to change the current model of data services in the following fundamental ways: (1) it decouples infrastructure providers from services providers and enables fine-grained competition, (2) it allows service interactions on arbitrary timescales, and, (3) it promotes flexible composition of these fine-grained service interactions based on user and application needs. At the heart of MoB is an open market architecture in which mobile users can opportunistically trade various services with each other in a flexible manner. In this paper we first describe the overall architecture of MoB including various enablers like user reputation management, incentive management, and accounting services. We next present our experience from both simulations as well as our prototype implementation of MoB in enhancing application performance in multiple different scenarios—file transfers, web browsing, media streaming, and location-enhanced services. This work is supported in part by NSF grants CNS-0520152, CNS-0639434, CNS-0627589 and CNS-0627102. Rajiv Chakravorty received the B.E. degree from Nagpur University, Nagpur, India, in 1997 and the M.Tech. degree form the Indian Institute of Technology, Delhi in 1999. He is working towards the Ph.D. degree at the Computer Laboratory, University of Cambridge, U.K. In 2005 he was a visiting research scholar in the Department of Computer Sciences, University of Wisconsin, Madison. He has worked with Philips Research, ASA Laboratories, Eindhoven, The Netherlands. He also pursued research at ComNets, RWTH-Aachen, Germany. His current interests include mobile and wireless systems, and networking. He is a recipient of DAAD Scholarship Award from Germany, and the Sun Microsystems Scholarship and the Hughes Hall Commonwealth scholarhip from Cambridge Univeristy. Sulabh Agarwal received the B.Tech. degree in Computer Science and Engineering from Indian Institute of Technology, Delhi in 2000, and the M.S. degree in Computer Science from University of Maryland, College Park in 2002. His research interest is in the area of computer networking. Suman Banerjee received the B.Tech. degree in Computer Science and Engineering from Indian Institute of Technology, Kanpur in 1996, and the M.S. and the Ph.D. degrees in Computer Science from University of Maryland, College Park in 1999 and 2003 respectively. He is an Assistant Professor of Computer Sciences at University of Wisconsin-Madison and heads the Wisconsin Wireless and NetworkinG Systems (WiNGS) laboratory. His broad research interests are in the areas of networking and distributed systems with a special focus in the area of wireless and mobile networking systems. Ian Pratt received the Ph.D. in Computer Science from University of Cambridge, Cambridge, U.K. He was elected a Fellow of King’s College, Cambridge, U.K., in 1996. He is a Senior Faculty member at the Computer Loboratory, University of Cambridge, Cambridge, U.K. He is a a leader of the Systems Research Group, where he has been architect of a number of influential projects, including the Desk Area Network workstation, the Cambridge Open Mobile System, the Xen Virtual Machine Monitor, and the XenoServer infrastructure for global computing. His research interests cover a broad range if systems topics, including computer architecture, operating system design, mobile systems, and networking.     

Protocol-independent multicast packet delivery improvement service for mobile Ad hoc networks

This paper addresses the issue of improving multicast packet delivery in mobile ad hoc networks and proposes an adaptive mechanism called Protocol-Independent Packet Delivery Improvement Service (PIDIS) to recover lost multicast packets. PIDIS provides its packet-delivery improvement services to any multicast routing protocol for mobile ad hoc networks by exploiting the mechanism of swarm intelligence to make intelligent decisions about where to fetch the lost multicast packets from. PIDIS is a gossip protocol, and nodes using PIDIS are only concerned with which neighbor nodes to gossip with to recover the most lost packets, rather than which member nodes to gossip with. Thus, it does not rely on membership information in a multicast scenario, which is often difficult to get. PIDIS employs the beneficial aspects of probabilistic routing and adapts well to mobility. PIDIS achieves probabilistic improvement in multicast packet delivery and, unlike other gossip-based schemes, does not need to maintain information about group members from which lost multicast packets are retrieved. Further, the operations of PIDIS do not rely on any underlying routing protocol or primitive, and can be incorporated into any ad hoc multicast routing protocol. We incorporated PIDIS over ODMRP [On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks, Kluwer Mobile Networks and Applications, 2000], and compared it against Anonymous Gossip (AG) [International Conference on Distributed Computing Systems (ICDCS 2001) Phoenix, Arizona, April 2001] implemented over ODMRP, and ODMRP itself. Our simulation results show that ODMRP + PIDIS is more efficient and performs better than ODMRP + AG and ODMRP in terms of multicast packet delivery, end-to-end delay, and MAC layer overheads. We attribute the better performance and lower MAC overheads of ODMRP + PIDIS to the efficient gossiping made possible by using the swarm intelligence techniques.     

基于不同移动模型的移动自组网多播路由协议性能研究

为了研究移动自组网中多播路由协议在不同移动模型下的性能,选取随机路点移动模型、高斯马尔科夫移动模型和参考点组移动模型,将三种移动模型的移动场景加入到NS2中,对基于部分网络编码的实时多播协议PNCRM进行仿真.结果表明,PNCRM协议在随机路点移动模型和高斯马尔科夫移动模型中的数据包投递率明显高于参考点组移动模型,但是参考点组移动模型的总开销和端到端延时是最优的.这样我们就可以根据不同的性能指标要求选择合适的移动模型.     

一种新的QoS组播路由算法

针对现有的求解多约束QoS组播路由中存在的问题,结合BP神经网络局部搜索的优势和蚁群算法全局搜索的优势的特点,进行QoS组播路由算法的设计,提出了一种新型的NNAC算法。该算法通过BP神经网络寻找路径的更优解,改善了QoS组播路由路径寻找的方法。通过实验仿真表明,NNAC算法得到最优组播树的总延时为35,总代价费用为21,在完成150个度约束组播路由路径时,NNAC算法在进行最优组播树的寻找成功率上高于AC算法,同时该算法还克服了AC算法易陷入局部最小点的不足。     

QoS-based multicast routing optimization algorithms for Internet

Most of the multimedia applications require strict Quality-of-Service （QoS） guarantee during the communication between a single source and multiple destinations. The paper mainly presents a QoS Multicast Routing algorithms based on Genetic Algorithm （QMRGA）. Simulation results demonstrate that the algorithm is capable of discovering a set of QoS-based near optimized, non-dominated multicast routes within a few iterations, even for the networks environment with uncertain parameters.     

Dynamic agent-based hierarchical multicast for wireless mesh networks

We propose and analyze a multicast algorithm named Dynamic Agent-based Hierarchical Multicast (DAHM) for wireless mesh networks that supports user mobility and dynamic group membership. The objective of DAHM is to minimize the overall network cost incurred. DAHM dynamically selects multicast routers serving as multicast agents for integrated mobility and multicast service management, effectively combining backbone multicast routing and local unicast routing into an integrated algorithm. As the name suggests, DAHM employs a two-level hierarchical multicast structure. At the upper level is a backbone multicast tree consisting of mesh routers with multicast agents being the leaves. At the lower level, each multicast agent services those multicast group members within its service region. A multicast group member changes its multicast agent when it moves out of the service region of the current multicast agent. The optimal service region size of a multicast agent is a critical system parameter. We propose a model-based approach to dynamically determine the optimal service region size that achieves network cost minimization. Through a comparative performance study, we show that DAHM significantly outperforms two existing baseline multicast algorithms based on multicast tree structures with dynamic updates upon member movement and group membership changes.     

Collaborative techniques for intrusion detection in mobile ad-hoc networks

In this paper, we present two intrusion detection techniques for mobile ad-hoc networks, which use collaborative efforts of nodes in a neighborhood to detect a malicious node in that neighborhood. The first technique is designed for detection of malicious nodes in a neighborhood of nodes in which each pair of nodes in the neighborhood are within radio range of each other. Such a neighborhood of nodes is known as a clique [12]. The second technique is designed for detection of malicious nodes in a neighborhood of nodes, in which each pair of nodes may not be in radio range of each other but where there is a node among them which has all the other nodes in its one-hop vicinity. This neighborhood is identical to a cluster as mentioned in [12]. Both techniques use message passing between the nodes. A node called the monitor node initiates the detection process. Based on the messages that it receives during the detection process, each node determines the nodes it suspects to be malicious and send votes to the monitor node. The monitor node upon inspecting the votes determines the malicious nodes from among the suspected nodes. Our intrusion detection system is independent of any routing protocol. We give the proof of correctness of the first algorithm, which shows that it correctly detects the malicious nodes always when there is no message loss. We also show with the help of simulations that both the algorithms give good performance even when there are message losses arising due to unreliable channel.     

An improved quantum-inspired evolutionary algorithm for coding resource optimization based network coding multicast scheme

This paper investigates how to minimize the required coding resources in network-coding-based multicast scenarios. An evolutionary algorithm (MEQEA) is proposed to address the above problem. Based on quantum-inspired evolutionary algorithm (QEA), MEQEA introduces multi-granularity evolution mechanism which allows different chromosomes, at each generation, to have different rotation angle step values for update. In virtue of this mechanism, MEQEA significantly improves its capability of exploration and exploitation, since its optimization performance is no longer overly dependant upon the single rotation angle step scheme shared by all chromosomes. MEQEA also presents an adaptive quantum mutation operation which is able to prevent local search efficiently. Simulations are carried out over a number of network topologies. The results show that MEQEA outperforms other heuristic algorithms and is characterized by high success ratio, fast convergence, and excellent global-search capability.     

Fairness of sharing protection for multicast in WDM networks

In this paper, the sharing schemes of multicast in survivable Wavelength-Division Multiplexed （WDM） networks are studied and the concept of Shared Risk Link Group （SRLG） is considered. While the network resources are shared by the backup paths, the sharing way is possible to make the backup paths selfish. This selfishness leads the redundant hops of the backup route and a large number of primary lightpaths to share one backup link. The sharing schemes, especially, the self-sharing and cross-sharing, are investigated to avoid the selfishness when computing the backup light-tree. In order to decrease the selfishness of the backup paths, it is important to make the sharing links fair to be used. There is a trade-off between the self-sharing and cross-sharing, which is adjusted through simulation to adapt the sharing degree of each sharing scheme and save the network resources.     

A two-layer recurrent Neural Network based approach for overlay multicast

Overlay multicast has become one of the most promising multicast solutions for IP network, and Neutral Network（NN） has been a good candidate for searching optimal solutions to the constrained shortest routing path in virtue of its powerful capacity for parallel computation. Though traditional Hopfield NN can tackle the optimization problem, it is incapable of dealing with large scale networks due to the large number of neurons. In this paper, a neural network for overlay multicast tree computation is presented to reliably implement routing algorithm in real time. The neural network is constructed as a two-layer recurrent architecture, which is comprised of Independent Variable Neurons （IDVN） and Dependent Variable Neurons （DVN）, according to the independence of the decision variables associated with the edges in directed graph. Compared with the heuristic routing algorithms, it is characterized as shorter computational time, fewer neurons, and better precision.     

Location aided probabilistic broadcast algorithm for mobile Ad-hoc network routing

On-demand routing protocols are widely used in mobile Ad-hoc network (MANET). Flooding is an important dissemination scheme in routing discovering of on-demand routing protocol. However, in high-density MANET redundancy flooding packets lead to dramatic deterioration of the performance which calls broadcast storm problem (BSP). A location-aided probabilistic broadcast (LAPB) algorithm for routing in MANET is proposed to reduce the number of routing packets produced by flooding in this paper. In order to reduce the redundancy packets, only nodes in a specific area have the probability, computed by location information and neighbor knowledge, to propagate the routing packets. Simulation results demonstrate that the LAPB algorithm can reduce the packets and discovery delay (DD) in the routing discovery phase.     

Distributed trajectory design for data gathering using mobile sink in wireless sensor networks

Several studies have demonstrated the benefits of using a mobile sink (MS) to reduce energy consumption resulting from multi-hop data collection using a static sink in wireless sensor networks (WSNs). However, using MS may increase data delivery latency as it needs to visit each sensor node in the network to collect data. This is a critical issue in delay-sensitive applications where all sensed data must be gathered within a given time constraint. In this paper, we propose a distributed data gathering protocol utilizing MS for WSNs. The proposed protocol designs a trajectory for the MS, which minimizes energy consumption and delay. Our protocol operates in four main phases: data sensing, rendezvous point (RP) selection, trajectory design, and data gathering. In data sensing, a number of deployed sensor nodes keep sensing the target field for a specific period of time to capture events. Then, using a cluster-based RP selection algorithm, some sensor nodes are selected to become RPs based on local information. The selected RPs are then used to determine a trajectory for the MS. To do so, we propose three trajectory design algorithms that support different types of applications, namely reduced energy path (REP), reduced delay path (RDP), and delay bound path (DBP). The MS moves through the constructed path to accomplish its data gathering according to an effective scheduling technique that is introduced in this work. We validate the proposed protocol via extensive simulations over several metrics such as energy, delay, and time complexity.     

求解超定线性方程组L_1─范数最优解的神经网络方法

基于线性规划对偶理论，本文给出一种求解超定线性方程组Ｌ１─范数解的神经网络方法。这一方法由两部分组成，首先利用ＬＳＳＭ神经网络求出Ｌ１问题的近似对偶解，然后利用改进的Ｔ－Ｈ网络求Ｌ１─问题的解，当参数选择适当时，Ｔ－Ｈ网络的全局渐近稳定点就是问题的精确解，模拟试验也表明了这一方法的可行性。