Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks

In this paper, the well-known network backbone formation problem is modeled as the stochastic min-degree constrained minimum spanning tree (md-MST) problem, where the link duration is associated with the edge weight. Then, a decentralized learning automata-based algorithm is proposed to form the most stable backbone of the wireless mobile ad hoc network (MANET) by finding a near optimal solution to the stochastic md-MST problem of the network topology graph. The proposed method significantly decreases the network overhead and shortens the network delay by reducing the number of intermediate forwarding hosts. It also extends the backbone lifetime by selection of the links with the maximum expected duration. The convergence of the proposed algorithm to the most stable network backbone is proven on the basis of the Martingale theorem. Several simulation experiments are conducted to investigate the efficiency of the proposed backbone formation algorithm. Numerical results show the superiority of the proposed method over the existing methods in terms of the backbone lifetime, end-to-end delay, backbone size, packet delivery ratio, and control message overhead.     

移动自组织网与有线网融合技术研究与展望

随着移动自组织网络(MANET)组网技术的不断成熟,MANET路由协议与传统Internet路由协议的融合已经成为网络互联的重要内容,成为影响组网效率的决定性因素.本文分别对移动自组织网络作为末端网和承载网的互联技术进行了研究,并在此基础上提出了基于无线栅格网络(wireless mesh networl,WMN)结构的未来移动互联技术的演进方案,对WMN的路由协议进行了有意义的探讨.     

Virtual Backbone Construction in MANETs Using Adjustable Transmission Ranges

Recently, the use of a virtual backbone in various applications in mobile ad hoc networks (MANETs) has become popular. These applications include topology management, point and area coverage, and routing protocol design. In a MANET, one challenging issue is to construct a virtual backbone in a distributed and localized way while balancing several conflicting objectives: small approximation ratio, fast convergence, and low computation cost. Many existing distributed and localized algorithms select a virtual backbone without resorting to global or geographical information. However, these algorithms incur a high computation cost in a dense network. In this paper, we propose a distributed solution based on reducing the density of the network using two mechanisms: clustering and adjustable transmission range. By using adjustable transmission range, we also achieve another objective, energy-efficient design, as a by-product. As an application, we show an efficient broadcast scheme where nodes (and only nodes) in a virtual backbone are used to forward the broadcast message. The virtual backbone is constructed using Wu and Li's marking process [37] and the proposed density reduction process. The application of the density reduction process to other localized algorithms is also discussed. The efficiency of our approach is confirmed through both analytical and simulation study.     

A virtual multiple message ferry backbone routing scheme for mobile ad-hoc networks

A MANET (Mobile Ad-Hoc Network) consists of relocating wireless communication devices without infrastructure installed in its network environment. Due to the mobility of the devices, the network topology changes frequently and consequently results in poor network performance. When the density of nodes in a MANET is sparse, the performance becomes even worse due to the intermittent connected routing problem arising. To cope with this problem, this paper integrates mechanisms of Virtual Multiple Message Ferry Routing (VMMFR) and Virtual Multiple Message Ferry Dispatch Scheduling (VMMFDS) into the routing protocol design of MANETs and proposes a Virtual Multiple Message Ferry Backbone Routing (VMMFBR) scheme for MANETs. Several simulations have been conducted using the network simulator NS-2 to evaluate the performance of the proposed VMMFR mechanism. Due to the VMMFR mechanism providing a reliable and predictable backbone routing for MANETs communications. The results show that the proposed method has a higher packet delivery ratio, low bandwidth consumed, and that there is greater precision of packet delivery time, compared to the traditional MANETs routing protocols (AOMDV and DSR). In addition, some theoretical results for the proposed VMMFDS mechanism to minimize the transfer waiting time are also given in this paper.     

无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.     

Structure virtuelle pour une auto-organisation dans les réseaux ad hoc et hybrides

Ad hoc networks are spontaneous wireless networks without any wired infrastructure of mobile terminals. We assume that an efficient network is achieved through a self-organization. Thus, we propose here a virtual structure allowing a self-organization, constituted by both a backbone and services areas. The backbone constitutes a connected structure to gather and disseminate the control traffic, representing a natural prolongation of backbone in wired networks. Services areas structure the network in separating the network in homogeneous zones managed by a clusterhead. Since terminals are mobile, we propose both construction and maintenance procedures in order to maintain an efficient and stable virtual structure, during all the network life, in order to create a stable virtual structure, we introduce a stability metric, depending on several criteria. Finally, a power-energy saving solution is proposed to optimize the network lifetime.     

Adaptive Filtering Algorithm in Clock Calibration System

In wireless sensor network (WSN), data transfer from source to the destination needs an optimized network with less energy consumption. However, the optimized network with connected dominating set (CDS) of graph theory plays an important role in WSN for virtual backbone network formation. The connected dominating set is NP-hard problem with larger in size. However, the problem of the size of the network and NP-hard makes the researchers concentrate to improve the algorithms for virtual backbone. In this paper, we propose a semigraph contiguous prevalent set (SCPS) algorithm for semigraph structure to reduce NP-hard and size of the virtual backbone. The virtual back bone with SCPS algorithm applies with various protocols such as AODV, DSR, and DSDV for performance evaluation. From simulation result, we observe the network parameters such as size, diameter, average hoping and waiting time between the nodes are reduced. The proposed SCPS construction method retains the best performance ratio of \((2 + \ln \Delta_{a} )|opt|,\) whereas \(|opt|\) is the size of any optimal adjacent dominating set (ADS) and \(\Delta_{a}\) is the maximum adjacent degree of all nodes of the network and has the low time complexity of O(n ² ), whereas n denotes the network size. Furthermore, the proposed SCPS virtual backbone in hardware implementation proves the network life time increases about 86% of 9 V battery of the node.     

Constructing a MANET Based on Clusters

This paper proposes a scheme for constructing a mobile ad hoc network (MANET) based on clusters. The proposed MANET architecture is made up of two hierarchies. One hierarchy is the backbone network which is made up of cluster heads and associate nodes, and the other hierarchy is the cluster which is made up of one cluster head and multiple cluster members. In the proposed cluster generation algorithm, the number of potential cluster members is used as a metric, and it is always the new node with the maximum number of potential cluster members that is elected as a cluster head. In this way, the number of cluster heads is minimized. In this scheme, only one associate node is used to achieve the communication between two cluster heads, so the number of nodes included in the backbone network is minimized. This scheme also proposes the cluster merging algorithm in order to maintain the minimum number of cluster heads. In the proposed cluster repair algorithm, if a cluster head fails/moves out of the cluster, then a new cluster head is elected to maintain the cluster stability. From the perspective of the cluster stability, this paper analyzes the performance parameters of the proposed scheme, and the data results show that the proposed scheme improves the MANET stability.     

Bandwidth-satisfied multicast trees in large-scale ad-hoc networks

The purpose of this paper is to construct bandwidth-satisfied multicast trees for QoS applications in large-scale ad-hoc networks (MANETs). Recent routing protocols and multicast protocols in large-scale MANETs adopt two-tier infrastructures to avoid the inefficiency of the flooding. Hosts with a maximal number of neighbors are often chosen as backbone hosts (BHs) to forward packets. Most likely, these BHs will be traffic concentrations/bottlenecks of the network. In addition, since host mobility is not taken into consideration in BH selection, these two-tier schemes will suffer from more lost packets if highly mobile hosts are selected as BHs. In this paper, a new multicast protocol is proposed for partitioning large-scale MANET into two-tier infrastructures. In the proposed two-tier multicast protocol, hosts with fewer hops and longer remaining connection time to the other hosts will be selected as BHs. The objective is not only to obtain short and stable multicast routes, but also to construct a stable two-tier infrastructure with fewer lost packets. Further, previous MANET quality-of-service (QoS) routing/multicasting protocols determined bandwidth-satisfied routes for QoS applications. Some are implemented as a probing scheme, but the scheme is inefficient due to high overhead and slow response. On the contrary, the others are implemented by taking advantage of routing and link information to reduce the inefficiency. However, the latter scheme suffers from two bandwidth-violation problems. In this paper, a novel algorithm is proposed to avoid the two problems, and it is integrated with the proposed two-tier multicast protocol to construct bandwidth-satisfied multicast trees for QoS applications in large-scale MANETs. The proposed algorithm aims to achieve better network performance by minimizing the number of forwarders in a tree.     

An efficient algorithm for backbone construction in cognitive radio networks

Numerous research articles exist for backbone formation in wireless networks; however, they cannot be applied straightforward in cognitive radio network (CRN) due to its peculiar characteristics. Since virtual backbone has many advantages such as reduced routing overhead, dynamic maintenance, and fast convergence speed, we intend to propose a backbone formation protocol in CRN. In this paper, we propose a tree‐based backbone formation protocol along with its maintenance. Our protocol is based on non‐iterative approach, thus leading towards limited message overhead and faster convergence speed. The proposed algorithm first forms the tree by maintaining the parent‐child relationship, and second, the parent nodes are connected together to form the virtual backbone. In the end, we evaluate the performance our protocol through extensive simulations.     

基于代数连通度的虚拟骨干网构造方法

随着无线传感器网络的大量运用,通过分级将网络规模缩小显得十分必要。与已有的一些无线传感器网络的分簇算法不同,本文旨在构造一个健壮的、稳定的虚拟骨干网。通过引入图论中的代数连通度,并考虑无线传感器网络的信道特性,使用基于连接概率的代数连通度来表征虚拟骨干网的健壮性。同时提出度量参数网络质量,结合考虑骨干网的健壮性与代价,通过调节参数因子进行健壮性与代价因素之间的权衡。对该网络优化问题,提出集中式算法进行求解,并通过仿真得到健壮的虚拟骨干网。     

基于计时器的最小连通支配集生成算法

在分簇的MANET中,基于计时器思想提出最小连通支配集生成算法,实现动态拓扑下骨干网构建与重构,证明了算法正确性。仿真结果表明,该算法能以少量消息开销,生成较小连通支配集,快速调整骨干网适应拓扑变化。     

On Construction of Virtual Backbone in Wireless Ad Hoc Networks with Unidirectional Links

Since there is no fixed infrastructure in wireless ad hoc networks , virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem. The virtual backbone construction has been studied extensively in {em undirected} graphs, especially in unit disk graphs, in which each node has the same transmission range. In practice, however, transmission ranges of all nodes are not necessarily equal. In this paper, we model such a network as a disk graph, where unidirectional links are considered. To study the virtual backbone construction in disk graphs, we consider two problems: Strongly Connected Dominating Set (SCDS) and Strongly Connected Dominating and Absorbing Set (SCDAS). We propose a constant approximation algorithm and discuss its improvements for the SCDS problem . We also propose a heuristic for the SCDAS problem. Through extensive simulations, we verify our theoretical analysis and also demonstrate that the SCDS can be extended to form an SCDAS with marginal extra overhead.     

Immune Algorithm for Solving the Optimization Problems of Computer Communication Networks

The basic problem in optimizing communication networks is to assign a proper circuit for each origindestination pair in networks so as to minimize the average network delay, and the network optimal route selection model is a multi-constrained 0-1 nonlinear programming problem. In this paper, a new stochastic optimization algorithm, Immune Algorithm, is applied to solve the optimization problem in communication networks. And the backbone network vBNS is chosen to illustrate the technique of evaluating delay in a virtual network. At last, IA is compared with the optimization method in communication networks based on Genetic Algorithm, and the result shows that IA is better than GA in global optimum finding.     

基于自组网的节能协作算法

自组网是兼做路由器的移动节点组成的移动无线网络，不依靠通信基础设施。本文提出了一个工作于物理层和MAC层之上、网络层之下的基于自组网的节能协作算法，其核心思想是构造虚拟主干网，使位于虚拟主干网外的节点工作于休眠状态，从而减少电源消耗。     

SDR: A Stable Direction-Based Routing for Vehicular Ad Hoc Networks

A stable and reliable routing mechanism for vehicular ad hoc networks (VANETs) is an important step toward the provision of long data transmission applications, such as file sharing and music download. Traditional mobile ad hoc network (MANET) routing protocols are not suitable for VANET because the mobility model and environment of VANET are different from those of traditional MANET. To solve this problem, we proposed a new stable routing algorithm, called stable directional forward routing. The novelty of the proposed routing protocol is its combining direction broadcast and path duration prediction into ad hoc on-demand distance vector routing protocols, which including: (1) Nodes in VANET are grouped based on the position, only nodes in a given direction range participating in the route discovery process to reduce the frequency of flood requests, (2) Route selection is based on the link duration while not the hops or other metrics to increase the path duration, (3) Route discovery is executed before the path expiration in order to decrease the end to end delay. The performance of the new scheme is evaluated through extensive simulations with Qualnet. Simulation results indicate the benefits of the proposed routing strategy in terms of decreasing routing control packet, reducing the number of link-breakage events, improving the packet delivery ratio and decreasing the end-to-end delay.     

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.     

Connectivity management in mobile ad hoc networks using particle swarm optimization

This paper proposes a dynamic mobile ad hoc network (MANET) management system to improve network connectivity by using controlled network nodes, called agents. Agents have predefined wireless communication capabilities similar to the other nodes in the MANET, however their movements, and thus their locations, are dynamically determined to optimize network connectivity. A new approach to measuring connectivity using a maximum flow formulation is proposed – this is both responsive and tractable. Furthermore, users’ locations are predicted for several time steps ahead and this is shown to improve network connectivity over the network operation period. A particle swarm optimization (PSO) algorithm uses the maximum flow objective to choose optimal locations of the agents during each time step of network operation. The proposed MANET management system is rigorously tested on numerous static and dynamic problems. Computational results show that the proposed approach is effective in improving the connectivity of MANETs and predicting movements of user nodes and deploying agents accordingly significantly improves the overall performance of a MANET.     

基于临近空间飞行器的区域自组网优化部署算法

该文针对基于临近空间飞行器的新型区域自组织网络,提出一种优化部署方案。采用线性递减权值粒子群算法,对于临近空间飞行器节点,一个粒子代表所有飞行器节点坐标集合,以最大化网络覆盖空间的联合通信覆盖率为目标,进行节点的优化部署。对于地面骨干节点,一个粒子代表一个网络分区内骨干节点坐标,以最多覆盖节点数和最小平均跳数为目标,进行初始化。网络运行过程中根据任务区域内数据业务分布情况,以趋近数据量多、业务优先级高的区域为目标,动态调整更新地面骨干节点位置。仿真结果表明,所提方案能为上层协议的运行提供良好基础,使网络分组投递率、延迟和开销等性能得到改善。     

A routing protocol for mobile ad‐hoc networks using the profit optimization model

Recently, wireless networks have become one of the major development trends in computer network technology. Because there is no more need of the wired transmission medium, applications have thus diversified. One such growing field of wireless networks is the mobile ad‐hoc network (MANET). A MANET consists of mobile hosts (such as portable laptops, vehicles, etc.), and no fixed infrastructure is required. MANETs provide ease of self‐configuration and can extend coverage at a low cost. Numerous applications have therefore been proposed under this network environment for daily life use. Because MANETs nodes are capable of moving, MANET network topology changes frequently. Thus, the traditional routing protocols fail to fit such an environment. In this paper, we propose an efficient routing protocol for MANETs, which integrates the mathematical model of profit optimization (the Kelly formula) from the field of economics to cope with the routing problem caused by node mobility. Some numerical simulations have been conducted to evaluate the performance of the proposed method using the network simulator NS‐2. The results show that our proposed method outperforms conventional routing protocols in packet delivery ratio comparisons; and the average end‐to‐end delays are within a tolerable range. Copyright © 2013 John Wiley & Sons, Ltd.