30-06-2012, 12:38 PM
Sending messages to mobile users in disconnected adhoc wireless networks
[attachment=26259]
INTRODUCTION
1.1 About the Topic
Mobile computers often disconnect from the network, and when they reconnect, they might find themselves with a radically different network connection in terms of bandwidth, reliability or latency. Approaches to cope with the transmission of data in mobile, wireless networks include traditional techniques such as try, timeout, sleep, retry, . . ., and wireless routing algorithms. The simple try, timeout, sleep, retry loop can often fail particularly if the system does not happen to retry connection during a brief reconnection period. Waiting may be disastrous in some emergency cases.
The current wireless networking solutions are not sufficient, because an entire path to the destination machine has to be available. Suppose you want to transmit data from machine Ms to machine Mg and the path includes at least one intermediate node, say machine Mi (this is often the case in wireless networks because of range limitations.) In order for the transmission to be successful, the connections between Ms and Mi and between Mi and Mg have to be available at the same time. The probability of this event is much smaller than the probability that one of the two hops (from Ms to Mi or from Mi to Mg) is open.
1.2 Application
We believe that this approach to communication is useful for the following two types of distributed applications.
(1) In the case when most of the network is connected (such as a well-maintained framework for a sensor network) , while some hosts are dispersed away from the framework, we do not have too many trajectory modifications to relay messages.
(2) In the case when the distance between two hosts is slightly larger than the transmission range, hosts need to move small distances to relay messages.
1.3 Basics of Topic
In this paper, we explore the possibility of changing the trajectories of the hosts in a dynamic disconnected ad-hoc network to transmit messages among hosts. We show how the information about the motion of the destination host can be used to determine how the message can be sent by the cooperation of the intermediate hosts. We seek to minimize the trajectory modifications in order to transmit a message.
Two algorithms are studied in the rest of the paper. In the first algorithm, we assume the information about the motions and locations of hosts is known to all hosts, or can be estimated with some error parameters. The second algorithm does not assume that the movement of the hosts is known.
1.4 Motivation
In an ad-hoc network, the hop by hop communication may not be possible because the neighboring hosts may be disconnected. Instead of statically waiting for network reconnection, a host can change its trajectory based on the knowledge about other hosts trying to achieve the network connection actively. We believe that kind of active message transmission is useful for applications that require urgent message delivery and involve cars and robots, such as field operations or emergency relief.
This paper describes how the trajectory change can be used to transmit messages in disconnected ad-hoc networks. We present two methods to solve the problem. The first uses the full knowledge of the motions of the mobile hosts, or with some limited errors. Location update is employed in the second method where the full knowledge is unknown. These algorithms avoid the traditional waiting and retry method, which is intolerable in some emergency case.
1.5 Contribution
Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.
1.6 Sections [Organization of Paper]
Chapter 1 explains the motivation behind the thesis topic, as well as the purpose of this thesis. Also, outlined are the contents of different chapters that form the thesis.
The remainder of this paper is organized as follows. Section 2 introduces the related work. The message transmission algorithm with full knowledge of the host motions is described in Section 3. Section 4 presents the performance evaluation of the algorithms when they operate with imprecise information about the hosts’ locations. The message transmission algorithm without full knowledge of the host motions is analyzed in Section 5. Section 6 evaluates the performance. Section 7 concludes the paper.
RELATED WORK
[2.1] Minimum spanning trees of moving points in the plane.
Author: Jyh-Jong Fu and R. C. T. Lee
They had given Consideration is given to the following problem. Preprocess n moving points in a plane, such that the Euclidean minimum spanning tree of these points at a given time t can be reported efficiently. In the result, if the moving points are in k-motion, after an O(kn/sup 4/ log n) time preprocessing step and using O(m) space to store the preprocessing result, the Euclidean minimum spanning tree at t can be reported in O(n) time, where m denotes the number of changes of the Euclidean minimum spanning tree of these points from time t=0 to time t= infinity.
[2.2] A new routing protocol for the reconfigurable wireless network
Author: Z. J. Haas
Ad hoc networks are characterized by dynamic topology caused by node mobility, multihop wireless connectivity and channel non deterministic behaviour (Interference, multipath, hidden and exposed node problem makes the wireless channel very difficult to predict)This behaviour of Ad hoc networks must be analyzed in detail as a result of pairing of the selected MAC and Routing protocols. We focus our studies in the routing layer while closely observing the developments in MAC layer. We present and examine analytical simulation results for the routing protocols DSR, AODV and ZRP, especially focusing in ZRP and the impact of some of its most important attributes to network performance, using the well known network simulator QualNet.
[2.3] Dynamic source routing in ad-hoc wireless networks
Author : D. B. Johnson and D. A. Maltz
There has been a lot of work in the past on routing in ad-hoc networks [3, 2, 9, 11, 12, 13]. Routing algorithms have to cope with the typical limitations of wireless networks: high power consumption, low wireless bandwidth, and high error rates. The existing routing algorithms can be categorized by when the routes are determined. A pro-active algorithm probes the routes periodically. The message sent from one host to another can take the path which is already in the routing tables. A reactive algorithm triggers route searching when a host sends a message. The message can be sent after a route is discovered. Hybrid algorithms combine the pro-active and reactive methodologies. The algorithms are generally based on the link-state information between the neighboring hosts. Some other interesting algorithms make use of the GPS1 location information. LAR limits the search for a route to the “request zone”, determined based on the expected location of the destination node at the time of route discovery. By using the GPS location information, a host can make decisions on whether it will forward the message to its neighbors or discard it.
[2.4] A First Course in Stochastic Processes.
Author : S. Karlin and H. M. Taylor
The purpose, level, and style of this new edition conform to the tenets set forth in the original preface. The authors continue with their tack of developing simultaneously theory and applications, intertwined so that they refurbish and elucidate each other.
The authors have made three main kinds of changes. First, they have enlarged on the topics treated in the first edition. Second, they have added many exercises and problems at the end of each chapter. Third, and most important, they have supplied, in new chapters, broad introductory discussions of several classes of stochastic processes not dealt with in the first edition, notably martingales, renewal and fluctuation phenomena associated with random sums, stationary stochastic processes, and diffusion theory.
[2.5] Modeling and analysis of active messages in volatile networks
Author : C. Okino and G. Cybenko
They proposed approach to message transmission in wireless networks extends the concept of an “active message” introduced by ([10]). An active message is a communication strategy based on mobile agents, which has been proposed to handle the network disconnection in the wireless network. The idea is to use light weight mobile agents as the message carriers. The active message is capable of jumping from one node to another according to the message path which is defined by a routing algorithm. The message is forwarded hop by hop with the possibility that it may reside on some intermediate node due to the loss of a network link.
[attachment=26259]
INTRODUCTION
1.1 About the Topic
Mobile computers often disconnect from the network, and when they reconnect, they might find themselves with a radically different network connection in terms of bandwidth, reliability or latency. Approaches to cope with the transmission of data in mobile, wireless networks include traditional techniques such as try, timeout, sleep, retry, . . ., and wireless routing algorithms. The simple try, timeout, sleep, retry loop can often fail particularly if the system does not happen to retry connection during a brief reconnection period. Waiting may be disastrous in some emergency cases.
The current wireless networking solutions are not sufficient, because an entire path to the destination machine has to be available. Suppose you want to transmit data from machine Ms to machine Mg and the path includes at least one intermediate node, say machine Mi (this is often the case in wireless networks because of range limitations.) In order for the transmission to be successful, the connections between Ms and Mi and between Mi and Mg have to be available at the same time. The probability of this event is much smaller than the probability that one of the two hops (from Ms to Mi or from Mi to Mg) is open.
1.2 Application
We believe that this approach to communication is useful for the following two types of distributed applications.
(1) In the case when most of the network is connected (such as a well-maintained framework for a sensor network) , while some hosts are dispersed away from the framework, we do not have too many trajectory modifications to relay messages.
(2) In the case when the distance between two hosts is slightly larger than the transmission range, hosts need to move small distances to relay messages.
1.3 Basics of Topic
In this paper, we explore the possibility of changing the trajectories of the hosts in a dynamic disconnected ad-hoc network to transmit messages among hosts. We show how the information about the motion of the destination host can be used to determine how the message can be sent by the cooperation of the intermediate hosts. We seek to minimize the trajectory modifications in order to transmit a message.
Two algorithms are studied in the rest of the paper. In the first algorithm, we assume the information about the motions and locations of hosts is known to all hosts, or can be estimated with some error parameters. The second algorithm does not assume that the movement of the hosts is known.
1.4 Motivation
In an ad-hoc network, the hop by hop communication may not be possible because the neighboring hosts may be disconnected. Instead of statically waiting for network reconnection, a host can change its trajectory based on the knowledge about other hosts trying to achieve the network connection actively. We believe that kind of active message transmission is useful for applications that require urgent message delivery and involve cars and robots, such as field operations or emergency relief.
This paper describes how the trajectory change can be used to transmit messages in disconnected ad-hoc networks. We present two methods to solve the problem. The first uses the full knowledge of the motions of the mobile hosts, or with some limited errors. Location update is employed in the second method where the full knowledge is unknown. These algorithms avoid the traditional waiting and retry method, which is intolerable in some emergency case.
1.5 Contribution
Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.
1.6 Sections [Organization of Paper]
Chapter 1 explains the motivation behind the thesis topic, as well as the purpose of this thesis. Also, outlined are the contents of different chapters that form the thesis.
The remainder of this paper is organized as follows. Section 2 introduces the related work. The message transmission algorithm with full knowledge of the host motions is described in Section 3. Section 4 presents the performance evaluation of the algorithms when they operate with imprecise information about the hosts’ locations. The message transmission algorithm without full knowledge of the host motions is analyzed in Section 5. Section 6 evaluates the performance. Section 7 concludes the paper.
RELATED WORK
[2.1] Minimum spanning trees of moving points in the plane.
Author: Jyh-Jong Fu and R. C. T. Lee
They had given Consideration is given to the following problem. Preprocess n moving points in a plane, such that the Euclidean minimum spanning tree of these points at a given time t can be reported efficiently. In the result, if the moving points are in k-motion, after an O(kn/sup 4/ log n) time preprocessing step and using O(m) space to store the preprocessing result, the Euclidean minimum spanning tree at t can be reported in O(n) time, where m denotes the number of changes of the Euclidean minimum spanning tree of these points from time t=0 to time t= infinity.
[2.2] A new routing protocol for the reconfigurable wireless network
Author: Z. J. Haas
Ad hoc networks are characterized by dynamic topology caused by node mobility, multihop wireless connectivity and channel non deterministic behaviour (Interference, multipath, hidden and exposed node problem makes the wireless channel very difficult to predict)This behaviour of Ad hoc networks must be analyzed in detail as a result of pairing of the selected MAC and Routing protocols. We focus our studies in the routing layer while closely observing the developments in MAC layer. We present and examine analytical simulation results for the routing protocols DSR, AODV and ZRP, especially focusing in ZRP and the impact of some of its most important attributes to network performance, using the well known network simulator QualNet.
[2.3] Dynamic source routing in ad-hoc wireless networks
Author : D. B. Johnson and D. A. Maltz
There has been a lot of work in the past on routing in ad-hoc networks [3, 2, 9, 11, 12, 13]. Routing algorithms have to cope with the typical limitations of wireless networks: high power consumption, low wireless bandwidth, and high error rates. The existing routing algorithms can be categorized by when the routes are determined. A pro-active algorithm probes the routes periodically. The message sent from one host to another can take the path which is already in the routing tables. A reactive algorithm triggers route searching when a host sends a message. The message can be sent after a route is discovered. Hybrid algorithms combine the pro-active and reactive methodologies. The algorithms are generally based on the link-state information between the neighboring hosts. Some other interesting algorithms make use of the GPS1 location information. LAR limits the search for a route to the “request zone”, determined based on the expected location of the destination node at the time of route discovery. By using the GPS location information, a host can make decisions on whether it will forward the message to its neighbors or discard it.
[2.4] A First Course in Stochastic Processes.
Author : S. Karlin and H. M. Taylor
The purpose, level, and style of this new edition conform to the tenets set forth in the original preface. The authors continue with their tack of developing simultaneously theory and applications, intertwined so that they refurbish and elucidate each other.
The authors have made three main kinds of changes. First, they have enlarged on the topics treated in the first edition. Second, they have added many exercises and problems at the end of each chapter. Third, and most important, they have supplied, in new chapters, broad introductory discussions of several classes of stochastic processes not dealt with in the first edition, notably martingales, renewal and fluctuation phenomena associated with random sums, stationary stochastic processes, and diffusion theory.
[2.5] Modeling and analysis of active messages in volatile networks
Author : C. Okino and G. Cybenko
They proposed approach to message transmission in wireless networks extends the concept of an “active message” introduced by ([10]). An active message is a communication strategy based on mobile agents, which has been proposed to handle the network disconnection in the wireless network. The idea is to use light weight mobile agents as the message carriers. The active message is capable of jumping from one node to another according to the message path which is defined by a routing algorithm. The message is forwarded hop by hop with the possibility that it may reside on some intermediate node due to the loss of a network link.