Joint routing and flow rate optimization in multi-rate ad hoc networks

Typical radios in ad hoc networks can support multi-rate transmissions. However, traditional routing protocols do not use this feature well in multi-rate ad hoc networks and therefore, the network performance and resource utilization are not optimized. Some algorithms have been proposed to take advantage of the multi-rate transmission scheme, but their performance is not optimized either. In this paper, we show that a cross-layer optimization based approach can significantly improve the performance of multi-rate ad hoc networks over existing routing algorithms. For this, we consider link interference and propose joint routing and flow rate optimization for optimal performance in multi-rate ad hoc networks, i.e., a Cross-layer Optimization based Model for Multi-rate Ad hoc Networks (COMMAN). Considering the characteristics of multi-rate ad hoc networks, we design and implement a distributed heuristic of this centralized model. It is shown that the distributed heuristic algorithm can approximate the performance of COMMAN closely.     

An Energy-Efficient Resource Allocation Scheme for Mobile Ad Hoc Computational Grids

Due to recent advancements in mobile computing and communication technologies, mobile ad hoc computational Grids are emerging as a new computing paradigm, enabling innovative applications through sharing of computing resources among mobile devices without any pre-existing network infrastructure. Energy-efficient resource allocation is one of the key issues in mobile ad hoc computational Grids due to limited battery life of mobile nodes. To reduce energy consumption, we propose a hybrid power-based resource allocation scheme for allocation of interdependent tasks to nodes within mobile ad hoc computational Grid. The basic idea is to exploit dependencies and task type, and allocate interdependent tasks to nodes accessible at minimum transmission power. We also propose a power-based algorithm to search a group of closest nodes to allocate a set of interdependent tasks. Compared to traditional algorithms, complexity of proposed algorithm depends on number of transmission power levels rather than number of nodes within a Grid. The scheme is validated in a simulation environment using various workloads and parameters.     

Maximizing connected coverage via controlled actor relocation in wireless sensor and actor networks

Wireless sensor and actor networks (WSANs) have recently emerged with the idea of combining wireless sensor networks (WSNs) and mobile ad hoc networks (MANETs). In addition to resource constrained sensors, resource rich and mobile actor nodes are employed in WSANs. These actors can collect data from the sensors and perform appropriate actions as a result of processing such data. To perform the actions at all parts of the region in a timely manner, the actors should be deployed in such a way that they might be able to communicate with each other and cover the whole monitored area. This requires that the actors should be placed carefully prior to network operation in order to maximize the coverage and maintain the inter-actor connectivity. In this paper, we propose a distributed actor deployment algorithm that strives to maximize the coverage of actors without violating the connectivity requirement. The approach applies repelling forces between neighboring actors and from the sensors that sit on the boundaries in order to spread them in the region. The spreading of the nodes is done using a tree of actors which can provide more freedom for the movement of the nodes but at the same time maintain the required connectivity among the nodes. We present two techniques for creation of such an actor tree which are based on local pruning of the actor links and spanning tree of the inter-actor network. The performance of our approach is validated both analytically and experimentally.     

Secure communications for cluster-based ad hoc networks using node identities

Ad hoc networks are self-configurable networks with dynamic topologies. All involved nodes in the network share the responsibility for routing, access, and communications. The mobile ad hoc network can be considered as a short-lived collection of mobile nodes communicating with each other. Such networks are more vulnerable to security threats than traditional wireless networks because of the absence of the fixed infrastructure. For providing secure communications in such networks, lots of mechanisms have been proposed since the early 1990s, which also have to deal with the limitations of the mobile ad hoc networks, including high power saving and low bandwidth. Besides, public key infrastructure (PKI) is a well-known method for providing confidential communications in mobile ad hoc networks. In 2004, Varadharajan et al. proposed a secure communication scheme for cluster-based ad hoc networks based on PKI. Since the computation overheads of the PKI cryptosystem are heavy for each involved communicating node in the cluster, we propose an ID-based version for providing secure communications in ad hoc networks. Without adopting PKI cryptosystems, computation overheads of involved nodes in our scheme can be reduced by 25% at least.     

Energy efficient and robust allocation of interdependent tasks on mobile ad hoc computational grid

A mobile ad hoc computational grid is a distributed computing infrastructure that allows mobile nodes to share computing resources in a mobile ad hoc environment. Compared to traditional distributed systems such as grids and clouds, resource allocation in mobile ad hoc computational grids is not straightforward because of node mobility, limited battery power and an infrastructure‐less network environment. The existing schemes are either based on a decentralized architecture that results in poor allocation decisions or assume independent tasks. This paper presents a scheme that allocates interdependent tasks and aims to reduce task completion time and the amount of energy consumed in transmission of data. This scheme comprises two key algorithms: resource selection and resource allocation. The resource selection algorithm is designed to select nodes that remain connected for a longer period, whereas the resource assignment or allocation algorithm is developed to allocate interdependent tasks to the nodes that are accessible at the minimum transmission power. The scheme is based on a hybrid architecture that results in effective allocation decisions, reduces the communication cost associated with the exchange of control information, and distributes the processing burden among the nodes. The paper also investigates the relationship between the data transfer time and transmission energy consumption and presents a power‐based routing protocol to reduce data transfer costs and transmission energy consumption. Copyright © 2014 John Wiley & Sons, Ltd.     

TAP: Traffic-aware topology control in on-demand ad hoc networks

Energy efficiency is crucial to achieve satisfactory network lifetime in ad hoc networks. In order to reduce the energy consumption significantly, a node needs to turn off its transceiver. Many existing energy-saving algorithms are based on constructing a simplified routing backbone for global connectivity. In this paper some problems involved with node sleep in on-demand ad hoc networks are addressed firstly. Then we propose a distributed, cross-layer Traffic-Aware Participation (TAP) algorithm, where nodes make decisions on whether to sleep or not based on both the traffic pattern and local connectivity. Nodes get dynamic traffic characteristics as well as active neighbors within two hops via routing control and data packets periodically. We further present a lightweight algorithm to avoid network partition resulted from node sleeping. Simulation results show that, compared to current sleep-based topology control algorithms, TAP achieves better network service quality and lower delay while allowing comparable energy conservation.     

Energy efficient multicast routing in ad hoc wireless networks

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. Each node in the network is assumed to have a fixed level of transmission power. The problem of our concern is: given an ad hoc wireless network and a multicast request, how to find a multicast tree such that the total energy cost of the multicast tree is minimized. We first prove this problem is NP-hard and it is unlikely to have an approximation algorithm with a constant performance ratio of the number of nodes in the network. We then propose an algorithm based on the directed Steiner tree method that has a theoretically guaranteed approximation performance ratio. We also propose two efficient heuristics, node-join-tree (NJT) and tree-join-tree (TJT) algorithms. The NJT algorithm can be easily implemented in a distributed fashion. Extensive simulations have been conducted to compare with other methods and the results have shown significant improvement on energy efficiency of the proposed algorithms.     

Deterministic Communication in Radio Networks with Large Labels

We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n²log n) time for N polynomially large in n. The O(nlog²n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic O(n log N log n)-time broadcasting and O(n²log²N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n^3/2log²N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log²N log²n)-time gossiping algorithm for undirected networks.     

A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks

Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm     

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。     

一种基于身份的车载自组网认证机制

针对车载自组网（VANET）的安全特性,采用基于身份的密码学算法、分布式秘密共享算法和XTR公钥密码体制,实现安全高效的车辆节点认证。在使用Lagrange插值公式实现分布式的系统主密钥的基础上,基于XTR体制中的迹运算实现安全的分布式节点密钥签发;简单讨论了XTR密码体制下基于身份的数字签名算法;同时,引入信誉值的概念来查找和剔除网络中的恶意节点。通过算法安全性和效率分析,该机制适用于分布式的车辆移动网络环境。     

Distributed fault tolerant computation of weakly connected dominating set in ad hoc networks

Our purpose in this paper is to propose a self-stabilizing protocol for weakly connected dominating set (WCDS) set in a given ad hoc network graph. WCDS is a particular variant of graph domination predicates which play an important role in routing in ad hoc networks. There are many variants of domination problems in bidirectional networks; WCDS is also useful in forming clusters in ad hoc networks. There are many heuristic and distributed algorithms to compute WCDS in network graphs while almost all of them will need complete information about the network topology and most of them are not fault tolerant or mobility tolerant. Self-stabilization is a protocol design paradigm that is especially useful in resource constrained infrastructure-less networks since nodes can make moves based on local knowledge only and yet a global task is accomplished in a fault tolerant manner; it also facilitates for nodes to enter and exit the network freely. There exist self-stabilizing protocols for minimal spanning tree, total domination, and others. We have shown that the paradigm is capable of designing a protocol for WCDS. Our objective is to mathematically prove the correctness and the convergence of the protocol in any worst-case scenario, as is usually done for self-stabilizing protocols for other graph predicates used for ad hoc networks.     

Energy-efficient topology control in wireless ad hoc networks with selfish nodes

In wireless ad hoc networks there is no fixed infrastructure or centralized controller to enforce cooperation between nodes. Therefore, nodes may act selfishly in running network protocols for conserving their own energy resources. In this paper, we consider the “topology control (TC) game” as the problem of creating an energy-efficient topology in wireless ad hoc networks in the presence of selfish nodes. We define a new TC game in which nodes are able to dynamically adjust their transmission power in a per-packet manner, and try to minimize their energy usage through considering both traffic load and transmission power parameters. After analyzing the problem, we propose several algorithms to find stable topologies in an environment composed of selfish nodes, using two types of global and local connectivity information. Finally, we evaluate the performance of the proposed algorithms by simulations. Our simulation results show that using appropriate local information can interestingly result in more efficient topologies than global information.     

移动自组网中基于移动预测和概率的能量有效组播路由算法

移动自组网中节点的使用寿命很大程度上依赖于电池能量的有效利用．通过研究移动节点能量的剩余和使用情况，提出了一种新的关于节点能量估价函数PCF（power cost function）计算方法，能够较好地反映当前节点的能耗值．并且结合PCF提出一种基于移动预测和概率构造能量有效组播树M-REMiT（an algorithm based on mobility prediction and probability for refining energy-efficient multicast tree）的分布式算法，在节点移动的情况下，利用概率优化方法减少一棵组播树的总能量消耗，延长了组播树中每个节点的使用寿命．模拟结果显示这个组播算法比以前相关的算法具有更好的性能．     

SmallWorld Model-Based Polylogarithmic Routing Using Mobile Nodes

The use of mobile nodes to improve network system performance has drawn considerable attention recently. The movement-assisted model considers mobility as a desirable feature,where routing is based on the store-carry-forward paradigm with random or controlled movement of resource rich mobile nodes.The application of such a model has been used in several emerging networks,including mobile ad hoc networks(MANETs),wireless sensor networks(WSNs),and delay tolerant networks(DTNs).It is well known that mobility increases the capacity of MANETs by reducing the number of relays for routing,prolonging the lifespan of WSNs by using mobile nodes in place of bottleneck static sensors,and ensuring network connectivity in DTNs using mobile nodes to connect different parts of a disconnected network.Trajectory planning and the coordination of mobile nodes are two important design issues aiming to optimize or balance several measures, including delay,average number of relays,and moving distance.In this paper,we propose a new controlled mobility model with an expected polylogarithmic number of relays to achieve a good balance among several contradictory goals,including delay,the number of relays,and moving distance.The model is based on the small-world model where each static node has"short"link connections to its nearest neighbors and"long"link connections to other nodes following a certain probability distribution.Short links are regular wireless connections whereas long links are implemented using mobile nodes.Various issues are considered,including trade-offs between delay and average number of relays,selection of the number of mobile nodes,and selection of the number of long links.The effectiveness of the proposed model is evaluated analytically as well as through simulation.     

层状 Ad Hoc 网络的信息传播路由算法研究

讨论了层状移动AdHoc网络的一个信息传播路由算法和基于半马尔可夫过程的节点移动跟踪模型,通过该路由算法可以有效地解决层状子网络间的通信和信息交换。通过路由算法得到的中继节点的移动跟踪模型和计算机仿真,分析了层状移动AdHoc网络的传播性能和路由开销,并得出:当 0≤ρ≤ 1时,层状AdHoc网络的传播性能显著地受到移动呼叫率ρ的影响,当ρ>1时,层状AdHoc网络的传播性能主要取决于移动网络的节点总数、节点移动速度和加速度的结论。     

基于分层结构的Ad Hoc多播路由算法

根据Ad Hoc移动网络采用多级分层结构管理体系的特点,提出了一种Ad Hoc移动网络的多播路由算法。通过对移动自组网进行簇划分,形成由簇节点、簇桥节点和簇内节点构成的分簇网络结构,并且在由簇节点和簇桥节点形成的虚拟骨干网基础上,通过回路检测和冗余剪枝算法处理,最终得到一个能满足多播要求的多播树。仿真实验说明,该多播路由算法具有稳定的数据包发送率,减少了路由建立时间。     

Toward secure and scalable time synchronization in ad hoc networks

Time synchronization is crucial in ad hoc networks. Due to the infrastructure-less and dynamic nature, time synchronization in such environments is vulnerable to various attacks. Moreover, time synchronization protocols such as IEEE 802.11 TSF (Timing Synchronization Function) often suffer from scalability problem.In this paper, we address the security and the scalability problems of time synchronization protocols in ad hoc networks. We propose a novel suite of time synchronization mechanisms for ad hoc networks based on symmetric cryptography. For single-hop ad hoc networks, we propose SSTSP, a scalable and secure time synchronization procedure based on one-way Hash chain, a lightweight mechanism to ensure the authenticity and the integrity of synchronization beacons. The “clock drift check” is proposed to counter replay/delay attacks. We then extend our efforts to the multi-hop case. We propose MSTSP, a secure and scalable time synchronization mechanism based on SSTSP for multi-hop ad hoc networks. In MSTSP, the multi-hop network is automatically divided into single-hop clusters. The secure intra-cluster synchronization is achieved by SSTSP and the secure inter-cluster synchronization is achieved by exchanging synchronization beacons among cluster reference nodes via bridge nodes.The proposed synchronization mechanisms are fully distributed without a global synchronization leader. We further perform analytical studies and simulations on the proposed approaches. The results show that SSTSP can synchronize single-hop networks with the maximum synchronization error under 20 μs and MSTSP 55–85 μs for multi-hop networks, which are, to the best of our knowledge, among the best results of currently proposed solutions for single-hop and multi-hop ad hoc networks. Meanwhile, our approaches can maintain the network synchronized even in hostile environments.     

A link availability-based QoS-aware routing protocol for mobile ad hoc sensor networks

With more and more wireless devices being mobile, there is a constant challenge to provide reliable and high quality communication services among these devices. In this paper, we propose a link availability-based QoS-aware (LABQ) routing protocol for mobile ad hoc networks based on mobility prediction and link quality measurement, in addition to energy consumption estimate. The goal is to provide highly reliable and better communication links with energy-efficiency. The proposed routing algorithm has been verified by NS-2 simulations. The results have shown that LABQ outperforms existing algorithms by significantly reducing link breakages and thereby reducing the overheads in reconnection and retransmission. It also reduces the average end-to-end delay for data transfer and enhances the lifetime of nodes by making energy-efficient routing decisions.