A Message Forward Scheduling Based on a Secretary Problem for Mobile Relay Nodes

A store-carry-forward networking is considered in which each message arriving at a wireless access point (AP) from some source is forwarded to a car passing near the AP and is potentially delivered by the car to the destination of the message along the roads. Such network systems exploiting cars as mobile relay nodes are of practical importance because the cars have sufficient power and storage and the traffic volume and mobility pattern of the cars are predictable to some extent. However, while a message is forwarded to a mobile node that potentially relays it, the mobile node may or may not pass near the destination of the message, and the success of the delivery is uncertain. In addition, although forwarding multiple (N) copies of a message to N different mobile nodes may help the success delivery, this naive approach is not always effective when the number of messages that can be forwarded from the AP to a mobile node is limited due to a short contact time and/or a low wireless transmission capacity. In the present paper, therefore, we propose a message forward scheduling to improve the success delivery of messages within a finite lifetime, assuming that (i) the AP can estimate the relative magnitude (rank) of delivery success probability of each mobile node for a message, and (ii) the number of messages forwarded from the AP to a mobile node is restricted. The proposed scheme can select a mobile node with a higher delivery probability by applying the concept of Secretary Problem, an optimal sequential stopping rule without recall which minimizes the expected rank of the selected observation, i.e., a mobile node. The effectiveness of our proposed scheme is investigated through simple numerical simulations.