Per-Hop Reversed Packet Auctions for Cooperative Routing in Mobile Wireless Networks

Abstract

Many applications could benefit from multi-hop communications through users' mobile devices. A key issue is how to incentivize users to cooperate in both routing and relay of messages by sharing their device's precious resources. Previous works on the subject have either tackled cooperation in the relay of messages alone or in both routing and relay functionalities. In the latter case, path selection is usually carried out at the destination node, which renders significant delays because the selected path needs to be conveyed all the way back to the source node before any data packet can be transmitted. This is certainly unsuitable in mobile scenarios. This paper presents the performance of the “Tightness” strategy, which allows the routing and relaying of messages “on-the-go”, via per-hop reversed packet auctions. At each hop, the sender asks for bids from potential relays according to a “budget” attached to the data packet, through which the auction winner gets paid and can pay for others in subsequent auctions. The auction winner is chosen not only based on bid value, but also on the estimated relay's likelihood to deliver the packet to destination. Likewise, each potential relay makes a bid considering its own chances to deliver the packet to destination. A fine is also announced in every auction, that must be paid by all relays if the packet is not delivered to destination within a “deadline” expressed in number of hops. The performance of the Tightness strategy is evaluated for both static and mobile scenarios and compared to two baseline strategies according to different performance metrics.

Keywords

• Auctions
• cooperation
• routing
• wireless networks