Strategic Pricing to Stimulate Node Cooperation in Wireless Ad Hoc Networks
Mingmei Li, リ ミングメイ · SOKENDAI (Graduate University for Advanced Studies) · 2007
In wireless ad hoc networks, all nodes cooperate to provide network services. Due to the limited radio transmission range, data packets are usually forwarded through multiple relay nodes before they reach the destinations. If a node always serves as a relay to transmit the packets, it may quickly use up its own energy and other resources. Therefore, some nodes use a selfish approach: they try to avoid forwarding the packets. Such selfish behavior would probably cause the network to break down. Selfish nodes are common within ad hoc networks because they are managed by different authorities. In this thesis, the node cooperation problems are analyzed in two steps: 1) a game theoretic analysis is provided to stimulate node to cooperate; 2) a price- demand function based incentive model is proposed to optimize the nodes' service demand and service provision, and encourage the relay nodes to be honest. Firstly, a game theoretic analysis is proposed to study node cooperation. In the related chapter, a "payment and compensation" scheme is used as a less-aggressive way to avoid nodes' non-cooperative behavior. It is assumed that once a packet is sent from a source node, the packet is associated with a sending fee, i.e, when a node needs sending the packets as a source node, a sending fee is required (e.g. reasonably some money). The fee is adjustable according to the network status, whereas the node can also accept or reject the fee. In order to induce voluntary forwarding, the network will also compensate the nodes who consume their energy in forwarding the packets for others. If I think the sending fee as the penalties to the source nodes and the compensation fee as the encouragement to relay nodes, then local optimization of the node, (the desired performance plus the compensat,ion then minus the cost to be paid) will yield an optimal point. Each node can only select its own packet generation strategy, however the final utility of each node is determined by the strategy set constituted by the other nodes. With the game theoretic analysis, I found that by introducing an incentive pricing policy "payment and compensation" the relay nodes have less motivation to drop the packets. However, I also found that game theoretic literature may not be directly applicable in the scenario where cheating nodes exist and how to reasonably charge the source nodes and compensates the relay nodes. Therefore, secondly, a price-demand function based incentive model (PDM) is proposed. In the PDM model, the network is modeled as a market, where the pricing is determined by the source node's demahd and the relay node's service supply. The source nodes make use of a price-demand function, which allocates payments to the service provider (relay nodes). The relay nodes are encouraged to cooperate in the PDM model, which is based on the assumption that each relay node wishes to maximize its payoff. Then the source nodes can optimize their prices and the number of sending packets to satisfy the relay nodes' payoff requirement. Once the payoff requirements of the relay nodes are satisfied, the relay nodes have no reason to be selfish. In the PDM model, a source node that has packets to send initially broadcasts RREQ in the network. Once the relay node(s) are selected, each relay node replies to the source node for its forwarding cost. Then the source node calculates the price of the sendihg packets it will pay for each relay node and the number of packets it will send. According to the source nodes' demand, it chooses the route with the lowest payment or the route with the la'rgest number of sending packets. The PDM pricing model seeks to address two main issues: 1) to determine how much to charge the source nodes and how much to compensate the relay nodes; 2)to avoid the relay nodes to dishonestly report their forwarding costs. Hence, the contributions are summarized as follows: 1) The relay nodes intend to dishonestly report their forwarding cost to gain a high payoff from the source nodes, which obviously contradicts with the motivation to stimulate cooperation. In the PDM model, however, the relay nodes will have no reason to report a false forwarding cost, since only telling the truth guarantees the relay nodes' final payoff. Such a property is shown by the proof. 2) The PDM pricing model reflects the relationship between the service demand of the source nodes and the service supply of the relay nodes. The PDM model can save money for the source nodes for sending the packets, which is indicated by the simulation results.