Distributed network control for mobile multi-modal wireless sensor networks

A sensor network operates on an infrastructure of sensing, computation, and communication, through which it perceives the evolution of events it observes. We propose a fusion-driven distributed dynamic network controller, called MDSTC, for a multi-modal sensor network that incorporates distributed computation for in-situ assessment, prognosis, and optimal reorganization of constrained resources to achieve high quality multi-modal data fusion. For arbitrarily deployed sensors, a certain level of data quality cannot be guaranteed in sparse regions. MDSTC reallocates resources to sparse regions; reallocation of network resources in this manner is motivated by the fact that an increased density of sensor nodes in a region of interest leads to better quality data and enriches the network resilience. Simulation results in NS-2 show the effectiveness of the proposed MDSTC. ¹     

Distributed clock skew and offset estimation from relative measurements in mobile networks with Markovian switching topology

We analyze a distributed algorithm for the estimation of scalar parameters belonging to nodes in a mobile network from noisy relative measurements. The motivation comes from the problem of clock skew and offset estimation for the purpose of time synchronization. The time variation of the network was modeled as a Markov chain. The estimates are shown to be mean square convergent under fairly weak assumptions on the Markov chain, as long as the union of the graphs is connected. Expressions for the asymptotic mean and correlation are also provided.     

Securing dynamic itineraries for mobile agent applications

In this paper we present a novel mechanism for the protection of dynamic itineraries for mobile agent applications. Itineraries that are decided as the agent goes are essential in complex applications based on mobile agents, but no approach has been presented until now to protect them. We have conceived a cryptographic scheme for shielding dynamic itineraries from tampering, impersonation and disclosure. By using trust strategically, our scheme provides a balanced trade-off between flexibility and security. Our protection scheme has been thought always bearing in mind a feasible implementation, and thus facilitates the development of applications that make use of it. An example application based on a real healthcare scenario is also presented to show its operation.     

Distributed reformation of core-based group-shared multicast trees in mobile ad hoc networks

This paper proposes a method to reduce the cost of a core-based group-shared multicast tree, where the cost is evaluated by the total bandwidth consumption of multicasting packets among all group members. Due to the broadcast nature of radio transmissions, we find that the challenge of determining minimum cost multicast tree can be approximated by finding the multicast tree with a minimum number of non-leaves (the minimum non-leaf multicast tree problem). However, we also find that the minimum non-leaf multicast tree problem is NP-complete. Thus, a method is proposed to dynamically reduce the number of non-leaves in an existing multicast tree. Experimental results show that our method reduces the cost of the multicast tree in both geometrically and randomly distributed network models and the random waypoint mobility model.     

Distributed Court System for intrusion detection in mobile ad hoc networks

Securing routing layer functions in mobile ad hoc networks is an important issue, which includes many challenges like how to enhance detection accuracy when facing the highly dynamic characteristic of such networks, and how to distinguish malicious accusations under a totally autonomous structure. In this paper, we propose Distributed Court System (DCS), a complete Intrusion Detection System that intends to solve these challenges in a low-cost and robust way. We do not deploy any centralized entity, but rely on the collaboration among the nodes neighbouring the suspected node, to integrate information, improve the detection accuracy, and reject dissemination of malicious accusation. Through mathematical analysis and simulation, the proposed DCS is proved to be effective in a highly mobile and hostile network environment.     

Distributed deadlock resolution in store-and-forward networks

We present a simple distributed algorithm that resolves store-and-forward deadlocks in data communication networks. The basic idea of the algorithm is to detect cycles of nodes that may cause store-and-forward deadlocks, and to rotate packets along these cycles. The algorithm uses a fixed amount of storage in each node for its execution, and, under reasonable assumptions upon the routing and packet handling, it ensures that packets that enter the network arrive at their destinations in finite time.Part of this work was done while this author was on sabbatical leave with IBM, Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA.     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

Lower bounds for the broadcast problem in mobile radio networks

Summary.  In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol Π, for any n and for any D≦n/2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by Π for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors. Received: August 1994 / Accepted: August 1996     

Cost-effective mobile ad hoc networks management

As there are more and more mobile devices in use, different mobile networking models such as ad hoc or mesh are attracting a large research interest. Self-organizing mobile ad hoc networks (MANET) allow devices to share their services and resources without any central administration or Internet support. In this respect they can become the backbone of the wireless grid or the gateway to existing grids. To achieve these goals, MANET management must be as effective as that of wired networks. This is, however, a challenging task due to network features like mobility, heterogeneity, limited resources of hosts and feeble communication. This paper presents a set of simple, cost-effective and resilient procedures for the basic tasks of MANET creation and management.     

Evaluating location management schemes for third generation mobile networks

Several strategies have been proposed recently to improve the performance of the IS-41 location management scheme. A forwarding pointers' strategy and a built-in memory strategy are proposed to reduce the signaling cost for location update and improve the IS-41 location update procedure. In this paper, we present a performance analysis of each strategy in an arbitrary time interval. In this analysis, users are classified by their call to mobility ratio which is defined as the call arrival rate divided by the mobility rate. We evaluate each of these strategies using this call to mobility ratio in order to come up with a set of recommendations that determine when each strategy is beneficial and for which class of users. We provide also a simplified analysis of the database loads generated by each strategy.     

Improved group-based cooperative caching scheme for mobile ad hoc networks

Data caching is a popular technique that improves data accessibility in wired or wireless networks. However, in mobile ad hoc networks, improvement in access latency and cache hit ratio may diminish because of the mobility and limited cache space of mobile hosts (MHs). In this paper, an improved cooperative caching scheme called group-based cooperative caching (GCC) is proposed to generalize and enhance the performance of most group-based caching schemes. GCC allows MHs and their neighbors to form a group, and exchange a bitmap data directory periodically used for proposed algorithms, such as the process of data discovery, and cache placement and replacement. The goal is to reduce the access latency of data requests and efficiently use available caching space among MH groups. Two optimization techniques are also developed for GCC to reduce computation and communication overheads. The first technique compresses the directories using an aggregate bitmap. The second employs multi-point relays to develop a forwarding node selection scheme to reduce the number of broadcast messages inside the group. Our simulation results show that the optimized GCC yields better results than existing cooperative caching schemes in terms of cache hit ratio, access latency, and average hop count.     

A fault tolerant mutual exclusion algorithm for mobile ad hoc networks

In this paper, we propose a permission-based message efficient mutual exclusion (MUTEX) algorithm for mobile ad hoc networks (MANETs). To reduce messages cost, the algorithm uses the “look-ahead” technique, which enforces MUTEX only among the hosts currently competing for the critical section. We propose mechanisms to handle dozes and disconnections of mobile hosts. The assumption of FIFO channel in the original “look-ahead” technique is also relaxed. The proposed algorithm can also tolerate link or host failures, using timeout-based mechanisms. Both analytical and simulation results show that the proposed algorithm works well under various conditions, especially when the mobility is high or load level is low. To our knowledge, this is the first permission-based MUTEX algorithm for MANETs.     

Location aware, dependable multicast for mobile ad hoc networks

This paper introduces dynamic source multicast (DSM), a new protocol for multi-hop wireless (i.e., ad hoc) networks for the multicast of a data packet from a source node to a group of mobile nodes in the network. The protocol assumes that, through the use of positioning system devices, each node knows its own geographic location and the current (global) time, and it is able to efficiently spread these measures to all other nodes. When a packet is to be multicast, the source node first locally computes a snapshot of the complete network topology from the collected node measures. A Steiner (i.e., multicast) tree for the addressed multicast group is then computed locally based on the snapshot, rather than maintained in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Pr

Full-size image

u" height="11" width="9">fer sequence and is included in the packet header as in, and extending the length of the header by no more than, the header of packets in source routing (unicast) techniques. We show that all the local computations are executed in polynomial time. More specifically, the time complexity of the local operation of finding a Steiner tree, and the encoding/decoding procedures of the related Prüfer sequence, is proven to be O(n²), where n is the number of nodes in the network. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that DSM delivers packets to all the nodes in a destination group in more than 90% of the cases. Furthermore, compared to flooding, DSM achieves improvements of up to 50% on multicast completion delay.     

A scalable publish/subscribe system for large mobile ad hoc networks

Since nodes that compose mobile ad hoc networks (MANETs) does not have any prior knowledge about other nodes in many cases, the publish/subscribe communication paradigm that has the decoupling and asynchrony properties can be useful to share information between nodes. Existing publish/subscribe services for MANETs can be categorized into document flooding (DF), destination-based routing (DBR), and content-based routing (CBR). Although those approaches may work well when the size of network is small, all of them suffer from the performance decline as the size of the network increases. In this paper, we compare those approaches, and then propose a scalable publish/subscribe communication scheme in large MANETs by combining DF and CBR hierarchically. Our approach is to cluster all nodes in networks and to exploit CBR and DF for the intra- and inter-cluster communication, respectively. By using this approach, we can effectively utilize benefits of both approaches. Then, we present performance evaluation results which validate our idea with respect to system performance and scalability.     

水下移动无线传感器网络研究综述

水下移动传感器网络是水下机器人与水下传感器网络的结合,解决了传统水下监控网络存在的无法自动实现节点投放与回收,容易存在监测盲区以及不能动态组网等问题,按照自下而上的体系结构,对水下移动传感器网络的研究内容及发展方向进行了归纳阐述,包括水下节点设计、节点互联和动态组网,即点、线、面的层次结构;着重分析了节点移动特性对水下传感器网络的影响及相应的解决方法.虽然水下移动传感器网络的研究面临很多挑战,但它必将具有广阔的应用前景.     

Distributed clustering algorithms for data-gathering in wireless mobile sensor networks

One critical issue in wireless sensor networks is how to gather sensed information in an energy-efficient way since the energy is a scarce resource in a sensor node. Cluster-based architecture is an effective architecture for data-gathering in wireless sensor networks. However, in a mobile environment, the dynamic topology poses the challenge to design an energy-efficient data-gathering protocol. In this paper, we consider the cluster-based architecture and provide distributed clustering algorithms for mobile sensor nodes which minimize the energy dissipation for data-gathering in a wireless mobile sensor network. There are two steps in the clustering algorithm: cluster-head election step and cluster formation step. We first propose two distributed algorithms for cluster-head election. Then, by considering the impact of node mobility, we provide a mechanism to have a sensor node select a proper cluster-head to join for cluster formation. Our clustering algorithms will achieve the following three objectives: (1) there is at least one cluster-head elected, (2) the number of cluster-heads generated is uniform, and (3) all the generated clusters have the same cluster size. Last, we validate our algorithms through an extensive experimental analysis with Random Walk Mobility (RWM) model, Random Direction Mobility (RDM) model, and a Simple Mobility (SM) model as well as present our findings.     

Adaptive location updates for mobile sinks in wireless sensor networks

Mobile sinks can be used to balance energy consumption for sensor nodes in Wireless Sensor Networks (WSNs). Mobile sinks are required to inform sensor nodes about their new location information whenever necessary. However, frequent location updates from mobile sinks can lead to both rapid energy consumption of sensor nodes and increased collisions in wireless transmissions. We propose a new solution with adaptive location updates for mobile sinks to resolve this problem. When a sink moves, it only needs to broadcast its location information within a local area other than among the entire network. Both theoretical analysis and simulation studies show that this solution consumes less energy in each sensor node and also decreases collisions in wireless transmissions, which can be used in large-scale WSNs.

An evolutionary computation approach for designing mobile ad hoc networks

This paper presents the topological design of ad hoc networks in terms of distances among static nodes and speeds of mobiles nodes. Due to the complexity of the problem and the number of parameters to be considered, a genetic algorithm combined with the simulation environment NS-2 is proposed to find the optimum solution. More specifically, NS-2 provides the fitness function guiding the genetic search. The proposed framework has been tested using a railway scenario in which several static and mobile nodes are interacting. Results show the feasibility of the proposed framework and illustrate the possibility of genetic approach for solving similar application scenarios.     

Managing real-time database transactions in mobile ad-hoc networks

In a mobile ad-hoc network (MANET), mobile hosts can move freely and communicate with each other directly through a wireless medium without the existence of a fixed wired infrastructure. MANET is typically used in battlefields and disaster recovery situations where it is not feasible to have a fixed network. Techniques that manage database transactions in MANET need to address additional issues such as host mobility, energy limitation and real-time constraints. This paper proposes a solution for transaction management that reduces the number of transactions missing deadlines while balancing the energy consumption by the mobile hosts in the system. This paper then reports the simulation experiments that were conducted to evaluate the performance of the proposed solution in terms of number of transactions missing deadlines, total energy consumption and the distribution of energy consumption among mobile hosts. Recommended by: Ahmed Elmagarmid This work is partially supported by the National Science Foundation grants No. EIA-9973465 and IIS-0312746.