Autonomous and rational routing for improving performance

Published:

I. INTRODUCTION

Most of the ad-hoc routing protocols proposed in the current literature presume that nodes are cooperative and are always willing to contribute their own resources (e.g., power, bandwidth, storage) in support of routing processes. In such settings, nodes are assumed to be truthful in the sense that intermediate nodes do not alter the content of forwarded packets and do not mischaracterize routing parameters so as to gain an advantage with respect to routing. However, in real settings, nodes of an ad-hoc network are under the control of individuals, who may not necessarily be cooperative. Indeed, such individuals are likely to be rational, selfish, or even malicious. Malicious nodes are those bent on disrupting the network functionality, whereas rational, selfish nodes are those that do not aim to disrupt the network, but are simply interested in maximizing the utility they beget from the network, even if doing so requires them to be untruthful.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Besides cooperative routing protocols, there have been several proposed routing protocols that provide incentives for nodes to help out in carrying the network load. Such incentives can be in the form of payment for cooperation [1, 7, 4, 8, 19, 18] or in the form of punishment (disincentives) for non-cooperation [3, 2]. In this paper, we focus on payment-based models, where nodes are rewarded for their help. In these models as well as in ours, a node would be willing to inform other nodes of its private (secret) costs for providing help in order to get paid, and a node would be willing to lie about its (or others') costs if this might lead to a higher payment.

To provide incentives for cooperating nodes, the routing problem is treated as a game where the nodes in the network are the players, each player's utility is the payments it receives, and the social optimum is to choose the most cost efficient route for packet delivery. Since there can be multiple routes between any pair of nodes in the network, we need to define a set of rules for the nodes to follow to choose this most cost efficient route. Moreover, we need to define the payoff functions used to calculate the payments for cooperating nodes. Mechanism design [9, 14] can be used to define the game's rules and payoff functions such that the social optimum is a dominant strategy for each player. A dominant strategy means that no player has an incentive to deviate from that strategy.

II. RELATED WORK

Routing protocols for ad-hoc networks vary greatly in design and in the assumptions they make about the network. Several protocols assume that the nodes in the network are selfless (altruistic) and are willing to help other nodes when such help is needed [15, 16, 12, 13, 11]. The Destination-Sequenced Distance-Vector routing (DSDV) protocol [15] is a proactive protocol which requires regular update of the routing table at the nodes. The disadvantages of such a design are that it consumes the power resources of the nodes and causes a significant communication overhead even when the network is idle. On the other hand, the Ad-hoc On-demand Distance Vector (AODV) protocol [16] and the Dynamic Source Routing protocol [12] are both reactive protocols, wherein routes are established on demand, thus reducing the communication overhead introduced by DSDV. In DSR, all the route information is kept in the control packets. This means that control packets grow larger as the route grows longer. This is in contrast to AODV where all route information is stored locally at the nodes and the control packet sizes remain constant. Therefore, AODV is largely considered a faster and less power-consuming protocol than DSR [13, 11].

As we alluded earlier, in realistic settings, nodes are expected to be selfish, and thus would not help unless incentivized to do so (through the use of reward or punishment mechanisms). Example mechanisms that punish non-cooperative nodes through the use of reputation-based protocols include the works described in [3, 2]. Example mechanisms that reward cooperative nodes include the works described in [1, 7, 4, 18, 8, 19]. In [4] the intermediate nodes are paid with a virtual currency called NUGLETS. In [18], Sprite is proposed which provides incentive - in a game theoretic sense - for mobile nodes to cooperate and report actions honestly. In [1], the authors used mechanism design to provide the nodes incentives in the form of payments. Intermediate nodes are paid an amount of money proportional to the amount of power resources they consume for helping in addition to a small premium. The premium is calculated using the VCG model to guarantee the truthfulness of the nodes in the network. In [7], the authors extended the protocol to provide the same incentives but with less communication overhead.

III. SYSTEM MODEL AND ASSUMPTIONS

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

We augment the model used by Anderegg and Eidenberz in [1] where the network is represented as a graph G = (V,E,w) with the set of vertices V that represent the mobile nodes in the network and the set of directed edges E which represents the unidirectional links between the nodes in the network. The weight function W : E− > R for each edge (i, j) represents the weight of the link between the node i and the node j, which is the cost of transmitting a packet from i to j.

Each node has a unique identifier i and has an individual cost of energy parameter ci. The cost of energy ci of a node i is its private type, i.e., only i knows it's true value, which is a measure of the level of inconvenience the node faces when asked to forward a packet. One of the factors affecting this measure is the level of difficulty the node faces in order to recharge its power. The payment that a node receives for helping others is proportional to its cost of energy ci; therefore, a node might lie about its true value of ci if such a lie would increase its payment.

All nodes use omni-directional antennas for communication, i.e., when a node sends a signal carrying a packet, all neighboring nodes in its transmission range receive that packet. We assume that nodes can control their signal emission power; as the node increases its emission power, its transmission range increases, and as a result more neighboring nodes receive the packets sent and vice versa. When a node i uses an emission power Pemit(i) to send a packet, the node j at distance d from i receives the signal with power given by

Prec(i,j)=K*(Pemit(i) / dα ) ----- (1)

Where K is a constant and is the distance power gradient, another constant that ranges between 2 and 6 depending on the network conditions. A node successfully receives a signal if the power of the received signal is above a certain acceptance threshold. While the acceptance threshold might differ from one node to another in the network, for simplicity, we assume that all nodes in the network agree on the same value for the acceptance threshold Precmin. If the power of the signal received exceeds Precmin, then j successfully receives the packet carried by the signal. However, the original emission power used by node i (Pemiti ) might be overvalued and less emission power could have been used to successfully send a packet to j. Node j can calculate the minimum emission power that the node i would need to use to send a packet successfully to j using the following formula,

Pmin(i,j)= (Pemit(i) * Prec(min))/Prec(i,j) ---- (2)

Once calculated, this value is sent back to i and later, i uses this value as its default emission power - if and when it needs to transmit a packet to j in the future.

The total weight of a link (i, j) is the product of the cost of energy ci and the minimum emission power that i uses to send a packet to j.

W(i, j) = ci Ã- Pmini,j (3)

As previously mentioned, in the proposed protocol nodes will be paid to forward data for others. In [1], the authors propose two payment models; either the source node is responsible for paying all intermediate nodes or some central authority -a “bank” - holds accounts for all nodes in the network and is responsible for all transactions performed on them. Any node can communicate with the bank if it is in its communication range. If the bank is inaccessible, a node is allowed to store the transaction information locally. This information is relayed to the bank as soon as the bank becomes accessible again in the future. In Ad-Hoc VCG, the authors assume that the bank will deduct the payments given to cooperating nodes from the accounts of all the nodes in the network. In this paper, we assume that the destination node is responsible for calculating the payments for each of the helping nodes and it sends the payment information to the bank. The bank credits the accounts of all the intermediate nodes and debits the accounts of the source and/or destination nodes.

IV. AUTONOMOUS AND RATIONAL ROUTING PROTOCOL

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

The Autonomous and Rational Routing protocol is an on-demand routing protocol for ad-hoc networks. The VCG payment model is used to provide incentives for nodes to help out other nodes in the network as used in [1].

A. Overview

ARR consists of three components: route discovery, data transmission and route recovery.

When a node S needs to sends data to D but D is not in the transmission range of S, route discovery begins. In route discovery, S floods the network with a request to find a path to D and payments for the intermediate nodes are calculated.

During data transmission, after the path from S to D is known, the data is sent between them and intermediate nodes get paid for forwarding the data. Whenever the destination node successfully receives a data packet, it keeps track of how much it should pay each intermediate node and when possible it notifies the bank of the payments.

Route recovery is activated when links between nodes are broken during data transmission. If the next hop node is not available for any reason (such as node failures, link failures, or node mobility), the node that detects the failure sends an ERROR packet back to the source node. Upon receipt of such an error report, the source node starts the route discovery all over again.

B. Route Discovery

The route discovery in ARR is adapted from the AODV routing protocol, which is an on demand ad-hoc routing protocol proposed by Perkins and Royer in [16]. AODV provides several advantages in ad-hoc networks such as low communication overhead and less power consumption. In ARR, the route discovery phase is divided into two separate phases: the first phase is the actual discovery phase when the most cost-efficient path between the source and destination is found.

The second phase is when the payment calculation occurs. Nodes do not have to wait for the termination of this phase to start data transmission as it can start on the completion of the first phase. The second phase can be performed offline and at any time after the first phase is completed or during data transmission.

Phase 1: Finding a route. - The first phase is similar to the route discovery phase in AODV [16] where a source node S floods the network with its request to a destination node D. Then S has to wait for D to send out a reply with the most cost efficient path between them to start data transmission.

Packets Used:

Two types of packets are used in this phase; the REQUEST and the REPLY packets.

The REQUEST packet is the packet that floods the network. In addition to the typical ID and addressing fields that constitute the Packet header, this packet contains a Cost of Energy field, in which the cost of energy of the inner source node sending the current instance of the packet. The packet also contains an Emission Power field which indicates the emission power that the inner source is using to send the current instance of the packet and a Total Weight field which represents the total weight of the path from the source node to the inner source node.

The REPLY packet is sent out by D and it contains information about the most cost-efficient path between S and D. It is only forwarded by the nodes in the best path between S and D. It contains the Packet Header, the original Request ID and the List of Costs, a list that includes the ID, cost of energy and the minimum power of each intermediate node along the chosen path.

Data Structures Used:

During route discovery, each node needs to maintain two data structures to help out in the route discovery phase.

The Best Route Cache is used to store the best REQUEST packet received for a specific request between a pair of nodes. Its key index is the Request ID + Source + Destination values of the REQUEST packet and its value is the REQUEST packet itself.

The Neighbor Cache is used to keep track of which of the nodes neighbors can provide a path to the source node. Its key index is the Request ID + Source + Destination values obtained from the original REQUEST and its value is a list of node IDs which represent the neighbors of the node that previously sent a corresponding REQUEST to the node.

Details of Phase 1:

When a source node S wishes to find a path to a destination D, it prepares the initial REQUEST packet with its cost of energy and emission power and floods it to its neighbors.

When a node j receives a REQUEST packet from neighbor i it follows Algorithm 1 to decide whether to drop the packet or forward it. The weight in the packet is updated and forwarded if the packet carries a better weight than the best weight stored in the Best Route Cache. When the destination node receives the first REQUEST from the source node, it follows the same algorithm but without forwarding the packet with the best weight, and keeps listening for other route REQUEST packets in case a better REQUEST is received from the same source node. If a better REQUEST is received, the corresponding entry in the best route cache is updated. After a timeout period expires, the destination extracts the best REQUEST it received from neighbor i from the Best Route Cache and sends out a REPLY packet with {c(i), Pmin(i,D)} to the source node through i.

-------------------------------------------------------------------

Algorithm 1

Actions performed by a node j upon receiving a REQUEST packet from node i

-------------------------------------------------------------------

if REQUEST has no new information then

drop REQUEST

else

Add neighbor i to the Neighbor Cache

Calculate Pmin(i,j) = Pemit(i) * Prec(min) / Prec(i,j)

Calculate w = total weight of path from S to j through i

best = total weight of the best REQUEST stored in the Best Route Cache

if best is null then

Replace Pemit(i) with Pmin(i,j) in REQUEST

Add REQUEST to the Best Route Cache

Forward REQUEST packet with c(j) and Pemit(j)

else

if w < best then

Replace Pemit(i) with Pmin(i,j) in REQUEST

Replace entry in the Best Route Cache with the current REQUEST

Forward REQUEST packet with c(j) and Pemit(j)

end

end

end

-------------------------------------------------------------------

Each intermediate node i receiving the reply packet from node j will follow Algorithm 2 to decide the uplink node to which the edited reply should be forwarded.

-------------------------------------------------------------------

Algorithm 2

Actions performed by a node i upon receiving a REPLY packet from node j.

-------------------------------------------------------------------

best = corresponding best REQUEST packet from Best Route Cache

k = inner source of best

Forward REPLY to k with {c(k), Pmin(k,i)} added to the list of costs

-------------------------------------------------------------------

Once the source node receives the REPLY packet, it can enter the data transmission phase and does not have to wait for the second phase to end.

Phase 2: Payments Calculation.

While route discovery allows the destination D to identify the best (most cost-effective) path, D is unable to calculate the payments to the intermediate nodes along that path. As we indicated earlier, in ARR these payments are based on a VCG model, requiring the calculation of the second-best path when each node on the best path is excluded. This process is carried out in Phase 2 of the ARR protocol. This phase is similar to the route discovery performed in phase 1, except that it is done in the opposite direction (from D to S) and the request packets have constraints to not include certain nodes in the discovery.

To start phase 2, S sends to D information about the intermediate nodes in the best path between them. This is done by piggy-backing a CONFIRM packet to the first DATA packet send to D.

Packets Used:

We introduce 3 types of packets in this phase, namely, the CONFIRM, FIND and FOUND packets. The CONFIRM packet is piggy-backed with the first DATA packet sent by the source node S. It is used to inform the destination node D about the details of the intermediate nodes in the chosen shortest path (SP) between S and D. There is only one field in the CONFIRM packet, namely the list of costs that were obtained from the REPLY packet in phase 1. When sending a DATA packet, the source node S signs and appends this list to the packet.

The FIND packet is used to discover whether a path between two nodes without a certain intermediate node. Its fields are the Packet Header with multiple inner destinations, the Excluded Node, the original Request ID and the Hop Count which is used to calculate the time out period the node will spend before sending the FOUND packet.

The reply to the FIND packet is the FOUND packet which is used by nodes in the second phase to notify the originator of the FIND packet that a path is indeed found excluding a specific node and it also carries the total weight of that found path. Its fields are the Packet Header with multiple inner destinations, the Excluded Node, original Request ID, Total Weight of the path and the Cost of Energy and Emission Power of the node sending the FOUND packet.

Data Structures Used:

 During phase 2, each node needs to also maintain similar data structures as those kept in phase 1 but for the FIND and FOUND packets.

The first data structure is the Find Neighbor Cache which is used to track which neighbors sent similar FIND packets to the node. It is used to keep track of which neighbors have previously sent a FIND packet, to guarantee that only one FIND and one FOUND packets are sent for each request. Its index key is also the Request ID + Source + Destination values of the original REQUEST packet and its value is a list of neighbors.

The second data structure is the Best Found Cache which is used to store the best FOUND packet received so far for each corresponding FIND packet. The index key of this data structure is also the Request ID + Source + Destination values of the original REQUEST packet and its value is the best FOUND packet received.

Details of Phase: Once the destination node D receives the CONFIRM packet, it extracts the list of intermediate nodes in the shortest path between the source and the destination (SP). For each intermediate node i, D will search for a best path from S to D without that intermediate node (SP−i).

The destination extracts from its Neighbor Cache the set of neighbors N that have paths to the source node and for each intermediate node i obtained from the CONFIRM packet, D will send a FIND packet excluding i to be sent to all the nodes in the set N − i as shown in Algorithm 3.

-------------------------------------------------------------------

Algorithm 3

Actions performed by a the destination upon receiving a CONFIRM packet

-------------------------------------------------------------------

Prepare FIND packet excluding i

Send FIND to all neighbors in the set N-{i} with Hop Count of 1

Start a timer which indicates the end of phase 2 for D

-------------------------------------------------------------------

When an intermediate node i receives a FIND packet from j, it will follow Algorithm 4 to decide whether to drop the packet or forward it to all the nodes in the set of neighbors obtained from the Neighbor Cache.

-------------------------------------------------------------------

Algorithm 4

Actions performed by a node upon receiving a FIND packet

-------------------------------------------------------------------

Add j to Find Neighbor Cache if FIND has been received before then drop FIND packet

else

Get set of neighbors N from Neighbor Cache for corresponding request

Forward FIND with incremented Hop Count to the neighbors N - {excluded node}

Start a timer with a value inversely proportional to Hop Count of original FIND

end

-------------------------------------------------------------------

When the source node receives a FIND packet with itself in the Destination field, it will send a FOUND packet to the Inner source of the FIND packet.

During the timeout period, when a node j (including the destination node D) receives a FOUND packet from node i, it will decide whether to store the FOUND packet in the Best Found Cache or just drop it according to Algorithm 5.

When the timer at node i stop, i will extract the best FOUND packet received from the Best Found Cache and extract the set of neighbors from the Find Neighbor Cache. Then the node updates the fields in the FOUND packet and sends it to all the neighbors in list extracted from the Find Neighbor Cache and clears its caches.

-------------------------------------------------------------------

Algorithm 5

Actions performed by a node upon receiving a FIND packet

-------------------------------------------------------------------

Calculate Pmin(i,j)

Update Total Weight field to new total weight of path (w)

best = weight of FOUND packet in Best Found Cache

if best is null then

Add FOUND to Best Found Cache

else

if w<best then

Replace entry in the Best Found Cache with the current FOUND

end

end

-------------------------------------------------------------------

When the D finishes its timeout period, it takes the information in the Best Found Cache and calculates the payments that should be made to each intermediate node using the following formula:

M(i) = |SP-i| - |SP| + ci * Pmin(i,j) ----(4)

The value |SP−i| is obtained from the FOUND packets in the Best Found Cache and the values |SP|, ci and Pmin(i,j) are obtained from the CONFIRM packet received at the beginning of the phase.

V. SIMULATION RESULTS

An event-based simulator was designed to simulate ad-hoc networks and to test the performance of various routing protocols. These assumptions are unrealistic since in ad-hoc networks, nodes are likely to be autonomous and rational (selfish) routing (ARR) or Constrained Selfish Routing (CSR) protocol so using this simulator, the performance of ARR/CSR is compared to Ad-Hoc VCG [1]. The simulations were run in a closed environment in which any number of simulated nodes moves freely.

The mobility model used in the simulator is adopted from the Random Walk model [5]. Initially, each node picks a random direction (θ) taken from a uniform distribution on the interval [0, 2Π]. The node moves in the chosen direction for a fixed period (default is 4 seconds) and then pauses for another fixed period of time (a control variable). Next, the node picks a new random direction (θ') taken from a uniform distribution on the interval [θ − 20, θ + 20] and repeats the same process. The reason for choosing the interval [θ − 20, θ + 20] when deciding θ' is to simulate a realistic motion.

Applications on the simulated wireless nodes are designed to send data to random destinations (picked uniformly at random) at random times, with inter messaging time picked from an exponential distribution with a mean of 10. Once a destination is chosen, the route discovery process of the simulated protocol starts.

Four sets of simulations were performed to measure the efficiency of ARR or CSR in various conditions. In all simulations, the environment is 500m Ã- 500m in size, the nodes' transmission range is 100m and the total simulation time is 100sec. The measured performance parameters are the Communication overhead which is represented in two forms: the total number of packets sent out during the route discovery phase, the total number of bytes sent out during the route discovery phase, and the Power consumption rate which measures the average rate of power consumed by the nodes during the whole simulation.

In the first set of simulations, the number of nodes in the network is varied from 8 to 12 devices, the pause time of each node is 6 sec and the total number of requests made in each simulation is 5 requests. The performance evaluation of the protocols is shown in Figure 1, Figure 2 . Each value in the graph represents an average of 5 simulation runs with different seeds within a 90th-percentile confidence interval.

The results show that as the network size grows larger, the communication overhead in ARR/CSR exhibits a nearly linear growth while Ad-Hoc VCG shows a super-linear growth. Moreover, the results prove that ARR/CSR is more power efficient than Ad-Hoc VCG because of the less communication overhead of CSR/ARR.

  1. Packet Overhead
  2. Bytes Overhead

In the second set of simulations, the number of requests made in the simulation is varied from 2 to 20 requests, the number of nodes in the network is 8 and the pause time of each node is 6 sec. The performance evaluation of the protocols is shown in Figure 3. Each value in the graph represents an average of 5 simulation runs with different seeds within a 90th-percentile confidence interval.

The results show that as the number of requests made in the network increases, the communication overhead in both CSR/ARR and Ad-Hoc VCG increases linearly. However, the degree of increase in the overhead of CSR/ARR is less than that of Ad-Hoc VCG because of the linear overhead of CSR in terms of the number of nodes in the average case compared to the super-linear overhead of Ad-Hoc VCG.

  1. Packet Overhead
  2. Bytes Overhead

In the third set of simulations, the pause time of the nodes is varied between 6 seconds and 2 seconds. In these simulations, the number of nodes in the network is set to 8 and the number of requests in the simulation is 5. The performance evaluation of the protocols is shown in Figure 4. Each value in the graph represents an average of 5 simulation runs with different seeds within a 90th-percentile confidence interval.

The results show that both protocols are stable as the mobility of the nodes increases i.e., as the pause time decreases. Moreover, CSR/ARR shows an improved performance over Ad-Hoc VCG.

(a) Packet Overhead

In the fourth set of simulations, we compare the average weights of the routes chosen by CSR to those chosen by vanilla AODV. If power was not an issue in the network, AODV would have been simpler to use. However, we consider ad-hoc networks with limited power resources. Therefore, choosing power-efficient routes is more desirable that just choosing the shortest routes. In CSR/ARR, if the cost of energy of the nodes in the network is constant, then the routes chosen are the most power-efficient routes. In these simulations the number of nodes in the network is varied from 8 to 12 devices, the pause time of each node is 6 sec and the total number of requests made in each simulation is 5 requests. The results shown in Figure 5 are obtained by comparing the average route weight of CSR/ARR to that of AODV where all nodes have unit cost of energy.

VI. CONCLUSION

The ARR protocol is an incentive-based routing protocol which provides incentives for selfish nodes in the network in a game theoretic setting. In this paper, we have shown ARR to induce truthful node behavior through the use of a VCG-based model for calculation of payments to intermediate nodes. With truthfulness guaranteed, ARR provides the most cost efficient path between any pair of nodes in an ad-hoc network with a linear lower bound of O(n) on the communication overhead, where n is the number of nodes in the network. The lower communication overhead also guarantees lower power consumption.

VII. REFERENCE

[1]. Luzi Anderegg and Stephan Eidenbenz, Ad hoc-vcg: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents, MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networking (New York, NY, USA), ACM, 2003, pp. 245-259.

[2]. S. Buchegger and J. Y. Le Boudec, Nodes bearing grudges: towards routing security, fairness, and robustness in mobile ad hoc networks, Proceedings. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2002.

[3]. Sonja Buchegger and Jean-Yves Le Boudec, Performance analysis of the confidant protocol, MobiHoc '02: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing (New York, NY, USA), ACM, 2002, pp. 226-236.

[4]. L. Buttyan and J. Hubaux, Nuglets: a virtual currency to stimulate cooperation in self-organized ad hoc networks, Tech. Report DSC/2001, 2001.

[5]. Tracy Camp, Jeff Boleng, and Vanessa Davies, A survey of mobility models for ad hoc network research, Wireless Communications Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications 2 (2002), 483-502.

[6]. Edward H. Clarke, Multipart pricing of public goods, Public Choice 11 (1971), no. 1, 17-33.

[7]. Stephan Eidenbenz, Luzi Anderegg, and Roger Wattenhofer, Incentive-compatible, energy-optimal, and efficient ad hoc networking in a selfish milieu, HICSS '07: Proceedings of the 40th Annual Hawaii International Conference on System Sciences (Washington, DC, USA), IEEE Computer Society, 2007, p. 293.

[8]. Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, and Scott Shenker, A bgpbased mechanism for lowest-cost routing, Distrib. Comput. 18 (2005), no. 1, 61-72.

[9]. Joan Feigenbaum and Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, DIALM '02: Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications (New York, NY, USA), ACM, 2002, pp. 1-13.

[10]. Theodore Groves, Incentives in teams, Econometrica 41 (1973), no. 4, 617-31.

[11]. Xiaoyan Hong, Kaixin Xu, and Mario Gerla, Scalable routing protocols for mobile ad hoc networks, IEEE Network 16 (2002), no. 4, 11-21.

[12]. David B. Johnson and David A. Maltz, Dynamic source routing in ad hoc wireless networks, Mobile Computing, Kluwer Academic Publishers, 1996, pp. 153-181.

[13]. Padmini Misra, Routing protocols for ad hoc mobile wireless networks, Tech. report, Ohio State University, 1999.

[14]. Noam Nisan and Amir Ronen, Algorithmic mechanism design (extended abstract), STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of computing (New York, NY, USA), ACM, 1999, pp. 129-140.

[15]. Charles E. Perkins and Pravin Bhagwat, Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers, SIGCOMM '94: Proceedings of the conference on Communications architectures, protocols and applications (New York, NY, USA), ACM, 1994, pp. 234-244.

[16]. Charles E. Perkins and Elizabeth M. Royer, Ad-hoc on-demand distance vector routing, In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90-100.

[17]. William Vickrey, Counterspeculation, auctions, and competitive sealed tenders, The Journal of Finance 16 (1961), no. 1, 8-37.

[18]. Sheng Zhong, Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks, in Proceedings of IEEE INFOCOM, 2003, pp. 1987-1997.

[19]. Sheng Zhong, Li Erran Li, Yanbin Grace Liu, and Yang Richard Yang, On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretic and cryptographic techniques, Wirel. Netw. 13 (2007), no. 6, 799-816.

[20]. Christine Bassem and Azer Bestavros, CSR: Constrained Selfish Routing in Ad-hoc Networks. Technical report Boston University 2009, pp.-10-17.