Efficient Scheduling of Pigeons for a Constrained Delay Tolerant Application

After disasters (e.g., earthquakes, fires, tornadoes) happen, it is urgent to rescue people and protect property. To ensure the rescuing work timely and correctly executed, accurate live information (e.g., in the format of videos) is needed by the commanding headquarter. As the instant communications of large amount of message is usually unrealistic, especially after the disasters which probably destroy the communication infrastructure, a feasible solution is to send special vehicles (like helicopters) to the disaster areas to collect the information. This special type of communication belongs to the range of delay tolerant communications.

Pigeon networks [1, 2], which borrow the ancient idea of employing pigeons as the communication tool, can be viewed as a special type of delay tolerant networks (DTNs) [3] that use special-purpose message carriers. Of course, the "pigeons'' used here are not the real pigeons. Instead, they are vehicles that are equipped with much better moving ability and partial instant wireless communication ability. For instance, it can be an unmanned aviation vehicle or a robotic insect.

The communication in a DTN is achieved through the mobility of nodes since two nodes can only communicate when they are close enough. This mobility has two modes: random mobility and controlled mobility. Examples of random mobility include epidemic routing [4] and the naturally mobile sensor networks [5]. For the controlled mobility mode, usually special purpose message carriers like message ferries [6] are used and they can follow desired routes to pick up or deliver messages.

The mobility of a pigeon can be controlled, which is similar to the message ferry [6]. However, the difference is that a pigeon network has the character of being private and secure [1, 2], which is especially suitable for the purpose of disaster rescue and recovery. Thus, in the remained part of this paper, pigeon is used in place of the vehicle mentioned above.

Although the rescuing task has to be time tolerant due to the long time (compared with instant communications) needed by the travel of pigeons, the delay that can be tolerated is still limited. For example, the best time to rescuing people in an earthquake disaster should be within 48 hours, and this limit is largely shortened (two hours) if someone is wounded or if the buildings that people are locked in are in dangerous situation. In conclusion, this becomes a constrained delay tolerant problem, and the delay is the most important metric to be considered for this type of problems.

Superficially, the delay that each message demand suffers is the only important factor, and so it sounds like a pigeon can stay in an area as long as it can to make sure that the demands in that area can be satisfied. However, another fact is that the pigeons available for the disaster rescue and recovery tasks are also limited. If the pigeons can be schedule more efficiently, more disaster areas can be covered. As a result, more lives and properties can be saved if the pigeons are scheduled more efficiently.

The problem presented in this paper is very close to the dynamic vehicle routing problem (VRP) [7‐9]. The arrival of new demands is stochastic, and there is no ending of time horizon. Thus, a complete solution of routing and scheduling plan like in the static vehicle routing problem is impossible. This character makes policies rather than the solution the primary goal to pursue in the area of dynamic VRP. The representative works include those by Bertsimas and van Ryzin [10, 11] and extended work by Swihart and Papastavrou [12].

While this paper borrows the important results from Bertsimas and van Ryzin [10, 11] and Swihart and Papastavrou [12], it is also obviously different.

( ) The problem in this paper is more like a dynamic traveling salesman problem (TSP) rather than a dynamic VRP. The main reason is that essentially there is no capacity constraints. The amount of information that can be picked up by a pigeon is very large due to the advanced storage technique. Thus, it can be viewed as if there is no limit.

( ) There is only one destination node, which is the headquarter. All pigeons must start from the headquarter and deliver all information to the headquarter rather than random destinations like in [12]. This difference makes the delay considered here totally different from what are in [10, 12].

( ) Messages to be picked up have their deadlines that should not be violated. In contrast, in [10, 12], the only goal is to minimize the average delay.

The rest of this paper is organized as follows. The basic model is described in Section 2, and the analyses on the two main strategies—the on-demand strategy and the waiting-based packing strategy—are presented in Sections 3 and 4, respectively. In Section 5, the numerical results are shown, and Section 6 concludes this paper.

Due to the consideration of safety for emergency staff and the availability of resources, the headquarter for information precessing and rescue commanding is usually far away from the disaster area. As shown in Figure 1, is the travel time for a pigeon between the headquarter and the disaster area with the assumption that the velocity of a pigeon is constant. The pigeon has enough communication ability to know the arrivals of messages on the information collectors in the disaster area immediately. For the facility of analysis, the disaster area is assumed to be a square with the size being , which is similar to most study on dynamic vehicle routing problem like in [10, 12]. The demands are generated in the disaster area with average rate being , and the time spent on picking up each message is . For each demand generated, it must be delivered to the headquarter within time . is also called the deadline of a message in the following part of this paper.

A key question here is how a pigeon should be scheduled to pickup and deliver messages. If the goal is merely guaranteeing minimum delay for each message as in [10, 12], it is often beneficial to let the pigeon start picking up the messages whenever they are available. This approach can be viewed as an on-demand strategy.

In the following part of this paper, these two strategies are evaluated. The main performance metrics studied include the maximum throughput of the system, the maximum number of messages allowed to be picked up on each trip, and the comparison of efficiency of these two strategies under different load cases.

Denote the time point that the message demands firstly generated as time ; a pigeon is sent out to the disaster area right away. The dynamic flow of traveling and pickup is described in Figure 2.

With the assumption that a pigeon is able to communicate with the information collectors, it is reasonable for a pigeon to determine the messages to be picked up when it arrives at the disaster area. The pickup strategies in the disaster area is a dynamic traveling salesman problem (DTSP) [7]. As shown by Bertsimas and van Ryzin [10], possible strategies include Shortest TSP, Nearest Neighbor, and Space Fill Curve. Since the focus of this paper is analysis of the scheduling of the pigeon, only the Shortest TSP policy is considered due to its tractability on analysis.

The on-demand strategy studied above has at least two disadvantages: ( ) the pigeon might never get any rest; ( ) the number of messages picked up on each trip can be quite limited, which causes low efficiency of the pigeon. To avoid these shortcomings, a waiting-based packing strategy is introduced and analyzed in this section.

As shown in Section 3.1, the number of messages picked up on each trip for the on-demand strategy is . If the pigeon waits some additional time in the disaster area (or the headquarter), more demands can be formed during the pigeon's waiting (can be for taking a rest, or going to other areas for a trip). Thus, the amount of messages to be picked up is more than . In the practical operation, a fixed amount of messages (or say a batch with size ) can be packed for the pigeon to pick up. An important constraint, however, is that the deadlines of messages should not be violated.

In this section, the above analysis is firstly verified with the simulation results, in which CSIM [15] simulation tool is employed. After the verification of correctness, the improvement of efficiency by the waiting-based packing scheme is shown.

The main parameters used here are the following: the time spent on picking up a message is hour (36 seconds), the single trip time between the headquarter and the disaster area is hour (12 minutes), and the deadline for a message is 4 hours. The travel time of a side of the disaster area, which is normalized as , is 0.05 hour (3 minutes).

The dynamic scheduling strategies of pigeons for information pickup and delivery in the disaster area is analyzed. The upper bound of traffic that can be supported under the deadline constraints for the basic on-demand strategy is given through the analysis and verified by the simulations. Based on the analysis of the basic on-demand scheduling strategy, a waiting-based packing strategy is introduced. Although the latter strategy could not improve the maximum traffic rate that a pigeon can support, it improves the efficiency of the pigeon largely.

Possible future works include more detailed investigations of the dynamic routing strategies other than the shortest TSP policy and the effect of the different distributions of the arrival rate, service rate, deadlines on the conclusion, and bounds obtained in this paper.