Font Size: a A A

Routing Of Delay Tolerant Network For Catastrophe Rescue Scenario

Posted on:2014-12-22Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y WangFull Text:PDF
GTID:1108330479479663Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
In recent years, natural disasters frequently occur all around the world, which causes greatly economy loose of human society. Usually, the fundamental communication equipment will be totally damaged by these catastrophes such as series earthquake, rock flues and hurricane. And the rescue procedure will be precluded due to the lack of communication support. It is very important to research the communication problem in catastrophe rescue scenario. Traditional TCP/IP based network protocols assume that there is at least one end-to-end route between the source and destination node, and the link should be stable. But in the catastrophe rescue scenario, the link will be frequently interrupted due to the serious communication environment. The traditional network(e.g., Ad hoc network)protocol cannot work in such scenario, and it cannot provide communication for the rescue work. Such networks like catastrophe rescue scenario with frequently interrupted link and high message latency are called the Delay Tolerant Network(DTN), which is drawn more and more attention in recent years. DTNs use “store-carry-forward” paradigm to deliver messages, and extra node called message ferry could be employed into DTN to enhance the network performance. Message ferries are controllable mobile nodes equipped with much more resource(e.g., energy and storage space) than the regular nodes.It can proactive move to the regular nodes, receiving and delivering the message between them. And the message delivery ratio will be greatly enhanced and the message delay will be greatly reduced. In catastrophe rescue scenario, in order to reduce the message delay, the Unmanned Aviation Vehicle(UAV) equipped with communication equipment can act as message ferry to communicate with the rescue groups, and carry the message to the command post for further processing.This paper concentrated on the mobility model and message ferry based routing, and studied the communication in catastrophe rescue scenario. The main work and contributions are as follows:1. Mobility models which aim to simulate the mobility patterns of mobile nodes in the real environment, play an indispensable role in simulation based mobile wireless networks performance evaluation. By adopting different mobility models, researchers can easily evaluate the performance(e.g., routing and topology) of the wireless network under different scenarios. Although lots of mobility models have been proposed during the past decade, there is no model can well model the catastrophe rescue scenario. This work analyzes the mobility patterns of rescue group and transport group in the catastrophe rescue scenario, and proposes the Random Way Point with Base Point(RWPBP) mobility model to model these characteristics.RWPBP can perform various movement patterns by configuring different parameters, including the movement patterns of the two groups in catastrophe scenario, as well as the classic Random Way Point mobility model.2. It had been shown that, in the simulation based studies of network performance using mobility model, the simulation result at the beginning is dramatically different from that at the end. The reason is that, at the beginning, the speed and spatial distributions of the nodes are dominated by the initial setup of the mobility model. After a long time running, the speed and location distributions of the nodes will be convergence to a steady state, which is called stationary distribution. Stationary distribution is an indispensable building block of the study of mobility model. It can give a deep understanding of the simulation results and simulation under stationary distribution can generate more accurate results. We mathematically analyze the speed and spatial stationary distributions of the nodes and derive explicit expressions for the one dimensional case. In order to keep the stationary distribution through the entire simulation procedure, we provide strategies to initialize the speed, location and destination of the nodes at the beginning of the simulation. These strategies can avoid discarding the initial observed results.3. The previous studies of DTN always assumed that the nodes in the simulation scenario communicate with each other. But in catastrophe rescue scenario, the nodes need to communicate with the base point other than the other nodes. In the previous message ferry based studies, the route of the ferry is always designed as a simple cycle, which starts from the base point, accesses all the nodes and moves back to the base point. We found that the simple cycle ferry route cannot guarantee the minimum average weighted delay of the message. So we proposed designing closed walk ferry route, which may contain more than one simple cycle, to reduce the average weighted delay. We formulated this problem as Closed Walk Ferry Route Design(CWFRD) problem, proved it to be NP-hard problem, gave the Integer Linear Programming(ILP), and proposed several heuristic algorithms for it.The experimental results showed that the average weighted delay could be greatly reduced by designing a closed walk ferry route.4. In the catastrophe rescue scenario, the rescue groups might sparsely distribute in a large area. The UAV which acts as message ferry, cannot be equipped with infinite energy, and it might not be able to access all the nodes in one tour. Even the energy is not sufficient for the ferry to finish the closed walk route designed by CWFRD.The UAV needs to move back to the base point to get the energy refilled. And then in this paper, we discussed the ferry route design problem with the energy constraint, which is called the Energy Constrained Ferry Route Design(ECFRD)problem. We not only consider how to reduce the average weighted delay, but also how to minimize the maximum message delay. We formulated these two problems as ECFRDAW Dproblem and ECFRDMax Dproblem, respectively. We proved them to be NP-hard problems, showed the ILP formulations of the two problems, and proposed several heuristic algorithms for them.
Keywords/Search Tags:Catastrophe Rescue, Delay Tolerant Network, Message Ferry, Mobility Model, Stationary Distribution, Closed Walk, Energy Constraint, Route Design
PDF Full Text Request
Related items