IFAS: Interactive flexible ad hoc simulator

Ad hoc networks are characterized by fast, dynamic changes in the topology of the network. Introduction of new routing algorithms requires a deep and reliable evaluation process. In this paper, we describe an interactive flexible ad hoc simulator (IFAS) that presents a modern and novel approach to the family of ad hoc simulators. This simulator supports unique viewing, debugging, tuning and interactive capabilities that shorten significantly the design and debug process of new algorithms. The development of the IFAS is ongoing; however, we consider this new simulator as an innovative tool that will supplement traditional simulators.     

A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.     

Multiple-access insights from bounds on sensor localization

In ad hoc location-aware sensor networks, unlocalized sensors can estimate their locations based on the triangulation of range measurements from location-aware sensors or “anchors”, whose locations are known or estimated a priori. In this paper, we investigate the relationship between multiple-access design parameters and the accuracy of location estimation in ad hoc sensor networks. Bounds on the average localization accuracy in a packet-based sensor network with time-of-arrival (TOA) based distance estimation are used to investigate the connection between the average effective throughput of packets and the average localization accuracy. On this basis, we (i) develop an analytical framework that allows us to analyze the relationship between network parameters and the average localization accuracy obtained in ad hoc sensor networks with a spread-spectrum physical layer, and (ii) show that, for such networks, minimizing the average localization error is equivalent to maximizing the average effective throughput. We further demonstrate that the developed framework allows the extraction of the optimal network parameters that maximize localization accuracy. The trends in the localization accuracy with respect to the network parameters observed through analysis are then validated via simulation studies. Finally, some aspects of the modeling of location-aware sensor networks that warrant investigation and require more sophisticated modeling strategies are listed.     

Real time query propagation strategies with Lightweight Coordination Calculus (LCC) for ad hoc networks of geospatial databases

Large volumes of geospatial data are increasingly made available through dynamic networks, such as ad hoc networks. Consequently, new adapted query propagation approaches that take into account geospatial aspects of data are needed. Different existing query propagation approaches use various criteria to select relevant sources. In addition, many approaches rely on existing semantic mappings between sources; however, in ad hoc networks, sources move autonomously and in a dynamic fashion. Our goal is rather to reduce the number of sources that must be accessed to answer a query and, therefore, to reduce the volume of semantic mappings that needs to be computed to answer the query. In this paper, we propose three real time query propagation strategies to address this issue. Those strategies reproduce the behavior of members of a social network. The strategies are designed to be part of a real time semantic interoperability framework for ad hoc networks of geospatial databases. The strategies have been formalized with the Lightweight Coordination Calculus (LCC), which support distributed interactions based on social norms and constraints. The implementation and testing of the strategies show that they complement each other to provide optimal query answers.     

基于攻击事件的动态网络风险评估框架

将动态网络的演化思想应用于计算机网络风险评估中,提出了基于攻击事件的动态网络风险评估框架。整个框架首先在静态物理链路的基础上构建动态访问关系网络,随后提出的Timeline算法可以利用时间特性有效地描述攻击演化趋势和发现重要攻击事件,图近似算法可以将分析过程简化为时间段近似图之间的分析,能够有效减小噪声行为的影响。此外,整体框架可以对网络段进行演化追踪和关联分析。实例分析表明,该框架具有很好的实用性,可以更好地揭示攻击者的攻击策略以及重要攻击事件间的紧密联系。     

Adaptive TCP congestion control and routing schemes using cross-layer information for mobile ad hoc networks

Compared with traditional networks, ad hoc networks possess many unique characteristics. For example, ad hoc networks can drop a packet due to network events other than buffer overflow. Unfortunately, the current layered network architecture makes it impossible to pass the information specific to one layer to other layers. As a result, if a packet is lost due to reasons other than buffer overflow, TCP adversely invokes its congestion control procedure. Similarly, the routing algorithm may misinterpret that a path is broken and adversely invoke the route recovery procedure.This study addresses the limitations of the current layered network architecture by adopting a cross-layer protocol design for TCP and routing algorithms in ad hoc networks. The objective of this approach is to enable the lower-layered ad hoc network to detect and differentiate all possible network events, including disconnections, channel errors, buffer overflow, and link-layer contention, that may cause packet loss. Using the information exploited by lower layers, the upper layer-3 routing algorithm, and the layer-4 TCP can take various actions according to the types of network events. Simulation results demonstrate that the combination of the cross-layer optimized TCP and routing algorithms can effectively improve the performance of TCP and DSR, regardless of whether it is in a stationary or a mobile ad hoc network.     

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.     

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.     

Requirements and design for neutral trust management framework in unstructured networks

Free-rider problem greatly influences the performance of unstructured networks (like ad hoc or peer-to-peer networks). To solve such problem, we focus on trust management framework, which is intended to stimulate nodes to cooperate with each other and prevent free-riders. Currently, the existing trust management framework can be classified into trust establishment framework and reputation-based framework. None of them, however, was explicitly designed with the considerations on neutrality, which is indispensable issue when devising a network system. Therefore, we attempt to march towards the design of neutral trust management framework in this paper. We firstly investigate the relation between neutrality and trust definition, and identify the requirements for design of neutral trust management framework. Then, we focus on trust management of one kind of typical unstructured networks, mobile ad hoc network (MANET). We design a neutral trust management framework of MANET to meet the clarified design requirements. Further, we perform analysis on our proposed framework, which shows our proposal can achieve neutrality under the location-dependent attack of free-rider in MANET.     

F-Ant: an effective routing protocol for ant colony optimization based on fuzzy logic in vehicular ad hoc networks

Vehicular ad hoc networks (VANETs) are a subset of mobile ad hoc networks that provide communication services between nearby vehicles and also between vehicles and roadside infrastructure. These networks improve road safety and accident prevention and provide entertainment for passengers of vehicles. Due to the characteristics of VANET such as self-organization, dynamic nature and fast-moving vehicles, routing in this network is a considerable challenge. Swarm intelligence algorithms (nature-inspired) such as ant colony optimization (ACO) have been proposed for developing routing protocols in VANETs. In this paper, we propose an enhanced framework for ACO protocol based on fuzzy logic for VANETs. To indicate the effectiveness and performance of our proposed protocol, the network simulator NS-2 is used for simulation. The simulation results demonstrate that our proposed protocol achieves high data packet delivery ratio and low end-to-end delay compared to traditional routing algorithms such as ACO and ad hoc on-demand distance vector (AODV).

     

无线网络拓扑控制中支撑图构造算法

支撑图(spanner)在无线(自主、传感器)网络拓扑控制中起着重要作用,不但能保证最终的拓扑图链路减少,保持连通性,而且保证任意一对通信节点之间所需费用是最少可能费用的常数因子倍.针对无线网络拓扑控制问题,大量支撑图构造算法被提出,以尽可能高效地满足网络设计需要的各种拓扑特性,如局部性、稀疏性、小权值、有界度及容错性等.对支撑图的研究成果进行了详细讨论,依据支撑图的定义和不同的分类原则给出了支撑图分类,分析了各种支撑图的典型集中式和局部算法、满足某一或多个拓扑特性的算法,并提出了需要进一步研究的问题.与无线网络中新出现、更实用的模型结合,寻找更简单、性能更好的算法将是未来支撑图构造算法的主要研究方向.     

CARRADS: Cross layer based adaptive real-time routing attack detection system for MANETS

Routing behavior in ad hoc networks is highly transient. Thus, dynamically adapting the routing attack detection system at real-time to new attacks and changing network conditions is critical in ad hoc networks. Conventional incremental learning methods are computationally expensive for resource-constrained nodes in ad hoc networks. In this paper, we propose CARRADS, a computationally efficient methodology for adapting the intrusion detection model at real-time. The adaptation process consists of two major stages. In the first stage, the main task is to identify occurrence of new patterns in the routing control traffic and prioritize them based on their information content. The second stage of adaptation is to incrementally update the detection model using the new patterns with minimum computational overhead. CARRADS uses SVM algorithm for its superior detection abilities. However, using some innovative techniques the computational overhead of incremental update is reduced by a factor of 20 to 30 times at the cost of a negligible decrease in detection accuracy. This makes CARRADS a viable approach for real-time IDS in ad hoc networks.     

Ad Hoc网络中一种基于环状分层结构的组密钥协商协议

移动ad hoc网络是一种新型的移动多跳无线网络.其自身的特征,如网络规模庞大、动态的拓扑结构、有限的计算、通信和存储能力等,使得传统的密钥分配和管理机制无法直接应用于该网络.提出了一种新的适用于移动 ad hoc网络的组密钥协商协议.该协议在环状分层结构上基于多线性映射进行组密钥的协商和分配,使得节点在密钥协商过程中具有低计算开销与低通信开销的优势,较好地解决了在移动ad hoc网络中进行组密钥协商时所遇到的节点能量受限问题,适用于移动ad hoc网络.     

Malware-Propagative Mobile Ad Hoc Networks: Asymptotic Behavior Analysis

In this paper, the spreading of malicious software over ad hoc networks, where legitimate nodes are prone to propagate the infections they receive from either an attacker or their already infected neighbors, is analyzed. Considering the Susceptible-Infected-Susceptible （SIS） node infection paradigm we propose a probabilistic model, on the basis of the theory of closed queuing networks, that aims at describing the aggregated behavior of the system when attacked by malicious nodes. Because of its nature, the model is also able to deal more effectively with the stochastic behavior of attackers and the inherent probabilistic nature of the wireless environment. The proposed model is able to describe accurately the asymptotic behavior of malware-propagative large scale ad hoc networking environments. Using the Norton equivalent of the closed queuing network, we obtain analytical results for its steady state behavior, which in turn is used for identifying the critical parameters affecting the operation of the network. Finally, through modeling and simulation, some additional numerical results are obtained with respect to the behavior of the system when multiple attackers are present, and regarding the time-dependent evolution and impact of an attack.     

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.     

自组网中路由度量的研究

路由度量的选择对路由协议的设计和性能起着至关重要的作用。文章主要研究和定量分析各种路由度量和它们之间的组合对自组网拓扑性能的影响,其结果将有助于使用混合度量作为路径选择标准的自适应路由协议的建模和开发。首次通过使用基于快照的分析方法,该文隔离和定量分析了四种影响自组网拓扑性能的路由度量:跳数、信号强度、方位信息和移动速度。与其它研究成果的不同之处在于它专注于相对未曾研究的领域,即用静态方法研究选路度量对动态网络拓扑性能的影响。特别地,文章从下列性能指标:平均路径稳定时间、平均新增中间节点数和平均跳数来评估这些路由度量的影响。     

高动态飞行器自组织网络组网研究

节点高速移动和网络拓扑变化迅速严重影响着高动态飞行器自组织网络性能。提出了一种适于高动态场景的移动自组织网络协议栈设计。该设计着重QoS需求,围绕网络拓扑高动态变化特征,合理配置不同层次的网络协议,适合高动态应用场景。以平面网络为例,分析评估了FANET网络在高动态环境下的性能。实验结果表明,该组网方式可行并能满足高动态飞行器自组织网络的功能和性能需求。还提出了节点在个体移动方式下保持网络高性能的最佳节点数目和网络各层次协议适应高动态拓扑变化的应对策略。     

On the lifetime of node-to-node communication in wireless ad hoc networks

Lifetime of node-to-node communication in a wireless ad hoc network is defined as the duration that two nodes can communicate with each other. Failure of the two nodes or failure of the last available route between them ends their communication. In this paper, we analyze the maximum lifetime of node-to-node communication in static ad hoc networks when alternative routes that keep the two nodes connected to each other are node-disjoint. We target ad hoc networks with random topology modeled as a random geometric graph. The analysis is provided for (1) networks that support automatic repeat request (ARQ) at the medium access control level and (2) networks that do not support ARQ. On the basis of this analysis, we propose numerical algorithms to predict at each moment of network operation, the maximum duration that two nodes can still communicate with each other. Then, we derive a closed-form expression for the expected value of maximum node-to-node communication lifetime in the network. As a byproduct of our analysis, we also derive upper and lower bounds on the lifetime of node-disjoint routes in static ad hoc networks. We verify the accuracy of our analysis using extensive simulation studies.     

Minimum disruption service composition and recovery in mobile ad hoc networks

The dynamic nature of mobile ad hoc networks poses fundamental challenges to the design of service composition schemes that can satisfy the end-to-end quality of service requirements and minimize the effect of service disruptions caused by dynamic link and node failures. Although existing research on mobile ad hoc networks has focused on improving reliability, little existing work has considered service deliveries spanning multiple components. Moreover, service composition strategies proposed for wireline networks (such as the Internet) are poorly suited for highly dynamic wireless ad hoc networks.This paper proposes a new service composition and recovery framework designed to achieve minimum service disruptions for mobile ad hoc networks. The framework consists of two tiers: service routing, which selects the service components that support the service path, and network routing, which finds the optimal network path that connects these service components. Our framework is based on the disruption index, which is a novel concept that characterizes different service disruption aspects, such as frequency and duration, that are not captured adequately by conventional metrics, such as reliability and availability.Using the definition of disruption index, we formulate the problem of minimum-disruption service composition and recovery (MDSCR) as a dynamic programming problem and analyze the properties of its optimal solution for ad hoc networks with known mobility plan. Based on the derived analytical insights, we present our MDSCR heuristic algorithm for ad hoc networks with uncertain node mobility. This heuristic algorithm approximates the optimal solution with one-step lookahead prediction, where service link lifetime is predicted based on node location and velocity using linear regression. We use simulations to evaluate the results of our algorithm in various network environments. The results validate that our algorithm can achieve better performance than conventional methods.     

Investigating the performance of TCP in mobile ad hoc networks

Mobile ad hoc networks have several inherent characteristics (e.g. dynamic topology, time-varying and bandwidth constrained wireless channels, multi-hop routing, and distributed control and management). The goal of this work is to investigate the impact of these characteristics on the performance of TCP. First, we investigate throughput performance of TCP as a function of path length (i.e. multiple wireless hops), node mobility, and traffic intensity. Next, we examine the ‘fairness’ of the ad hoc network with regard to equal sharing of network bandwidth among multiple TCP flows. Third, we evaluate the impact of two on-demand routing protocols (i.e. AODV and DSR) on the throughput of TCP. Finally, a factorial design experiment is conducted to quantify the effects and interactions of three factors, which influence the throughput of TCP. These factors include routing, node speed, and node pause time. Two key results were observed. Results show that traffic intensity (e.g. number of concurrent flows) is significantly affects TCP throughput, suggesting the need for congestion control, scheduling and traffic management schemes. Second, source routing achieves higher throughputs while also generating significantly less routing overhead than AODV. Results also show that in some instances, the fairness of the network is very uneven among concurrent TCP flows, resulting in several sending stations achieving very little or no throughput.