Citation
Cooperation and misbehavior in wireless ad hoc networks

Material Information

Title:
Cooperation and misbehavior in wireless ad hoc networks
Creator:
Aljdawi, Mahmoud
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
xi, 60 leaves : ; 28 cm.

Subjects

Subjects / Keywords:
Ad hoc networks (Computer networks) ( lcsh )
Wireless sensor nodes ( lcsh )
Cooperation ( lcsh )
Selfishness ( lcsh )
Ad hoc networks (Computer networks) ( fast )
Cooperation ( fast )
Selfishness ( fast )
Wireless sensor nodes ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Thesis:
Thesis (M.S.)--University of Colorado Denver, 2010. Political science
Bibliography:
Includes bibliographical references (leaves 59-60).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Mahmoud Aljdawi.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
710043718 ( OCLC )
ocn710043718

Downloads

This item has the following downloads:


Full Text
w
COOPERATION AND MISBEHAVIOR IN WIRELESS AD HOC NETWORKS
by
Mahmoud Aljdawi
B.Sc., Sebha University, 2001
A thesis submitted to the
University of Colorado Denver
In partial fulfillment
of requirements for the degree of
Master of Science
Computer Science
2010


This thesis for the Master of Science
degree by
Mahmoud Aljdawi
has been approved
by
Bogdan Chlebus
Ilkyeun Ra
Min-Hyung Choi
Pecemher 2do
Date


Aljdawi, Mahmoud (M.S., Computer Science)
Cooperation and Misbehavior in Wireless Ad Hoc Networks
Thesis directed by Associate Professor Bogdan Chlebus
ABSTRACT
We consider self-organized wireless ad hoc networks that do not rely on a
preexisting infrastructure such as routers in wired networks or access points in
managed wireless networks. Each node participates in routing by forwarding data for
other nodes, and so the determination of which nodes forward data is made
dynamically based on the network connectivity. Each node is its own authority so
cooperation between the nodes cannot be taken for granted. Nodes may strive to
maximize their own benefits by enjoying network services and at the same time
minimizing their contribution. Such selfish behavior can negatively impact the
networks performance unless a mechanism that makes the nodes to cooperate is
provided.
In this thesis, we present some protocols and mechanisms that can enforce
nodes to cooperate and forward the others packets. We first introduce the watchdog


and path-rater mechanisms which identify misbehaving nodes and then help the
routing protocol to avoid these nodes. Second, we present a protocol which is based
on selective altruism and utilitarianism and makes misbehavior unattractive. After
that, we discuss a generic mechanism based on reputation which enforces cooperation
among the nodes to prevent selfish behavior. We present also a cheat-proof, credit-
based system provides incentive for nodes to cooperate and report actions honestly. A
cooperation-optimal routing-and-forwarding protocol which consists of two sub-
protocols for routing and forwarding is presented. The two sub-protocols work
together to provide incentives for nodes to forward packets.
This thesis surveys recent research on selected aspects of wireless ad hoc
networks.
This abstract accurately represents the content of the candidates thesis. 1
recommend its publication.
Signed
Bogdan Chlebus


CONTENTS
Figures......................................................................X
Tables.......................................................................XI
Chapter
1. Introduction...............................................................1
l.lMobile Ad Hoc Networks.....................................................2
1.2 Wireless Mesh Networks....................................................3
1.3 Wireless Sensor Networks..................................................3
1.1 Malice and Selfishness....................................................3
1.2 Encouraging Nodes Cooperation.............................................4
2. Dynamic Source Routing with Watchdog and Path Rater........................5
2.1 Introduction..............................................................5
2.2 Route Discovery..........................................................6
2.3 Route Maintenance........................................................6
2.4 Watchdog.................................................................7
2.4.1 Ambiguous Collisions....................................................7
2.4.2 Receiver Collisions.....................................................8
2.4.3 False Misbehavior.......................................................9
2.5 Path rater...............................................................9
3. Confidant Protocol........................................................11
V


3.1 Introduction
11
3.2 Components of The Protocol............................................11
3.2.1 The Monitor.........................................................12
3.2.2 The Trust Manager...................................................13
3.2.3 The Reputation System...............................................13
3.2.4 The Path Manager....................................................14
3.3 Good put..............................................................14
3.4 Overhead..............................................................15
3.5 Utility...............................................................15
4. Core Mechanism........................................................16
4.1 Introduction..........................................................16
4.2. Reputation...........................................................16
4.2.1 Subjective Reputation...............................................16
4.2.2 Indirect Reputation.................................................17
4.2.3 Functional Reputation...............................................18
4.2.4 Combination of Reputation Information for Multiple Functions........18
4.3 Network Entities......................................................19
4.4 Reputation Table.....................................................19
4.5 The Watchdog Mechanism...............................................19
4.6 Scenarios in Executions..............................................20
VI


4.6.1 Execution when no Misbehavior is detected
20
4.6.2 Execution when Misbehavior is detected.................................21
4.6.3 Request Made by misbehaving node.......................................21
4.7 Updates and Distribution................................................21
4.8 Enforcing Cooperation...................................................22
4.9 Application of Core to Route Discovery..................................23
4.10 Application of Core to Packet Forwarding...............................24
5. Sprite System.............................................................25
5.1 Introduction.............................................................25
5.2 The Payment Scheme......................................................26
5.3 Credit for Forwarding Messages..........................................27
5.4 Cheating on Submitting Receipts.........................................27
5.5 Motivating Nodes to Forward Messages....................................27
5.6 Preventing False Receipt................................................29
5.7 Message Forwarding......................................................30
5.7.1 Sending a Message......................................................31
5.7.2 Receiving a Message....................................................31
5.7.3 Computing Payments.................................................... 33
6. Corsac Protocol...........................................................34
6.1 Introduction.............................................................34
VII


6.2 The Routing Protocol
35
6.2.1 Source Nodes Test Signals.............................................35
6.2.2 Intermediate nodes test Signals.......................................36
6.2.3 Route Information Forwarding...........................................36
6.2.4 Protocol for the Destination Protocol..................................37
6.3 Packet Forwarding.......................................................38
6.3.1 Routing Decision Transmission Phase....................................38
6.3.2 Data Transmission Phase................................................38
7. Commit Protocol...........................................................40
7.1 Introduction.............................................................40
7.2 Network Model...........................................................42
7.3 Modeling Routing as a Game..............................................43
7.4 The Goals of Commit Protocol............................................44
7.4.1 Individual Rationality.................................................44
7.4.2 Truthfulness...........................................................44
7.4.3 Energy Efficiency......................................................44
7.4.4 Limited Message Overhead...............................................45
7.5 The Protocol Functions...................................................45
7.5.1 Winner Determination...................................................45
7.5.2 Payment Computation....................................................45
VIII


7.5.3 Billing
.45
7.6 The Pricing Scheme.....................................................46
7.7 The Protocol Specification.............................................48
7.7.1 Route Discovery.......................................................48
7.7.2 Data Transmission.....................................................49
7.8 Example................................................................51
8. Conclusion..............................................................53
References..................................................................59
IX


LIST OF FIGURES
Figure
2.1 Ambiguous Collisions........................................................8
2.2 Receiver Collisions.........................................................8
3.1 The Architecture of a Node in the Confidant Protocol.......................12
5.1 The Architecture of Sprite System..........................................26
5.2 Illustration Payment (version 1)...........................................28
5.3 Illustration Payment (version 2)...........................................29
5.4 The Full Version Payment Scheme...........................................30
5.5 The Pseudocode of Sending a Message in Sprite System......................31
5.6 The Pseudocode of Receiving a Message in Sprite System.....................32
7.1 Example of Cheating Node Behavior..........................................47
7.2 Example of Network Topology................................................51
X


LIST OF TABLES
Table
8.1 The Features of the Protocols
55
XI


1. Introduction
The wireless ad hoc network can be defined as a decentralized wireless
network. This type is called ad hoc because it does not rely on preexisting
infrastructure, such as routers in wired networks or access point in managed wireless
networks. In this type of networks the participation of each node in routing is done by
forwarding data for other nodes.
The first type of wireless ad hoc networks was the packet radio networks
which were developed in the 1970s. This type of wireless ad hoc networks was
sponsored by the Defense Advanced Research Projects Agency.
Since the ad hoc wireless networks are decentralized, they can be suitable for
applications that do not rely on central points. The decentralized nature of wireless ad
hoc networks makes them more scalable that wireless managed networks. Moreover,
the minimal configuration and the quick deployment of the ad hoc wireless networks
make them suitable for emergency situations such as natural disasters or military
conflicts. The dynamic and adaptive routing protocol that these networks have would
enable ad hoc networks to be formed quickly.
1


Based on their application, the wireless ad hoc networks can be classified into
three types: Mobile Ad Hoc Networks, Wireless Mesh Networks, and Wireless
Sensor Networks
1.1 Mobile Ad Hoc Networks
The mobile ad hoc network can be defined as a self-configuring network of
mobile nodes connected by wireless links. The node in this type of networks is free to
move independently in any direction and changes its links to other nodes frequently.
The main challenge in building a mobile ad hoc network is how to provide each node
with the information that makes it able to route traffic. The mobile ad hoc networks
have become an active research topic sine the 1990s as a result of the growth of
laptops and Wi-Fi wireless networks.
The mobile ad hoc networks can be divided into three main types: Vehicular Ad Hoc
Networks which are used by vehicles to communicate with other vehicles or with
roadside equipment, Intelligent Vehicular Ad Hoc Networks which help vehicles to
behave intelligently during specific situations such as accidents, and Internet Based
Mobile Ad Hoc Networks: In this type of networks the mobile nodes are connected to
some fixed Internet-gateway nodes.
2


1.2 Wireless Mesh Networks
The wireless mesh network can be defined as a communication network
consists of radio nodes organized in a mesh topology meaning each node in the
network may act as an independent router.
1.3 Wireless Sensor Networks
The wireless sensor network can be defined as a network consists of
autonomous sensors that are spatially distributed to monitor physical or
environmental conditions such as temperature, sound, vibration, pressure, motion or
pollutants.
The wireless sensor networks were developed at the beginning for military
applications such as battlefield surveillance. After that, they were applied in some
industrial and civilian areas. These applications include industrial process monitoring
and control, machine health monitoring, environment and habitat monitoring,
healthcare applications, home automation, and traffic control.
1.4 Malice and Selfishness
Two types of uncooperative nodes can be identified: faulty/malicious nodes
and selfish nodes. The term faulty/malicious nodes means the broad class of nodes
that are either faulty and therefore cannot follow a protocol, or are intentionally
malicious and try to attack the system. Selfish nodes are economically rational nodes
3


whose objective is to maximize their own welfare, which is defined as the benefit of
their actions minus the cost of their actions. In other words, the misbehavior of a node
is considered as a selfish behavior if it aims at obtaining an advantage that can be
quantitatively expressed in the units of wireless networking or in a related incentive
system. Any other misbehavior of a node is considered to be malicious.
1.5 Encouraging Cooperation among Nodes
Because forwarding a message incurs a cost (of energy and other resources) to
a node, a selfish node needs incentive in order to forward others messages. One
possibility to provide incentive is to use a reputation system such as the one proposed
by Marti et al [8]. In this system, a node monitors the transmission of a neighbor to
make sure that the neighbor forwards others traffic. If the neighbor does not forward
others traffic, it is considered as uncooperative, and this uncooperative reputation is
propagated throughout the network. Another possibility to provide incentive is to use
credit (or virtual currency) or micro payment. Buttyan and Hubaux [3] proposed a
solution of this type in and then presented an improved result based on credit counters
in [4]. For both proposals, a node receives one unit of credit for forwarding a message
of another node, and such credits are deducted from the sender (or the destination).
This thesis surveys recent research on selected aspects of wireless ad hoc
networks.
4


2. Dynamic Source Routing with Watchdog and Path Rater
This protocol was presented by S. Marti, T.J. Giuli, K. Lai, and M. Baker in
their paper Mitigating Routing Misbehavior in Mobile Ad Hoc Networks [8],
2.1 Introduction
The protocol improves the throughput in an ad hoc network when some nodes
agree to forward packets, but they fail to do that. In this protocol, the nodes are
categorized based on their dynamically measured. The neighbor is a node that within
wireless transmission range of another node. The neighborhood consists of all the
nodes that are within wireless transmission range of a node. We assume that the
communications between the nodes are bidirectional which means if a node B is
capable of receiving a message from a node A at time t, then node A could instead
have received a message from node B at time t. We also assume that our wireless
network supports promiscuous made operation which means if a node A is within the
range of a node B, it can overhear communications to and from B even if those
communications do not directly involve A. In this protocol, the route paths are
discovered when a source sends a packet to a destination for which the source has no
path. Because of that, this protocol is referred to as on-demand one. The protocol
consists of two main functions: route discovery and route maintenance.
5


2.2 Route Discovery
In this function, when a source node S wants to communicate with a
destination node D, then S brings a route discovery by broadcasting a route request
packet to all its neighbors. This packet contains the address of the destination node D.
Each one of the neighbors that received the route request packet adds its address to it
and broadcast it again. This operation continues until the packet reaches the node D.
The destination node D sends a route reply packet to the source node S to inform it of
the discovered route. The D node can either use the reverse path to send its reply or it
can initiate a new route discovery to 5. There can be many routes from S to D which
means S may receive multiple route replies from D.
2.3 Route Maintenance
This function takes care of link breaks. The link breaks happen when two
nodes in a path are no longer in transmission range. When an intermediate node
detects a link break during forwarding a packet to the next node in the route path, it
sends back a message to the source notifying it of the link break. In this case, the
source tries another path if it has one or it starts the route discovery again if there is
no extra path to the destination.
Watchdog and path-rater are two techniques used on top of the dynamic
source routing protocol in order to detect and discourage any misbehavior.
6


2.4 Watchdog
This technique identifies the misbehaving nodes. Assuming there is a path
from node S to D through intermediate nodes A, B, and C. Each node on this path can
listen to the transmission made by its neighbors. In other words, when A transmits a
packet for B to forward to C, A can tell if B transmits the packet. The watchdog
method maintains a buffer of recently sent packets. Each overhead packet is
compared with the packet in the buffer. If there is a match, meaning the packet has
been forwarded on, the packet in the buffer is removed and forgotten by the
watchdog. However, if a packet has been in the buffer for longer than certain timeout,
then watchdog classifies the node which are responsible for forwarding the packet as
a misbehaving node and sends an alert message to the source node notifying it of this
misbehaving node. The main advantage of dynamic source routing protocol with
watchdog and path rater techniques is that the misbehavior can be detected early
during the forwarding level. However, watchdog technique might not detect the
misbehavior in some cases. The following are some cases that make the watchdog
technique unable to detect the misbehaving nodes.
2.4.1 Ambiguous Collisions
This problem happens when a node cannot hear the transmission of its
neighbor on the same path. As it is depicted in Figure 2.1:
7


O-2-*# L-*0
Figure 2.1: Node A does not hear B forward packet 1 to C, because
Bs transmission collides at A with packet 2 from the source S. [8]
A collision between two packets may happen at node A while it is listening to
the transmission of node B. In this case, node A cannot decide whether the collision
was a result of forwarding the packet by node B or if another node in the
neighborhood caused this collision. In order to deal with this problem, node A has to
watch node B for a certain amount of time. During this time, if node A could not hear
that node B is cooperating by forwarding the packets, then node B is considered as a
misbehaving node and A sends a message to the source node notifying it of the
misbehavior of node B.
2.4.2 Receiver Collisions
The receiver collision happens while node A is listening to node B to know if
it sends the packet to node C or not. During this operation, node A hears node B
forwarding the packets to node C. However, node A does not know if node C received
the packets or not. In Figure 2.2, the packet is not receive because of the collision that
happens at node C between packet 1 from node B and packet 2 from node D.
.......1... 1 XX 2
Figure 2.2: Node A believes that B has forwarded packet 1 on to C,
though C never received the packet due to a collision with packet 2. [8]
8


2.4.3 False Misbehavior
This problem is caused by false report from some node telling that some other
node is misbehaving while in fact it is not. Node A for example may send a report to
the source node saying that node B is misbehaving node while in fact B is a
cooperating node. Based on this report, the source nodes 5 considers B as
misbehaving while A is the real misbehaving node.
2.5 Path Rater
This technique avoids routing packets through misbehaving nodes. The path rater
technique is applied by each node in the network. The node uses the knowledge of
misbehaving nodes which was collected by the watchdog to choose the most reliable
path. Every node in the network manages a rating for its neighbors. To this end, a
node calculates the path metric by averaging the ratings of all the nodes on the path.
This metric is used to compare the reliability of different paths and choose the
shortest length path. The path with the highest metric is chosen if more than one path
to the destination are discovered. The ratings are assigned to the nodes as follows:
A node is given a neutral rating of 0.5 when it is discovered by the path
rater.
Each node gives itself a rating of 1.0.
The rating of each node on the chosen path is incremented by 0.01.
9


Each neutral node cannot be given more than 0.5 as a rating value.
The rating value of a node that is connected to a link break is decremented by
0.05.
A neutral node cannot be given a negative value.
The rating values of the nodes that are not on a chosen path are not modified.
10


3. Confidant Protocol
The results of this chapter were taken from the paper Performance Analysis
of the Confidant Protocol (Cooperation of Nodes-Faimess In Dynamic Ad-Hoc
Networks). By S. Buchegger and J. Y. Le Boudec. [2]
3.1 Introduction:
The Confidant protocol uses selective altruism and utilitarianism to make
misbehavior unattractive by detecting and isolating misbehaving nodes. The protocol
is an extension of source routing protocol for mobile ad-hoc networks. Confidant
protocol is based on the following two ideas: First, learning from observed behavior
where neighborhood watch is employed and nodes are warned by observing what
happens to other nodes in the neighborhood. Second, learning from the reported
behavior where the nodes in the neighborhood share information about the
misbehaving nodes. The nodes also use this information later when they want to
forward data packets.
3.2 Components of the Protocol
In Confidant protocol, each node has the following components: the monitor,
the reputation system, the path manager, and the trust manager.
11


Figure 3.1: The Architecture of a Node in the Confidant Protocol [2]
3.2.1 The Monitor (Neighborhood Watch)
In a wireless ad hoc network, nodes must be able to detect any unusual
behavior. In the monitor technique, the node detects any misbehavior by the other
nodes in the neighborhood. This detection is done by listening to the transmission of
these nodes. The node can also keep a copy of the currently forwarding packet and at
the same time listen to the node that should forward this packet. This strategy makes
the nodes able to detect any change happens to the contents of the packet. The
monitor keeps watching the neighborhood and when misbehavior occurs, the monitor
calls the reputation system.
12


3.2.2 The Trust Manager
The main role of the trust manager is to deal with incoming and outgoing alarm
messages. The trust manager of a node sends an alarm message to warn the neighbors
of misbehaving nodes. The node generates outgoing alarms after having experienced,
observed, or received a report of misbehavior. Each node has a list of friends who
receive these alarm messages. These incoming alarm messages are filtered according
to the trust level of the sender. The following are the components of the trust
manager:
Alarm Table: Information about the received alarms is stored in this table.
Trust Table: The trust levels of nodes in the neighborhood are managed in
this table.
Friend List: This list contains the friend nodes that the node sends alarm
messages to.
Trust is important especially when a node making decisions such as providing or
accepting information about a new route, accepting a new node as a part of a route,
and being a part of a discovered path.
3.2.3 The Reputation System
Each node has local rating lists and sometimes black lists. These lists could be
exchanged with friends. Each node checks the black list to see if its neighbor is on
13


this list before sending or accepting any information from it. False accusations can be
avoided by using timeout where lists of nodes that have cooperated for a certain
amount of time are used. The problem of scalability and how to avoid lists growing
too big can also be addressed by using timeout technique. In this protocol, a table
contains the neighbor nodes and their rating is managed by the reputation system. The
rating of a node is changed if this node has showed a misbehavior many times during
a specific period of time. The path manger takes action if the rating falls out of a
tolerable range.
3.2.4 The Path Manager
The path manager does the following: ranks the paths based to the reputation of
the nodes in that path, deletes the paths that contain misbehaving nodes, makes
actions on receiving a request for a route from a misbehaving nodes, and makes
action on receiving request for a route containing a misbehaving node (these actions
could be ignoring the request or alerting the source node).
3.3 Good put
In a network with n nodes, the resulting total good put G is the data forwarded
to the current destination for each node t and it is defined as:
^ X PdcketS[feceiVe(i
(j .....
X PdCk^tSoriginated
14


3.4 Overhead
The total overhead 0 in a network of n nodes is defined as follows:
2 ALARM
0 = -------------------------------
2 RREQ + RREP + ERROR
By using this ratio we can determine how much extra overhead is caused by
the Confidant protocol in compare to the overhead when the protocol is not used.
Where ALARM are the alarm messages, RREQ are the route request
messages, RREP are the route reply messages, ERROR are the error messages.
3.5 Utility
Utility can be defined as the ratio of originated to transmitted packets. We
assume that Cf is the cost of forwarding a packet, br is the benefit when receiving a
message as a destination, bs when having an own packet received by the destination.
Thus the utility u of a node i can be defined as:
Ui = br ft Packet sreceived + bs # Packetssenc successfuUy ~ Cf Pac^etstransmitted
The utility of a network consists of n nodes is defined as the follows:
U = 2=1 ut
15


4. Collaboration Reputation Mechanism (Core)
This mechanism was studied by P. Michiradi and R. Molva in paper [9].
4.1 Introduction
The core implements a mechanism to assess a reputation. This mechanism is
used to enforce cooperation among the nodes of a mobile ad hoc network to prevent
selfish behavior. In this mechanism, each node keeps track of other nodes
collaboration using a technique based on assessing reputation. The reputation of each
node is calculated based on the rating of this node. The rating of a node is increased
when it cooperates and it is decreased when it misbehaves.
4.2. Reputation
There are three types of reputation in the Core mechanism: subjective
reputation, indirect reputation, and functional reputation.
4.2.1 Subjective Reputation
Subjective reputation is the reputation that is calculated directly from the
observations that the subject node makes. From the point of view of subject St, a
subjects reputation at a time is calculated using a weighted mean of the observations
rating factors which lends relevance to past observations. The past observations are
16


given more relevance to have sporadic misbehavior in recent observations affect less
influence on the evaluation of the final reputation value. False detections can be
avoided by watching link breaks and misbehaving nodes. The following formula is
used to calculate the subjective reputation:
In the above formula, Sj is a neighbor of Sj. rf. (s/|/) is the subjective
reputation value calculated at time t by subject st on subject Sj with respect to the
function /, p(t, tk) is a time dependent function that gives higher relevance to past
values of ak, and ak is the rating factor given to the k-th observation. The used
scale goes from 1 to +1 where 1 means that the observed result and the expected
result do not match, and +1 means that the observed result and the expected result
match. If either the number or the quality of observations that are collected during a
period of time t are not sufficient, then the final value of the subjective reputation is
set to 0, which denotes a neutral impression. Since ak £ [1,1] and p(t, tk) is a
normalized value, also r* (s,\f) e [-1,1].
4.2.2 Indirect Reputation
The indirect reputation of subject Sj collected by st at time t for function / is
denoted by ir/fayl/). Where f denotes the routing or the forwarding function. The
17


indirect reputation takes only positive values. As a result of that, denial of service
attack which usually based on broadcasting negative ratings is prevented.
4.2.3 Functional Reputation
The functional reputation can be defined as a subjective and indirect reputation
calculated on different functions / each time. A global subjects reputation is added
to this type of reputation. The following formula r/.(s;|/(packet forwarding)) for
example represents the subject St evaluating the subject reputation of subject Sj on
the packet forwarding function while the formula r/.(sj\f (routing)) represents 5*
evaluating Sj on the routing function. The two resulting values after that are
combined together to calculate the global reputation value of the subject Sj.
4.2.4 Combination of Reputation Information for Multiple Functions
The following formula is used to combine reputation information:
rSiisj) = ^wk.{rst.(sj\fk)+ irf. (s; \fk)}
k
Where wk is the weight associated to the functional reputation value and rf.(sj) is the
global reputation value that is calculated in every node. The value of wk must be
carefully chosen because it has direct effect on the global reputation value. The
operation of packet forwarding has more impact than the operation of routing on the
overall performance. However, both operations must be executed.
18


4.3 Network Entities
Each mobile node in the network s* has a set of reputation tables and
watchdog mechanism which are used to provide collaborative reputation mechanism.
The reputation table and watchdog mechanism make each node able to watch and
classify the other nodes in the network. The resulting the classification is used to
encourage the nodes and obtain a strong cooperation among the nodes in the network.
The nodes can be classified into three types: a requester which is a node asking for an
execution of a function /, A provider which is a node that executes the function f,
and a trusted node which is a node that has positive reputation value.
4.4 Reputation Table
The reputation table can be considered as a data structure within each node in
the network. In this table, each row represents the reputation values of the nodes in
the neighborhood. Each row in this table is divided into four parts: a unique identifier
of the node, the subjective reputation values that have been made on the node, the
indirect reputation values that are reported by the other nodes in the neighborhood,
and the functional reputation values that the node has calculated.
4.5 The Watchdog Mechanism
The watchdog mechanism is a technique used by each node to detect
misbehaving nodes. When a monitoring node wants to follow the execution of a
19


function by another node, it runs the watchdog especially to this function and waits
for the result. The watchdog does the following: First, it stores the expected result in a
temporary buffer maintained in each node. Second, it compares the observed result
with the expected result. If they match meaning the function is properly executed,
then the expected result is removed from the buffer and the watchdog waits for the
next function to be executed. If the function is not correctly executed or if the
expected result remains in the buffer for more than a certain fixed time, a negative
reputation value is given to the observed node in the reputation table.
4.6 Scenarios in Executions
There are two types of entities considered in this protocol: a requester and one
or more providers. The requester and the providers must be within the same wireless
transmission range. When the protocol is executed, one of the following scenarios
occurs.
4.6.1 Execution when no Misbehavior is Detected
In this scenario, the requester executes the function f and then it activates the
watchdog to watch the execution of /. After that, the requester waits for a specific
time out. When the result of the watchdog shows that the requested function was
correctly executed, then the requestor releases the watchdog. The result of the
function execution contains the cooperating nodes that followed the protocol. This
20


result is used by the requestor to update its reputation table. After that, the requester
becomes idle.
4.6.2 Execution when Misbehavior is Detected
In this scenario, the requester executes the function / and then it activates the
watchdog related to the provider for the required /. After that, the requester waits for
a specific time out. The result of the watchdog will be negative because the provider
does not cooperate. The reputation of the provider in the reputation table is given
negative value. After that, the requester becomes idle.
4.6.3 Request Made by Misbehaving Node
When a node receives a request for the execution of a function /, the node
first checks the reputation value of the requestor. If the reputation value of the
requester is negative, then the node does not execute the requested function. The node
also can notify its neighbors of this misbehaving requester.
4.7 Updates and Distribution
The following is description of the mechanism used to update and distribute
reputation information. There are two times when the reputation tables can be
updated: in the request stage and in the replay stage. Only the value of subject
reputation may be updated in the former case. If the provider did not cooperate in this
stage, the observation is given a negative value and the reputation value of the
21


provider is decreased. If there is no misbehavior, then reputation values will not be
updated. In the latter case, the values of the indirect reputation are the only values that
are updated. In this case, the reply message brings reports about the cooperating
nodes. These reports cause making the indirect reputation of the cooperating nodes
positive. Because of a possible attack, only positive rating factors can be distributed
among the nodes while the negative rating factors are evaluated locally. Giving
negative rates makes it easy for misbehaving nodes to distribute false information and
create denial for service attack [7]. If a node is idle for most of the time except when
it has to communicate, its reputation gets decreased, even if it cooperates during the
other times.
4.8 Enforcing Cooperation
Next we explain how reputation is used to enforce cooperation among nodes.
The reputation reflects the cooperative behavior of nodes where the negative
reputation causes classifying the node as a misbehaving node and the positive
reputation causes tagging the node as a cooperating node. Moreover, the execution of
a function that is requested by any requestor depends on the reputation value of the
provider in the reputation table. The execution of the function is denied if this
reputation value is negative. It is hard for a node to build a good reputation because
getting a positive rating requires receiving reply message which contains all the nodes
22


that cooperated to correctly execute the requested function. However, a node is given
negative reputation value each time the watchdog gives a negative result.
4.9 Application of Core to Route Discovery
We want any node in an ad hoc network to discover a route to any other node in
the ad hoc network. This discovery can be done directly when the two nodes are
within the same wireless transmission range or it can be done through one or more
intermediate nodes. The node initiates a route discovery by broadcasting a route
request message which can be received only by the nodes within the transmission
range. The intermediate nodes that receive a route request message append their
addresses to this message broadcast it again. When the route discovery is successful,
the source node receives a route reply message with a sequence of nodes that it can
reach the destination through. We can define the Core protocol as a layer on top of
the dynamic source routing protocol. The misbehaving nodes that do not participate
during the route discovery are detected by the watchdog mechanism. This detection
happens during the request phase of route discovery. During the reply phase the
source and the intermediate nodes are informed of the nodes that participated in route
discovery. Base on this information the reputation values of the nodes are updated.
Each node uses the reputation table to classify other nodes it receives information
about. While the route requests that originated by cooperating nodes are properly
serviced, the route requests of the misbehaving nodes are denied. In order to change
23


its reputation value from negative to positive, a node has to be cooperative. The nodes
that want to be serviced when they need to communicate have to participate in route
discovery.
4.10 Application of Core to Packet Forwarding
When the node finds a path from the source to the destination to the
destination, it starts sending its packets through this path. The intermediate nodes on
the path perform the packet forwarding by transferring the packets. The misbehaving
nodes that refuse to forward the packets are detected by the watchdog. While the
misbehavior of the nodes is detected in the request phase of packet forwarding, the
source and the intermediate nodes are informed of the cooperating nodes that
participate in packet forwarding during the reply phase. The reputation values in the
reputation table are updated based on the cooperation of the nodes. This information
is used later by the node to classify other nodes. Any cooperating node can execute
the packet forwarding while the misbehaving nodes cannot do so. Cooperation is the
only way for a node to change its reputation from negative to positive. Nodes have to
participate in packet forwarding if they want their data packets to be forwarded later.
24


5. Cheat-Proof, Credit-Based System
This simple, cheat-proof, credit-based system (Sprite) was proposed by
S. Zhong, Y. R. Yang, and J. Chen [10].
5.1 Introduction
As it can be seen in Figure 5.1, The Sprite system consists of the credit
clearance service and a collection of mobile nodes. The nodes in this system send and
receive messages through a wireless network. The sender node knows the full path to
the destination of its packets. Since forwarding the packets costs the intermediate
nodes some of their resources, the sender pays with credit to the network each time it
sends something. When an intermediate node forwards packets for other nodes, it get
some credit and so it can send its packets later. The node has to report to the credit
clearance service the messages that it has forwarded. The main goals of the payment
scheme are to thwart cheating actions and to afford incentive that encourages nodes to
cooperate and forward each others packets. The system does not require the total
charge to the sender to be equal to the credit received by the intermediate nodes. In
order to prevent cheating, credit clearance service charges the sender more than what
it gives to the intermediate nodes.
25


Credit Clearance Service
Wide-Area Wireless Network
Node 1 Node 3
Node 2
Node 4
Node 5
Figure 5.1: The Architecture of Sprite System [10]
5.2 The Payment Scheme
Only the sender is charged in this system. This can be explained as the
follows: charging the destination can cause a Denial-of-Service attack on the
destination where other nodes may send a large amount data. Sharing the cost
between the sender and the destination still has the same problem where the sender
may make agreement with the intermediate nodes and they can secretly return the
payment the sender made back. However, if only the sender is charged, a node is
discouraged sending useless messages. If the destination pays for the received
messages, then the sender can get compensation from the destination. This
compensation can be done in the application layer by the execution of the payment
protocol.
26


5.3 Credit for Forwarding Messages
The amount of credit that a node receives depends on whether or not the
forwarding action was successful. Forwarding is successful if and only if the message
is received by the next node on the path. The credit clearance service decides that the
node has forwarded the message if it received a valid receipt from the successor of
that node.
5.4 Cheating in Submitting Receipts
Because the mobile nodes could be selfish, they may choose not to forward
others messages or they may try some cheating actions if these actions could
improve their resources. A selfish node may adopt one of the following cheatings:
The node receives the message but it does not report the receipt. The message could
also save the receipt but not forwarding the message. Another selfish action happens
when the node falsely claims that it has received the message while it has not
received the message.
5.5 Motivating Nodes to Forward Messages
The credit clearance service gives more credit to the cooperating nodes that
forward packets in order to motivate all the nodes to cooperate while misbehaving
nodes are not given any credit. The credit clearance service works as follows: it
determines the last node on the path that has received a packet. After that, the credit
27


clearance service enforces the sender to pay /? to this node and to pay a to each of the
predecessors of this node where (3 < a. The successor of the last node on the path
does not get any payment. As it can be seen in Figure 5.2, Because only the first three
intermediate nodes submit their receipts, they are the only nodes that receive
payments while nodes 1 and 2 get a payment of a for each. Node 3 gets a payment of
(3. Node 4 and the destination do not receive any credit because they do not submit
any receipt. The total amount that the sender pays is 2a + (3.
-(2a+p)
sender
a
*
node 1
a p 0 0
Figure 5.2: Illustration of Payment (Version 1) [10]
There is a probability of a collusion that can work against the above design if
the last node (or the last K nodes) that received the message collude with the sender.
The last node may do not report its receipt which caused the sender to save amount of
a credit and at the same time the last node will lose an amount of f3. The sender may
give an amount of f3 + to the last node where e > 0. In this case, the last node will
be better-off and the sender get an amount of a ((3 + e ). In conclusion, the
colluding group gets an amount of a (3. The credit clearance service charges the
sender an extra amount of credit if the destination node did not report its receipt. This
strategy helps preventing this cheating action. The extra charge is given to credit
28


clearance service itself rather than to any node. In this case, the colluding group will
not be able to benefit from this cheating action. Figure 5.3 shows the revised amount
that the sender pays, which is (4a + (3) 2(3.
-(4a+P)
sender
node 1
node 2
P,
X
0
node 3
node 4
destination
Figure 5.3: Illustration of Payment (Version 2) [10]
5.6 Preventing False Receipts
The nodes submit receipts instead of full messages in order to save bandwidth and
storage. In the presence of such a scheme for receipts, some nodes can try to cheat the
system in different ways. A node may forward only the receipt and not forwarding the
rest of the message. In addition, an intermediate node may wait until it has a fast
connection to forward the false receipt in order to save its resources. Ways to prevent
such attack depend on how the destination behaves. There are two considered cases.
First, when there is a colluding between the destination and the intermediate nodes
and second, there is no such colluding. In the first case, the destination submits a
receipt of a message even the whole message is not received. To deal with this case,
the intermediate nodes and the destination must pay for the message because the
message is sending for the destination and the destination submitted a receipt for the
message conforming that it has received the message. In the second case, the
29


destination does not collude with the intermediate nodes and the intermediate nodes
forward only the receipt of message instead of the whole message, therefore the
destination does not receive the message. Based on the above scenario, the receipt
will not be sent. This cheating action can be prevented by reducing the amount of
credit given to the intermediate nodes if the destination does not report that it has
received the message. By using this reduction of credit, the cheating nodes cannot get
enough credit even to forward their receipts. In other words, the credit paid to each
node is multiplied by y if the destination does not send a receipt conforming the
receiving of the message when y < 1. Figure 5.4 shows the amount of credit that
each node receives. The charge to the sender is reduced by y(3 instead of /3 for the
nodes that do not send their receipts.
Figure 5.4: The Full Version Payment Scheme [10]
-(4a+p-2yp)
5.7 Message Forwarding
A public/private key pair of node 7ij is presented by ( PK^SKi ). Sequence-
number matrix Seqi is maintained by each node rq where Seqi(J, k) is the sequence
number of message from sender rij to destination nk, observed by node rtj.
30


(signsk( ),verifypk()) represents the digital signature that is attached with each
message.
5.7.1 Sending a Message
Assuming that node n0 wants to send message m that has sequence number
seq0(0, d) to the destination node nd, through the path P. The signature, 5, on
P,seqo(0,d)) is computed by node n0 first where MDQ is a message
digest function. After that, n0 forwards the message (m, P, seq0(0, d),S) to the next
node and increases the sequence numberseqo(0, d). The following is the pseudocode
of sending a message:
Am is the message payload.
An0 is the sender, nd the destination, and P the path.
S <- signSKo(Md(m),P,seq0(Q,d)
Send (m, P,seq0(0, d),S) to the next node.
seq0(0,d) + +
5.5 The Pseudocode of Sending a Message in Sprite System [10]
5.7.2 Receiving a Message
When the node n; receives the message (m, P, seq, 5), It first checks if the
following three conditions are satisfied: the node rij is on the path, the sequence
31


number of the message is greater than seq^Q, d), and the signature of the message is
valid. If the conditions are satisfied, then the node n, saves message
(MD(m), P, seq, 5) as a receipt and forwards the message (m, P, seq, S) to the next
node if is not the final destination of this message. If any of the conditions is not
satisfied, then the message will be dropped. The following is the pseudocode of
receiving a message:
A (m, P, seq, S) is the received message.
A S0 is the sender, nd the destination.
if ((nt not in P) || (seq < seqi(0,d)|| (veri/yP/fo((MD(m),P,seq),5) TRUE))
drop the message
else
seqi(0,d) *- seq
save (MD(m),P,seq,S) as a receipt
if (ri[ is not the destination and decides to forward)
send (m, P, seq, S) to next hop
else
drop the message.
5.5 The Pseudocode of Receiving a Message in Sprite System [10]
32


5.7.3 Computing Payments
The receipt (D, P, seq, S) is considered as valid if the following condition is
satisfied: verifyPKo((D,P,seq),S) = TRUE. PK0 represents the public key of the
sender. P = (n0, n1(..., ne,..., nd) is the path that was used to send the packets. ne
represents the last node on the path P that has submitted a valid receipt. Using these
factors, the credit clearance service calculates the charge C that the node n0 pays, and
the payment p,- that is given to each node Tij as the follows:
C = (d 1 )a + (3 (d e)y(3
{a if i < e = d
(3 if i = e = d
yf3 if i < e < d
yf3 if i = e < d
33


6. Cooperation-Optimal Routing and Forwarding Protocol (Corsac)
The Corsac protocol was introduced by S. Zhong, L. E. Li, Y. G. Liu, and Y.
R. Yang in their paper On Designing Incentive-Compatible Routing and Forwarding
Protocols in Wireless Ad-Hoc Networks. [11]
6.1 Introduction
We refer to this protocol as a cooperation-optimal protocol for wireless ad-hoc
networks with non-cooperative selfish nodes. In this protocol, there are two stages in
which routing and forwarding occur in a node. These stages are the routing stage and
the forwarding stage. In the routing stage, the routing decision is made by the nodes
actions. The routing decision consists of the forwarding actions of all nodes. These
actions specify what each node supposed to do in the forwarding stage. In the
forwarding stage, the nodes utility is decided by the routing decision (what each
node is supposed to do in this stage) and the nodes forwarding actions (what each
node really does in this stage).
We assume that a* = (a[r\ aP), where aP is the node is subaction in the
routing stage, and aP is is subaction in the forwarding stage. We also assume that a
denotes the actions of all nodes, a^ denotes the routing subactions of all nodes, and
denotes the subactions of all nodes during the packet forwarding. The routing
34


decision R is defined as R = R(a^). It also can be defined as R = a^\ where
denotes all nodes supposed forwarding actions. The utility of each node w* is decided
by the routing decision R and the nodes actual actions in the forwarding stage
The utility can be written as the follows: a^). The prospective routing
utility of a node can be defined as the utility that the node achieves under the routing
decision, if each node follows the forwarding action that is made by the routing
decision. We have the routing decision R = a^\ then we can define the prospective
routing utility of node i as the follows: = Ui(R, a^). Since ujR^ depends only
on R, and R is decided by the routing subactions a^r\ then the prospective routing
utility of node i can be written as the follows:
u 6.2 The Routing Protocol
In this protocol, the source node starts the routing discovery when it receives a
new session from the application layer. The routing protocol consists of four sub-
protocols:
6.2.1 Source Nodes Test Signals
A session of M packets is started by the source 5. The packets are divided into
\M/b1 blocks, where b is the number of packets in each block.
35


The source node 5 picks a random number r0.
Assuming that H is a cryptographic hash function, S uses the number of bocks
in the session to compute r = H^M^b^(r0).
A message of the form (TESTSIGNAL, [5, D,r],[S,hi]) is sent by the node i
at power level l where ht indicates the encryption of [5, D, r, l, a5]. The key
kS D is used for the encryption.
6.2.2 Intermediate Nodes Test Signals
When an intermediate node i receives message of the form
(TESTSIGNAL, [5, D,r], [P, h]) from a neighbor node, the following happens:
A message of the form (ROUTEINFO, [5, D,r], [P, i, h']) is sent by the node i
at power level ^ctr- The key ki D is used to compute h' and protected by the
message authentication code.
In the case that iheTESTSIGNA message is the first one that node t receives
for the session (S, D,r), then i sends message of the form
(TESTSIGNAL, [5, D,r], [t, hj]) where h\ includes the encryption
of [S,D,r,l,ai).
6.2.3 Route Information Forwarding
When an intermediate node j receives message of the form
(ROUTEINFO, [5, D, r], [P, i, h]), the following happens:
36


In the case this ROUTEINFO message is new for the node j, then node j uses
the power level Pctr t send to send a message of the form
(ROUTEINFO, [5, D, r], [P, i, h]).
6.2.4 Protocol for the Destination Node
A cost matrix for each session (S, D, r) is maintained by the destination node D.
This matrix contains the power levels and the costs of energy.
When D receives message of the form (TESTSIGNAL, [S, D, r], h) from node
P, it first decrypts h, and then uses the key kP Dto verify the MAC. After that,
D saves the power level and the cost of energy in the cost matrix.
When D receives message of the form (ROUTEINFO, [S, D, r], [P, i, h]), from
node P, it first decrypts h, and then uses the key kP Dto verify the MAC. After
that, D saves the power level and the cost of energy in the cost matrix.
After D collects all the information about the link cost, it makes sure that the
energy cost is not change. After that, the minimum power level for each link is
chosen. Finally, D uses Dijkstras algorithm to compute the lowest cost path from S
to D. The computed lowest cost path is denoted by LCP(S, D) which is also the
chosen path that is used to forward packets. The lowest cost path without node i is
denoted by LCP(S, D; i). The payment for one data packet to node i is defined as
the follows:
37


Pi = cost(LCP(S,D,-i)) cost(LCP(S,D) {i})
6.3 Packet Forwarding
The packet forwarding protocol consists of two sub-protocols:
6.3.1 Routing Decision Transmission Phase
After the node D finishes the routing discovery phase, it sends message of the
form ([S, D, r], LCP(S, D), Ps, ((Pi,Pi) | i is an intermediate node on LCP(S, D)}). A digital
signature is sent with the routing decision message along the reversed path of
LCP(S, D). Pj denotes the power level that node i uses to forward data packets, and pt
denotes the unit payment node i receives. The routing decision is forwarded by each
intermediate node at a power level that can reach the path LCP(S, D).
6.3.2 Data Transmission Phase
After it receives the routing decision, the source node 5 makes sure that the
digital signature is valid. After that, S enters the data transmission phase. In the data
transmission, the source S sends data packets at the power level Ps while the
intermediate nodes send data packets at the power level Pj. These power levels were
computed in the routing decision. S sends out data packets in blocks where each
block contains b packets. The source S sends out r\M/b|_m = H^M^b^~m(r0) with the
last data packet in the m-th block. The source node 5 waits for a confirmation before
38


sending the next block. The intermediate nodes forward the block of packets that sent
by the source node 5 along the LCP(S, D) to the destination node D. The intermediate
nodes finish sending the block and then they wait for a confirmation before they start
forwarding the next block. After the destination D receives all the packets in a block,
it decrypts and then it sends r\M/b^m in dear-text back along LCP(S, D), as
a confirmation of this block. After the intermediate nodes receive the confirmation of
the m-th block, they verify that the condition r = Hm{r\M/b|_m) is satisfied. The
intermediate nodes forward the confirmation using the path LCP(S, D). After the
source node S receives the confirmation of one block, it starts sending the next block.
The confirmation r\M/b|_m is sent by each intermediate node j the system in order to
get a payment of p7. b m.
39


7. Sender-Centric Truthful and Energy-Efficient Routing Protocol (Commit)
The information of this chapter was taken from the paper which was presented
to the International Parallel and Distributed Processing Symposium (IPDPS) by S.
Eidenbenz, G. Resta, and P. Santi. [6]
7.1 Introduction
This protocol considers the problem of establishing a route between source
and destination, and sending packets through this route in ad hoc network with selfish
nodes. There are side payments made to the forwarding nodes. These payments are
used to motivate the nodes to follow the protocol specifications. In this protocol,
nodes are supposed to participate in the protocol execution and follow the protocol
specification. The messages must be routed along the most energy efficient path. This
protocol is the first individually rational, truthful, and energy-efficient routing in ad
hoc networks. In this protocol, a wireless network is considered. This network is used
to access a specific service such as internet access. The nodes in this network do not
have to be directly connected to the base station. Instead they can use other nodes as
intermediate nodes in order to connect the base station. The customer who wants to
be connected to the service will be called sender. The intermediate wireless nodes
will be called relays, and the service provider will be called the destination. The
intermediate nodes should be motivated to be cooperating and forward the packets of
40


other nodes to make the network works successfully. The Ad Hoc-VCG protocol
which is mentioned in [1] is used to discover the route that will be used to send or
receive the packets. The process of routing discovery is started by the sender node
broadcasting the destination that it wants to send packets to. If there is any path to this
destination, the sender receives a message indicating the path P and the cost of
sending the packets through this path. The price that the sender pays to send its
packets is distributed among the intermediate nodes. Each intermediate node receives
that amount that makes it able to forward the packet. Both the sender and the
destination must act truthfully in this protocol. The sender cannot withdraw the
connection request after starting the route discovery phase. The reason of this
restriction is that if the intermediate nodes in the path P would not be sure that they
will be paid, they will lose the incentive that encourages them to cooperate later in the
route discovery phase.
The basic idea of this protocol is used by the website PRICELINE. COM [12].
In this website, the customers provide the maximum amount of money they can pay
for a certain service such as a hotel reservation or a flight ticket. The request is
automatically accepted, and the transaction takes place if there is a service available
at the provided amount of money. The same thing happens in the scenario described
above. The customers who want to access the service issues a connection request. In
this request, the customers state the maximum amount of money they will pay for this
41


service. A full commitment of the customer is represented by the connection request -
that is the reason why this protocol is called Commit protocol. The customer pays the
corresponding amount if there is a connection can be made at cost less than what the
customer proposed. The customers in this strategy can always control the amount
they pay for exchanging the packets. The truthful in this protocol means that the
nodes should always follow the specifications of the protocol. Individual rationality
means that it is rational for the selfish node to cooperate during the execution of the
protocol.
7.2 Network Model
In this model, an ad hoc network consists of n nodes is considered. The
communication graph G represents the links between the nodes in the network. The
links are considered to be symmetric which means an edge between nodes v and w
appears in G if and only if v is within ws transmitting rang, and w is within vs
transmitting rang. The graph G is 2-connected which means from any node to the
destination there are at least two node-disjoint paths. The nodes execute a topology
control protocol to establish the communication graph. By the end of this execution,
every node v will determine its transmitting rang rv. r$ is the power required to
achieve a transmitting range rv, where a is constant between 1 and 6. In order to
update vr, the topology control protocol is executed periodically. However, the same
42


transmitting range rv is applied in the period of time between consecutive topology
checks.
7.3 Modeling Routing as a Game
The process of establishing a route between a source and a destination node is
modeled as a game. In this game, a node can play only one role: source, relay, or
destination. 5 denotes the sender, v or V[ denotes an arbitrary relay node, and D
denotes the destination. The destination node is neutral referee rather than an actually
part of the game. It computes the minimum energy (5, D) path and the payments for
the source and the intermediate nodes. The goal of this model is routing a path
between the sender and the destination and then using this path to send packets in
both directions. During the data session, the sender is charged for sending and
receiving packets. The utility of player 5 can be written as follows: us = m cs(D)
where m is the maximum per-packet price that 5 can pay and cs(D) is the actual per-
packet price that S pays. If a node v took place in the data session, then its utility can
be written as the follows:
uv = pay(v) l(v) where pay(v) is the payment that v receives for forwarding
each of the packets of the source node 5.
43


7.4 The Goals of Commit Protocol
Commit is a protocol for incentive compatible and energy-efficient routing in
ad hoc networks, and it has the following design goals:
7.4.1 Individual Rationality
This property is satisfied if the node that is included in the protocol does not
get a negative value for its utility. The goal of this property is to encourage the nodes
to participate in the protocol.
7.4.2 Truthfulness
As described above, truthfulness is the strategy in which the nodes follow the
protocol specification. In this strategy, the nodes declare their true type and send/relay
the messages as prescribed.
7.4.3 Energy Efficiency
If there is a feasible communication between S and D, it must take place along
the minimum energy cost path. The cost of energy for the path P can be defined as
Tivep,v$[s,D}Kv)- As we mentioned before, energy efficiency is a key property in the
ad hoc networks because the nodes in these networks are battery operated.
44


7.4.4 Limited Message Overhead
One of the important goals of this protocol is minimizing the number of
exchanged messages during the forwarding stage.
7.5 The Protocol Functions
The designed protocol must be able to perform the following tasks:
7.5.1 Winner Determination
If there is a winning path, it must be determined along with the communication
that must be established.
7.5.2 Payment Computation
If there is a winning path, then the price that S must pay for transmitting/receiving
the packets and the payments for the intermediate nodes on this path must be
determined.
7.5.3 Billing
After the communication is done, the source node S must be charged and the
intermediate nodes must be paid based on the computed prices.
The destination node D performs winner determination and payment
computation based on the information that it collected from the nodes. Billing is done
45


by starting the data session. The payment method used in the Commit protocol can
be defined as a distributed reverse second-price single item auction with reverse price
where the sender S can be considered as the auctioneer that wishes to buy an item (the
path from S to the D) at a maximum price of m (the reverse price). The relay nodes
can be considered as sellers. The reverse auction is second-price because the price
that the sender pays to the winning group (the intermediate nodes) depends on the
second best given offer.
7.6 The Pricing Scheme
The following factors are defined and used to compute the winning path and
the payments of the nodes: cP denotes the energy cost of an arbitrary path from S to D
(S, D)-path P. Where cP = Xvep,v{s,D} l(Y)- The winning path can be defined as the
path of minimum energy cost and it is represented by MP. For any node in the
winning path, c(P~v) denotes the cost of the minimum energy (5, D)-path P~v that
does not include this node v. We can define the payment for node v in the winning
path MP as follows: pay{y) = c(P~v) c(MP) + l(v). The trivial definition of the
price that S pays for sending the packets along MP is cs(D) = Y.vMP,vt{s,D)Pay(v)-
However, this definition leaves space for a misbehavior to the nodes in MP. Because
of the presence of the reverse price m, these nodes could declare a false type in order
to make the cs(D) price less than m.
46


In the example in Figure 7.1, the sender wants to pay at most 56 for each
packet to be sent to the destination.
Figure 7.1: Example of Cheating Node Behavior if CS(D) is defined as
Cs(0) = Y,veMP,vi{S,D}Pay(v) [6]
In the case that all the nodes declare their true types, the communication
cannot be made because of the following: Since MP = {v1; v2, v3), c(MP) = 26,
c(P~Vl) = c(P~v2) = c(P-**) = 40, payCvJ = 40 26 + 5 = 19, pay(y2) =
40 26 + 20 = 34, pay(v3) = 40 26 + 1 = 15. The total payment is 68 which
is above what the sender will pay (65), so the connection would not take place. Let
us assume that the node v2 gives a false power level which is 30. The payments will
be as the follows: payCvJ = 40 36 + 5 = 9, pay(y2) = 40 36 + 30 = 34,
pay(v3) = 40 36 + 1 = 5. The total payment will be 48 which is below the
payment that the sender proposes, so the communication takes place. In this case,
47


defining cs(D) = 'ZveMP,vt{s,D)Pay(v) leads to not-truthful mechanism. To avoid
this problem, we set cs(D) = c(P~MP) where c(P~MP) is the cost of the minimum
energy path that does not contain any of the nodes in MP. This path is called the
global replacement path. With this new definition of cs{D), any false declaration
from the nodes in MP will not affect cs(D) and the truthfulness of the mechanism is
not impaired. The winning path MP is defined as feasible if c5(D) < m. The
connection cannot be made if this condition is not satisfied. In general, the amount
that is charged to the sender and the total amount that is given to the intermediate
nodes are not equal. In other words, c(P~MP) =£ Y,veMP,v${s,D}Pay(v)- In this case, it
is said that the budget is imbalanced. The destination node D is responsible for
making this balance. D gets the additional amount if c(P~MP) < 'ZveMP,vt{s,D]Pay(.v)y
or it pays the difference if c{P~MP)> EpeMP,v{s,D}PayOO-
7.8 The Protocol Specification
The Commit protocol can be divided into two stages:
7.8.1 Route Discovery
In this stage, a limited flooding process computes the communication graph
while the destination node D computes the winning path MP and the payments. After
that, D sends the resulting path and the payments to the source node S.
48


7.8.2 Data Transmission
The sender 5 sends or receives the data packets and the payments along the
winning path from the destination node D. This operation continues until the sender S
ends the connection or until the topology is updated. First, S sends a route discovery
message of the form RD(S,D,m) using power l(v). In this message, S declares that it
wants to start a data transmission session to the destination node D. S indicates also
the maximum amount which is m that it can pay for each data packet to be sent to the
destination. Each intermediate node vk receives a message of the form
RD(S,D,m,vlll(v1)l... ,vK.lll(vK.1)). vx,... represents the path between the
sender S and the node %_x.m El^Ti1 l(vt) represents the difference between the
amount that S provides and the total cost of the path when vK receives the message.
When the node vk receives messages, it builds up a local view of communication
graph. Every time it receives information about the existence of an edge that it does
not know about before, it adds this information to its local view. After that, vK
appends the fields vK and l(vK) to the message that contains the new information and
then it forwards this message with power l(vK) to the next node on the path. The
node vK cryptographically signs the two fields vK and l(vK) to prevent other nodes
from altering them. Node vK also signs the field vKto ensure that there is an edge
between vK-1 and vK. The destination node D receives RD messages from all nodes
on the path. After receiving all information, D does the following:
49


Computes the minimum energy path MP = [S, vlt ...,vK, D) from S to D.
Computes the replacement path P~Vi for each intermediate node in the
minimum energy path.
Computes the global replacement path P-Mp.
Computes the payment/premiums for S and the nodes in MP and checks if the
condition cs(D) = c(P-MP) < m is satisfied.
Sends back the winning path, the payments, and the global replacement path
to 5 using the reverse of the MP path.
Cryptographically signs the messages to prevent the intermediate nodes from
manipulating the payments.
5 uses the global replacement path to send a test packet In this packet, S asks
each intermediate node v to sign its two neighbors. Finally, D sends a packet through
the reverse MP path to S. In this packet, D tells 5 that it is ready to receive the
packets so S can start sending its packets. The data transmission phase starts with S
sending its data packets to D using the computed path. The payments of the
intermediate nodes are included with the sent packets. The intermediate nodes
forward the data packets and collect the payments at the same time. The data
transmission phase terminates if one of the following two cases happened. First, if the
source node 5 has completed sending its packets. Second, if the network topology is
50


changed. If the second case happened, then S has to start the route discovery phase
from the beginning.
7.7 Example
To clarify the pricing scheme, we present the following example:
Figure 7.2: Example of Network Topology [6]
In this example, the intermediate nodes are labeled with their power levels
(types). The sender proposes a price of 100 to send its packets to the destination. The
communication should take place via the path with minimum energy (the path with
bold edges).
51


The sender S wants to pay at most 100 units to connect the destination node
D. The minimum energy path MP, the replacement path for each node on MP, and
the global replacement path P_MP are computed by D where:
MP = K,v3,v9} c{MP) = 26
P~Vl = {V5, v3, Vg]
P~v3 = {v1( v4, V1Q]
P~V9 = [vv v3, vB)
p-MP = {v2,V7,Vn}
c(P~Vl) = 31
c(P~v3) = 55
c(P~V9) = 30
c(P~MP)= 56
Since the computed price that S must pay c(P~Mf>) = 56 is less than the
proposed price (100), then the minimum energy path MP is feasible. The following
are the payments for the intermediate nodes on the in the chosen path:
pay(Vi) = c(P-v0 c(MP) + KvJ = 31 26 + 5 = 10
pay(v3) = c(P~v3) c(AfP) + l(y3) = 55 26 + 20 = 49
pay(t?9) = c(P-V9) c(MP) + i(v9) = 30 26 + 1 = 5
Since the total payment is 64 and 5 pays only 56 units, then the destination
node D pays the remaining amount which is 8 units.
52


8. Conclusion
In this thesis, recent research on selected aspects of wireless ad hoc networks
has been surveyed.
The protocols and techniques that we presented in this thesis showed how the
performance of the ad hoc network can be improved. The watchdog and path rater
technique for example increase the throughput by 17% in a network with moderate
mobility. During extreme mobility, the throughput is increased by 27%. The
watchdog and pathrater technique also increase the percentage of overhead
transmission from 9% to 17% in moderate mobility and from 12% to 24% in
extreme mobility.
Some protocols were simulated. For example, the authors of the Confidant
protocol used the mobile ad-hoc simulator GloMoSim to simulate their protocol. The
area of the simulation was 1000 m X 1000 m which presents the center of a town.
The speed was between 0 and 20 m/s and the radio range was 250 m. The sending
capacity of the simulation was 2 Mbps and the size of each packet was 64 B. The
simulation was run for 900 s. The simulation results showed a significant
improvement in the good put when the Confidant protocol is applied. Even with a
53


fraction of misbehaving nodes as high as 60% the protocol is scalable in terms of the
total number of nodes in a network and performs well.
The Sprite system was evaluated using the library Crypto + +4.0. The
mobile node that was used in the evaluation was a laptop with an Intel III processor at
866 MHz with Windows XP operating system. The length of a message payload was
1000 bytes. The evaluation showed that the overhead of the system was significant. It
also showed that the nodes would cooperate and forward each others messages
unless their resources are extremely low.
Corsac protocol was also implemented using the GloMoSim package. In this
implementation, the nodes were distributed in an area of 2000 by 2000 meters. Each
node had two transmission power levels at 7 and 14 dBm. The a value of each node
is 1. The time interval between two sessions from the same node was set to 60
seconds. The number of packets in each session was between 1 and 10 and the size of
each packet was 1024 bytes. The implementation showed that the Corsac protocol
was providing incentives for nodes to forward packets in a manner that improves
networks performance.
54


The following table shows the features of the protocols that we have studied
in this thesis.
Table 8.1 The Features of the Protocols
The Protocol The Description
Dynamic Source Protocol with Watchdog and Path Rater The node in this protocol is always busy watching the other nodes in the neighborhood. This operation costs the node to spend its resources even while it is not forwarding packets. This protocol can be classified as an expensive protocol in terms of resources.
Confidant Protocol The node in this protocol applies many systems in order to watch the behavior of the other nodes in the neighborhood. These systems work all the time to collect information about any misbehavior and to use this information later to route data through the cooperating nodes and ignore routing through the misbehaving nodes. Moreover, the node in this protocol sends alarm and notification messages each time it detects some misbehavior. All the above operations make the protocol a secure but at the same time they require the node to spend a lot of resources in order to done these operations.
Core Mechanism In this mechanism the node watches the nodes in the neighborhood and calculates their reputation all the time. In addition, the node sends messages to its neighbors each time it detects any misbehavior to notify them of the misbehaving node. This work makes the mechanism reliable and secure for sending the data but at the same time it requires the nodes to spend a big amount from their resources to obtain these reliability and security.
Sprite System This system adopts the strategy of charging the sender and paying the intermediate nodes. This strategy encourages the intermediate nodes to forward the packets of the other nodes because this forwarding gives them more credit. Moreover, the system prevents the nodes from sending useless messages because they have to pay for any message they send. The node in this system is given a credit for the amount of resources it
55


spends for forwarding the packets of the other nodes. Even the source node that pays for sending its own packets will be given credit when it plays the role of an intermediate node.
Corsac Algorithm This protocol consists of two stages, the routing stage and the forwarding stage. The source node starts the communication by indicating the destination that it wants to send data to. The intermediate nodes on the path between the source and the destination forward the communication request until it reaches the destination node. The destination node computes the path from the source to the destination, the cost of this path, and the payment that should be given to each intermediate node on the path. It can be noticed that only the nodes on the path between the source and the destination participate during the communication. The protocol encourages the intermediate nodes to forward the packets of the other nodes by giving them a payment for each packet they forward.
Commit Protocol As in the previous protocol, the source node sends a request to communicate with the destination node. When the destination node receives the request through the intermediate nodes, it computes the minimum energy path from the source to the destination and the payments for the intermediate nodes on this path. The source node start sending its packets through the computed path and it also sends the payments to the intermediate nodes through the same path. Only the nodes that are on the path participate by forwarding the packets and they are given payments for this cooperation.
Recommendations regarding applicability of these protocols need to take into
account the following properties of the protocols: the first three protocols that used
the reputation of the nodes to rout and forward data cost the nodes a lot of resources.
The nodes it these protocols return the favorite by forwarding the packets of the
cooperating nodes while they deny serving the misbehaving nodes. However, the last
56


three protocols do not require the nodes that are not on the chosen path to do any
activity. They also apply giving payments to the nodes on the path that forward the
data packets so the nodes are always encouraged to forward the packet of the other
nodes.
In terms of evaluation and relative usefulness of the considered protocols, I
rank them as the follows, from most useful to least useful:
1- Payment Based Protocols:
a. Sprite System
b. Commit Protocol
c. Corsac Algorithm
2- Reputation Based Protocols:
a. Dynamic Routing Source Protocol with Watchdog and Path Rater
b. Core Mechanism
c. Confidant Protocol
The first three protocols took their positions based on the strategy they belong to
which is the strategy of giving payment to the cooperation nodes. By using this
strategy the nodes do not need to participate unless they are part of a chosen path so
they spend their energy only when they are forwarding packets.
57


On the other hand, the last three protocols deserved their positions also based on
the strategy they belong to which is the strategy of watching the neighbors all the
time. In this strategy the nodes are always spending their energy watching the other
nodes in the neighborhood even when they are not part of a chosen path and they are
not forwarding packets.
Within each group, the protocols are evaluated based on their simplicity, from the
simplest to the more complex.
58


References
1. L. Anderegg and S. Eidenbenz. Ad-hoc VCG: a truthful and cost-efficient
routing protocol for mobile ad hoc networks with selfish agents. In ACM-
MobiCom, San Diego, September 2003.
2. S. Buchegger and J. Y. Le Boudec, Performance analysis of the CONFIDANT
Protocol (Cooperation of Nodes-Fairness In Dynamic Ad-Hoc Networks).In
Proceeding of the ACM Symposium on Mobile Ad Hoc Networking and
Computing (MobiHoc), Lausanne, Switzerland, June 2002.
3. L. Buttyan and J.-P. Hubaux. Enforcing service availability in mobile ad hoc
WANs. In Proceeding of the ACM Symposium on Mobile Ad Hoc
Networking and Computing (MobiHoc), Boston, MA, USA, August 2000.
4. L. Buttyan and J.-P. Hubaux. Simulating cooperation in self-organizing
mobile ad hoc networks. In ACM/Kluwer Mobile Networks and Applications
(MONET) Special Issue on Mobile Ad Hoc Networks, volume 8, October
2003.
5. Richard Dawkins. The Selfish Gene. Oxford University Press, 1989 edition,
1976.
6. S. Eidenbenz, G. Resta, and P. Santi, Commit: A sender-centric truthful and
energy-efficient routing protocol for ad hoc networks with selfish nodes.
International Parallel and Distributed Processing Symposium (IPDPS), 13,
2005.
7. Lei Guang and Chadi Assi. Cross-Layer Cooperation to Handle
MACMisbehavior in Ad Hoc Networks. Concordia Institute for Information
System Engineering, Concordia University, Montr'eal, Qu'ebec, Canada,
2006.
8. S. Marti, T.J. Giuli, K. Lai, and M. Baker, Mitigating routing misbehavior in
mobile ad hoc networks, In Proceeding of the ACM Conference on Mobile
Computing and Networking (MobiCom), Boston, Massachusetts, USA, 2000.
59


9. P. Michiradi and R. Molva, Core: A collaborative reputation mechanism to
enforce node cooperation in mobile ad hoc networks. In Proceedings of the 6th
IFIP Communications and Multimedia Security Conference, Portoroz,
Slovenia, Sep. 2002.
10. S. Zhong, Y. R. Yang, and J. Chen. Sprite: A simple, cheat-proof, credit-based
system for mobile ad hoc networks. In Proceeding of the IEEE Conference on
Computer Communications (INFOCOM), San Francisco, CA, USA, March-
April 2003.
11. S. Zhong, L. E. Li, Y. G. Liu, and Y. R. Yang, On designing incentive-
compatible routing and forwarding protocols in wireless ad-hoc networks.
ACM Springer Wireless Networks (WENET), Special Issue of Selected Papers
of Mobicom 2005, 2007.
12. http://www.priceline.com. 2010.
60


accept such thinking. They argue that many scholars believe that the theory of
acquired historical rights alone does not represent much significance. For example,
Professor Stephen McCaffrey, who has been a member of the International Law
Commission (ILC) as of 1985, pointed out that:
A downstream State that was first to develop its water resources could
not foreclose later development by an upstream State by demonstrating
that the later development would cause it harm; under the doctrine of
equitable utilization, the fact that a downstream State was 'first to
develop (and thus had made prior uses that would be adversely affected
by new upstream uses) would be merely one of a number of factors to be
taken into consideration in arriving at an equitable allocation of the uses
and benefits of the watercourse. (TMFA, 1996:18).
The Turks make use of McCaffreys observation, which indicates that
acquired historical rights cannot be used as a claim to limit the utilization of water
by upstream riparians. In other words, the historical and acquired rights, claimed
by Syria and especially Iraq, are inadequate. They represent only one of many factors
that must be taken into consideration in determining an equitable utilization of
international watercourses.
Also, Article Vn of the Helsinki Rules states that A basin state may not be
denied the present reasonable use of waters of an international drainage basin to
reserve for a co-basin state a future use of such waters. Obviously, Turkeys
massive GAP project to develop the Euphrates/Tigris basin violates this article. The
Turks argue that once their national needs are satisfied, they will be ready to
contribute their national resources to the well-being of the neighboring riparian
64


countries (Chalabi&Majzoub, 1995:226). Because of such efforts, Iraq, the
downstream co-riparian with prior established rights, has been receiving less water
from its upper-stream riparians.
Since most of the water feeding both the Euphrates and the Tigris is
generated from within the Turkish territories (88 to 98% of the Euphrates waters
and about 50% of the Tigris waters), the Turks feel that they have a right to make
use of such natural resource as they please. As we know, Syria contributes to the
flow of the Euphrates via al-Sajour, Balikh and the western Khabour, the three
tributaries that run in its territories. Iraq contributes practically no water to the
Euphrates but does contribute substantially to the Tigris through the tributaries that
rise from within its territory. If equitable sharing of the Euphrates/Tigris waters
would be applied according to the factors based on geography and hydrology, this
would probably, as Kliot views, assign Turkey some 40% of the combined waters,
Iraq 50% and Syria 10% (Kliot, 1994:116). However, he argues that if the factor of
the non-availability of other water resources or population dependence were
considered and given priority in the process of sharing the waters of the
Euphrates/Tigris, both Iraq and Syria would precede Turkeys rights in the
Euphrates/Tigris waters. Kliot believes that these two factors satisfy the principles of
equity and justice than the factor of Turkeys contribution to the water balance of the
basin (Kliot, 1994:150).
65


Rather than giving priority to acquired historical rights, Hillel gives more
weight to the real needs of each of the co-riparians of an international river. For him,
there are certain factors that are associated with real needs such as: the availability
of energy, the need for hydroelectricity, the feasibility of developing economic
alternatives to irrigation-based cultivation, the efficiency of water use, and the size
of each countrys population. (Hillel, 1994:103).
Turkey also violates Article V (h), which examine the availability of
alternative water resources. As we have seen in part I, Turkey has a superior water
supply in comparison with both Syria and Iraq. Turkey has 26 river basins within its
territory with a total average annual runoff of 185 BCM, only 62 BCM of which, as
estimated by the Turkish State Hydraulic Works, will be consumed each year after
the year 2000 (Kolars, 1994:63). That is to say, Turkey has very rich water resources
which could be developed for irrigation, thus leaving large amounts of the
Euphrates/Tigris flow for Syria and Iraq. The Euphrates/Tigris discharge comprises
40% of the total water supply of Turkey as compared with 80-85% in Syria and 98%
in Iraq (Kliot, 1994:150).
The principle of not causing an appreciable harm to other co-riparians also
enjoys wide support. But, from the Turks point of view, domestic policies regarding
water utilization in the three countries have to be reviewed. For the Turks, the Syrian
and the Iraqi claims to share the Euphrates/Tigris waters violate the fair, reasonable
and optimal utilization of the waters of the Euphrates/Tigris. Turkey claims that both
66


Iraq and Syria have a great deal of less fertile and unproductive land which is not
economically feasible for agriculture. However, they insist that Turkey gives them
considerable amounts of water to irrigate these unproductive land. Therefore, the
Turks argue that a study should be made of all the lands in the three countries in
order to determine for which of these lands irrigation makes economic sense. The
Turks assert that the measures preventing the waste of water, in particular the
application of a rational water pricing system, must be implemented (TMFA,
1996:19). Accordingly, Turkey has offered Syria and Iraq a plan for optimal,
equitable and reasonable utilization of the Euphrates/Tigris waters. This suggestion
could be seen by Syria and Iraq as an act of intervention in their domestic policies.
In conclusion, one can say that although the public international law clearly
defines the international watercourses, still there is no legally binding formula based
upon constant principles and rules in regard to utilization and distribution of the
waters of international rivers. There are no general international treaties that regulate
the utilization of the waters of international rivers. It is true that the general rules of
public international law, such as good neighborhood, good intention and the like are
helpful in dealing with the issue of international rivers (Al-Samman, 1992.65). It is
also true that both the Helsinki Rules and the rules of the UN Draft Articles seem
reasonable. They are very helpful, especially when there is no binding formal
agreement between the riparians of an international river (Amer, 1994:454). But,
their usefulness is limited because they do not provide any measures to determine
67


which rule should be given priority over others. In addition, these rules are not
exclusive, as Fares indicates (Fares, 1993:68).
David Goldberg, the Assistant Legal Counsel of the World Bank, is right
when he states that the law on international waterways is one of the most unsettled
areas of international law. (Gruen, 1992:5-6). Therefore, it seems that only
cooperation and integrated planning among the riparians will assign each of them the
best available amount of water resources. This leads us to the fourth and last part of
this study, which addresses the potential for basin-wide cooperation among the
riparians of the Euphrates/Tigris.
68


CHAPTER 4
THE POTENTIAL FOR EUPHRATES/TIGRIS BASIN-WIDE
COOPERATION
This chapter addresses the potential for basin-wide cooperation. It examines
the existing agreements in regard to the use and distribution of the Euphrates/Tigris
waters, challenges to cooperation and the means of overcoming such challenges. It is
divided into three sections. The first presents the existing water agreements in regard
to the Euphrates/Tigris. The second discusses the challenges for basin-wide
cooperation. The third section looks at the possible ways of overcoming such
challenges.
Although the recent trends in international law assert that other co-riparians
possess rights that could not be ignored because of the sovereignty of a riparian
country over the part of an international river that runs through its territory,
application of the international legal rules and principles of allocating shared waters
reveals major limitations. These limitations arise from the lack of priority ranking
order of the various factors that determine the allocation of the waters of
international rivers. Giving equal weight to all regulating rules specified by
international law or acknowledging that the rank of these factors varies according to
69


the situation encourages countries to pursue conflicting sovereignty doctrines. Those
who adhere to the Theory of Absolute Territorial Sovereignty focus on the rule
that each riparian has to do what it believes suitable to make use of the waters that
run through its own territory as any other natural resource. And those who adhere to
the Theory of Absolute Territorial Integrity see that no one has a right to change
the course or the flow of and international river.
In other words, there are no clear cut international legal rules to settle
international water disputes. Accordingly, each riparian state adheres to its right to
exercise sovereignty over the part of the river that runs through its territory providing
that it does not cause any appreciable harm to other co-riparians, which is always
interpreted differently by various parties according to their interests.
While Turkey, an upstream country, claims an absolute right to use the water
resources within its territories in whatever way it thinks suits its own interests and
purposes, downstream countries, on the other hand, tend to emphasize that the
natural course and flow of the two rivers must be respected and preserved. They also
claim that their prior use of the two rivers water give them acquired historical rights
that must be taken into consideration and fully respected by Turkey.
Turkey asserts that its commitment to the water needs of Syria and Iraq does
not impose on it any commitment to make any compromise or negotiations that
affects its sovereign rights over the Euphrates/Tigris waters. Accordingly, the Turks
claim that there should be no problem between the three riparians of the
70


Euphrates/Tigris basin because of the Attaturk Dam or any of the GAP projects
because Turkey did not sign any treaty in regard to the utilization and distribution of
these waters. Several Turkish officials and scholars asserted this argument during the
block of the Euphrates River in 1990 (Mouawad, 1992:770).
Also, the Turks argue that the construction of dams on the Euphrates is
designed to regulate the flow of water. Such regulation does not only serve the
interests of Turkey, but also contributes to the water needs of both Syria and Iraq. To
support their argument, the Turks make use of the natural fluctuation of the
Euphrates. They state that the flow of the river may fall as low as 100 CM/S during
the summer while it could reach a high as 7,000 CM/S during the spring when the
snow melts. The existence of the dams enables Turkey to provide a regular flow of
500 CM/S to its neighbors throughout the year, even dining the three consecutive
drought years of 1989, 1990 and 1991. Accordingly, they claim that the main
beneficiaries of this regular flow of water have been Syria and Iraq. In other words,
water storage in Turkey will also have a positive effect on Turkeys co-riparians
since the deficiency in natural flow could be make up by water from the reservoirs
behind the Turkish dams protecting Syria and Iraq from droughts
(Bulloch&Darwish, 1995:68-69).
As noted earlier, the relations between the three co-riparians of the
Euphrates/Tigris basin have gone through moments of crisis and tension, which
impede negotiation of a comprehensive agreement in a spirit of mutual trust. Part of
71


the reason for the unilateral efforts to harness the Euphrates/Tigris and the attempt to
construct storage facilities is the lack of trust among the three co-riparians. Each is
trying to appropriate as much water as possible for itself. While both Syria and Iraq
desperately seek a comprehensive agreement, it seems that Turkey, the upstream
riparian, has no intention of entering into any tripartite agreement with them in
regard to the allocation of the Euphrates/Tigris waters.
1. Existing Water Agreements in Regard to the Euphrates/Tigris:
Formally there is no legal international treaty that regulates the sharing of the
Euphrates/Tigris waters. However, agreements laying down general principles in this
regard were concluded. When Syria and Iraq were under the French and British
mandatory rule, the two ruling powers agreed to establish a committee to coordinate
water utilization in the basin.
During the Mandate era, several agreements on the common utilization of the
Euphrates/Tigris waters were concluded between the British and the French and
between the French and Turks. The most important of these agreements is the
Franco-British Convention of 1920 which asserts the coordination of water
utilization. In accordance with the principle of succession, this convention was
inherited by Syria and Iraq. In addition, there were two agreements between France
and Turkey. The first was in 1920 which put certain regulation for the utilization of
72


the Euphrates waters. It was mainly in regard to the Koveik tributary which supply
Aleppo with water. It also addressed the possibility of tapping the waters of the
Euphrates. Article 12 of this agreement states that:
the water of Koveik will be divided between the town of Aleppo and
the town and the region of the North, which have remained Turkish, in
such a way as to give equal satisfaction to both Parties
(Chalabi&Majzoub, 1995:193).
The second agreement was signed in 1930 which confirmed the previous
agreement and established a new principle in regard to the joint ownership of the
Tigris River. It mainly dealt with the issues related to the joint ownership of the
Tigris River. There is also a Friendship Agreement between Turkey and Iraq in 1946
in which Turkey obliged itself to report to Iraq on all its plans to utilize the
Euphrates/Tigris. This even gave Iraq the right to construct dams within the Turkish
territory when the purpose was to prevent downstream flooding (Chalabi&Majzoub,
1995:192-194).
Unfortunately, none of these agreements and protocols received the expected
respect and attention. This lack of respect and attention has increased since the
1960s, when each of the three riparians, especially Turkey and to some extent Syria,
began to implement unilateral projects to harness the two rivers, mainly the
Euphrates.
73


However, there was some sort of cooperation. In addition to the Joint
Technical Committee for Regional Waters which was established in 1980 as an
active organization that reflects a cooperative trend among the Euphrates/Tigris
riparians, there are two partial agreements in regard to the Euphrates/Tigris.
a) The 1987 Turkish-Svrian Protocol:
In 1987, Turkey agreed to increase the flow of the Euphrates from 450 to 500
CM/S, a quantity equal to 15.8 BCM/year out of 28.9 BCM annual average discharge
of the Euphrates River. In fact, there were some prior agreements to this one. In
1964, for the first time, Turkey pledged to release 350 CM/S from the Euphrates
downstream for its co-riparians. In 1976, during Syrias impoundment of water for
the al-Thawrah Dam, Turkey increased the minimum flow to 450 CM/S in order to
prevent a conflict between Syria and Iraq (Kliot, 1994:161). The 1987 Protocol
makes it clear that in the event that the monthly flow should fall below the level of
500 CM/S, Turkey agreed to make up the difference during the following month
(Hillel, 1994:103). Iraq has always objected to the setting of such a low figure. Both
Syria and Iraq interpret this agreement as a temporary measure to cover only the
period of the filling of the Attaturk Dam reservoir. Once the dam is at full capacity,
both countries would expect average flows to return to between 600-700 CM/S
(Robins, 1991:89-90).
74


b) The 1990 Svrian-Iraoi Accord:
In 1990, following the Turkish-Syrian Protocol of 1987, Syria and Iraq
agreed that the 15,8 BCM Turkey agreed to release to Syria, or any quantity of
Euphrates waters that enters Syria will be divided between the two countries as
follows: 42% to Syria and 58% to Iraq (Hillel, 1994:103).
There are three remarks on the Turkish-Syrian Protocol and the Syrian-Iraqi
Accord:
First, these two most recent agreements refer only to the Euphrates and not to the
Tigris.
Second, there is no comprehensive agreement.
Third, no serious negotiations have yet taken place among the three riparians of the
Euphrates/Tigris. Turkey, as an upstream riparian, still denies the international
character of the Twin Rivers, which contradicts its 1987 Protocol with Syria, and
insists on its full sovereignty over their waters. Turkey claims that it has no
international commitments in regard to the Euphrates/Tigris waters. The only
obligation the Turks referred to is to negotiate with the concerned parties before
starting on implementing any projects on the two rivers.
75


2. Challenges to Basin-Wide Cooperation:
One of the major characteristics of the water problem in the Euphrates/Tigris
basin is the use of water as a political weapon and a pressure card to solve other
problems. In other words, the relations among the three co-riparians of the
Euphrates/Tigris basin are not limited to water issues since there are other sources
for tension and even conflict. Many scholars argue that the link between water
problems among the Euphrates/Tigris co-riparians and politics is very clear. For
example, Al-Samman sees that the problem of allocating the waters of the
Euphrates/Tigris as a political game affected by political differences (Al-Samman,
1992:23).
Fares states that the main problematic issue between Syria and Turkey is a
political one and that water is not but a tool of mutual pressure between the two
countries (Fares, 1993:60). Similarly, Turan (1993) sees the problem as a man-made
and a political one that is closely tied to politics. He argues that states, being the
major actors in the international system, always try to maximize their sovereign
rights as well as their security. Riparian countries see close linkages between water
availability and their economic security. This leads them to view the control over
water resources as a vital security interest, which can only be legitimized by appeals
to sovereign rights. Also, a riparian country which feels threatened by the actions of
another riparian or riparians may resort to the use of other non-water related
76


resources to modify the behavior of its co-riparians on water questions (Turan,
1993:152-154). Although Turkey has formally stated that the waters of the Euphrates
and the Tigris Rivers will not be used as a political weapon, it is difficult to imagine
that water is not, or will not be used, whether explicitly or implicitly, as a lever of its
foreign policy (Robins, 1991:99).
The above argument is clearly represented in the incident in which Turkey
declared in January 1990 the blocking of the Euphrates River for about a month in
order to be able to fill the reservoir behind its newly built huge Attaturk Dam. This
decision led to a tension in both Turkish-Syrian and Turkish-Iraqi relations. Both
Syria and Iraq protested and demanded that Turkey moderate its enormous GAP
development. According to Kolars (1994), the filling of the reservoir behind the
Attaturk Dam could have been done in two ways: 1) the diversion channel could
have been left partially open, so that some water would continue to flow
downstream; 2) a quicker way was to block the flow of water to Syria altogether.
The second option was the one the Turks chose despite their protocol with Syria in
which Turkey committed itself to allow an average flow of500 CM/S into Syria.
While the Turks claim that there were some technical necessities behind the
blocking of the river to only one-tenth of its natural flow, the Syrians and the Iraqis
insisted that there were certain political motives and not technical ones behind the
Turkish action (Kolars, 1994:49). Both Syria and Iraq understood the action as a
77


Turkish message that Turkey has its hand on the tap and can starve them of water
whenever it chooses to do so.
It seems that there were certain political motives behind the decision by the
Turkish authorities. Among such motives was the shooting down of a Turkish land-
survey airplane within the Syrian territories by a Syrian Mig-fighter in October 1989,
in which Turkey claimed a compensation of $14.5 million. In addition, there was
Turkish pressure on both Syria and Iraq to stop the Kurds subversive activities
across the borders. The Turkish government threatened to block the flow of the
Euphrates water if Syria did not stop the trespassing of the Kurdish rebels into
Turkey. It seems also that President Assad had decided that he needed something
with which to bargain in his dealings with Turkey over the allocation of the
Euphrates waters. In order to have some extra cards in his hands, President Assad
invited some members of the Turkish Peoples Liberation Army and some other
factions of the revolutionary left, who returned to Turkey from Syria after
completing their training courses in guerrilla warfare against the Turkish regime. By
blocking the Euphrates flow, the Turks wanted to show President Assad that he was
not the only one who could dissimulate (Bulloch&Darwish, 1995:60,66).
Obviously, the Kurdish insurgency is one of the most important political
issues that affects water problems in the Euphrates/Tigris basin. Turkey, which
severely suppresses Kurds within its territory, criticizes Syria for constantly arming
and supporting the Kurdish guerrillas affiliated with the Kurdish Workers Party
78


(PKK). In practice, the Kurdish people were brutally suppressed in their eight
provinces of the countrys southeast, and was discriminated against when they
migrated to the relatively prosperous areas of the country. This largely explains the
GAPs political importance to Turkey which seems unlikely that the Turks will give
up their plans to harness the Euphrates/Tigris in the southeastern part of their
country (Kliot, 1994:125-126).
A major objective of the GAP project, as the Turkish officials frequently
explain to the Syrians and the Iraqis, is to improve living conditions of the Kurds.
The Economic Director in the Turkish Foreign Ministry, Mr. Utkan, once stated that
There are two ways to deal with an unhappy sector of your population; you can
crush them or you can try to improve their living and working conditions. Turkey has
opted for the second.. Turkish officials have expressed fears that Syria may try to
use Kurdish separatist guerrillas to sabotage the Attaturk Dam. From the Turkish
standpoint, the Kurdish revolt endangers Turkeys efforts to develop the GAP. In
October 1989, Prime Minister Ozal accused Syria of violating the 1987 protocol on
security and threatened to cut the flow of the Euphrates River into Syria unless the
latter ended its support to the Kurdish rebels. In fact, the two countries signed this
protocol in which Syria pledged to stop supporting the Kurds in exchange for which
Turkey made its pledge to provide 500 CM/S of water from the Euphrates into Syria
(Gruen, 1992:9). Bulloch and Darwish argue that such support was President Hafez
Assads direct response to Turkeys decision to harness the abundant waters of the
79


Euphrates/Tigris in a huge project bound to have effects far beyond Turkeys
borders. Bulloch and Darwish (1996) state that the Syrian Government realized that
it had a lever that could be used to force Turkey to take account of its water
demands. Therefore, it believed that it was the time to give full backing to the
Kurdish rebels (Bulloch&Darwish, 1996:59,62).
In 1992, the Turkish Foreign Minister claimed that Syria was using the
Kurdish rebels to put pressure on Turkey over water. He stated that: It is true that
Syria does have a habit of working through proxies. It was about 1980 that we
started talking very seriously about expanding the GAP project, and it was about that
time that Oclan (the Kurdish rebel leader) began getting help from Damascus. You
could make a connection. (Bullock&Darwish, 1996:71).
Another political issue is that Turkey wants to include the Orontes River in
any comprehensive settlement of the water dispute. The Orontes River rises in
Lebanon and flows through Syria and Turkey into the Mediterranean Sea. The Turks
claim that Syria started some constructions over the river without prior consultation
with Turkey. There are two dams constructed on the Orontes: one in Syria and the
other in Lebanon. The Orontes water, the Turks claim, is used for land irrigation in
Alexandaretta. However, during the summer season the river always dried up before
it reached Turkey. The Turkish argue that:
If a comparison is made between the utilization of the Orontes and the
Euphrates, there is justified cause for Turkey to complain about how the
80


water of the Orontes is completely consumed by Syria and Lebanon,
while Turkey releases 500CM/S of water even when the velocity of the
Euphrates falls to 100 CM/S. (Bulloch&Darwish, 1996:69).
But, since the flow of the Orontes River is only 459 MCM/year (that is less
than 2% of the Euphrates total annual flow), it will not hurt Syria at all to share its
water if Turkey agreed to sign a comprehensive agreement in regard to the Euphrates
(Sobhi, 1992:16). In fact, there is another major political issue. Mentioning of the
Orontes by the Turks rang many alarm bells in Damascus. A general agreement with
Turkey would have to cover the Orontes River, but that would bring in the dispute
over the Province of Alexandaretta, as the river runs through that comer area of
Turkey. The Syrians think the Turks would take an agreement on the Orontes as
recognition of Alexandaretta as Turkish. No doubt that the Syrian fears have their
justifications. When Turkey signed the 1987 Protocol with Syria, in which it
committed itself to release 500 CM/S into Syria through the Euphrates, it asked at
the same time for two specific security requests. The first one is to put an end to the
opposition Kurdish Labor Party. The second request was to erase Alexandaretta from
Syrian maps (Abdel-Rahman, 1992:527).
Thus, the conflict over the Province of Alexandaretta (Arabic Iskanderuna,
Turkish Hatay) is another related political issue that could be connected to water
disputes between Turkey and Syria. It is an old conflict between the two countries
since the Province was handed over to Turkey by France, the then mandatory ruler of
81


Syria, in 1939 as a bribe for entering W.W.n on the side of the Allies. The Syrians
have never accepted this territorial loss. Their maps still show the territory as part of
Syria (Kliot, 1994:165).
It is true that there is a mix between politics and water problems, the late
Turkish President Turgut Ozal repeatedly threatened to block the flow of the
Euphrates to both Syria and Iraq if the two countries continued their support to the
Kurdish rebels in Turkey. The Turks insist that a comprehensive agreement between
Turkey and Syria largely depends on the cooperation between the two countries to
limit the Kurds subversive activities and to include the allocation of the waters of
all shared rivers, especially the Orontes. By reaching such an agreement Turkey
wants the Syrians recognition of its sovereignty over Alexandaretta, which the
Syrians totally reject (Al-Samman, 1992:24).
Also, Turkeys role in Middle East affairs has changed sharply in the last two
decades. The Turks are making their bid for recognition as a major player in the
regions politics. Having failed in their effort to turn toward Europe and to be
accepted by the European Economic Community, the Turks, Mouawad argues, are
trying to make use of their natural resources at a time their surplus manpower is
rejected in Europe (Mouawad, 1992:787). The end of the Cold War and the
dissolution of the Soviet Union and the Warsaw Pact led to the diminishing of the
strategic value of Turkey, from the Western point of view, which was considered as
the guardian of the Turkish strategic straits (Eliwa, 1995:10). In short, Turkey began
82


to seek to play an active role in the Middle East and to be recognized as a major
regional power, especially after the two Gulf wars.
In addition to the political challenges, there is also a cultural challenge.
While GAP is a source of great pride to the Turks, it is a source of great worry for
the two downstream riparians. Among the Turkish population the water problems of
the Arab neighbors do not arouse much sympathy. The popular mood expressed by
the Turks reveals that the water problem of the Euphrates/Tigris is the Arabs
problem, not ours. Allah gave them oil under their soil, but gave us water in ours....
When they send us their oil free in their pipelines, well send them water in ours. If
they insist on fighting over the water, well fight (Gruen, 1992:7).
Finally, the differences do not exist only between Turkey on the one hand
and both Syria and Iraq on the other. Rather, there are many differences between the
ruling Baath Party in both of the two concerned Arab countries, Syria and Iraq.
3. The Potential for a Cooperative Alternative;
The present existing agreements in regard to the allocation of the
Euphrates/Tigris waters, together with the unilateral, separate drive for development
in the basin, will probably lead the three co-riparians to a certain degree of conflict
in the near future unless some cooperative measures are taken.
83


Obviously, there are differences among the three riparians. Turkey claims
that both rivers are transboundary. Accordingly, their water should be used in an
equitable, reasonable and optimal manner. It is necessary to conduct an inventory
of all arable lands in the basin in order to establish the optimal crops for each area as
well as the amount of water needed for the successful cultivation of such crops. Both
Syria and Iraq strongly object to the Turkish claims and insist that international law
asserts that the management and sharing of international rivers be equally in the
hands of all the concerned riparians (Kolars, 1994:87-88).
In addition, the Euphrates/Tigris co-riparians have different socio-economic
features which makes it difficult to weigh their rights to the waters of the two rivers.
While Iraq enjoys high incomes derived from oil, it suffers foreign debts and
destruction because of its two Gulf wars. Iraq also has an unfavorable climate and is
totally dependent on the Euphrates/Tigris waters. At the same time, Iraq has
unchallenged acquired historical rights to large amounts of the Twin Rivers water.
Turkey, on the other hand, is making an enormous effort to achieve self-sufficiency
in food production. The country lacks mineral resources and is completely dependent
on oil imports. However, Turkey has sources of water supply. Syria also is greatly
dependent on the Euphrates water. It also lacks mineral resources and suffers
economic difficulties.
Taking all this into consideration as well as other water-related and political
issues, a big effort is needed. In order for negotiations to reach a successful
84


settlement to the water problems among the Euphrates/Tigris co-riparians, the three
countries need to address solutions not only to water disputes, but also to the
previously mentioned political issues. In other words, workable solutions to water
problems should also address the constraints posed by regional politics. Wolf argues
that water problems could lead directly to both heightened political tensions and
opportunities for cooperation as well (Wolf, 1994:38). Competition will lead only to
more competition while cooperation encourages better relations, which could create
an environment conducive to increased cooperation (Wolf, 1994:7). In short,
political objections to water cooperation must be overcome in order to achieve an
efficient management of the Euphrates/Tigris waters for the benefits of all parties.
Since the single most important impediment to regional water resource
planning is the lack of a basin-wide water authority, any negotiations, Wolf (1994)
argues, should emphasize regional planning as a crucial goal (Wolf, 1994:38). Turan
(1993) states that regional organizations for data collection and water conservation
will help at confidence building between countries of the basin as they feel more
secure. Such organizations which aim to enhance mutual interdependence may help
reduce emphasis placed on sovereignty (Turan, 1993:152).
Wolf also argues that the better a states hydro-strategic position, the less
interest it has in reaching a water-sharing agreement. Therefore, strong third-party
involvement will be necessary for successful negotiations (Wolf, 1994:38). Joyce
Starr and Daneil Stoll argue that the US can play such a role. It can participate in the
85


efforts of developing water resources in the area, including the Euphrates/Tigris,
through the supply of sophisticated technology in the realm of water as well as
providing training programs for water specialists (Starr&Stoll, 1995:155).
Mouawad (1992) adds that the Arab-Turkish economic and political relations
should be developed in order to provide incentives and interests for Turkey to accept
the settlement of the water issue in a way acceptable to the two Arab partners
(Mouawad, 1992:787).
For Kliot (1994), a compromise could be based on a reduction in Turkeys
planned utilization of large amounts of the Euphrates flow, which will leave more
water for Syria and Iraq who are clearly more dependent on it. Both rivers can be
used for electrical hydro-power generation in Turkey as this is a non-consumptive
use of water. Iraq could be able to use water from the Tigris and its tributaries and
divert some of their waters to the Euphrates River through the already existing
Thurthar Canal. He also suggests that an increase of the Euphrates flow to from 15.8
to 19-20 BCM would leave Turkey with 6-8 BCM for impoundment in its storage
reservoirs. This would leave the two downstream countries enough irrigation water
in their section of the Euphrates basin (Kliot, 1994:150). Kliot adds that Turkey
should not have to withdraw more than 5 BCM for its agricultural needs and
hydroelectricity production in the GAP. Iraq should give up some of its share in the
Euphrates water to Syria providing that it could have the total flow of the Tigris at its
disposal (Kliot, 1994:171).
86


To sum up, the unilateral efforts adopted by all of the three co-riparians of
the Euphrates/Tigris basin reflect mutual distrust and lack of confidence because of
political, ideological and cultural differences. Overcoming political impediments is a
necessary step towards an efficient management of the Euphrates/ Tigris waters for
the benefit of all concerned parties. Establishing a basin-wide water authority is
another important step towards water cooperation. The alreading existing Joint
Technical Committee for Regional Waters can help in confidence building. These
efforts can be encouraged and enhanced by an active role of concerned strong third
party, such as the US and international organization, such as the United Nations.
87


Conclusion:
The sharing of jointly-owned water resources is a complex issue and a source
of tension and conflict in many areas of the world. But in arid areas, such as the
Middle East, this issue is more complicated. Given the current situation, tensions
over water in the region in general are likely to increase greatly in the near future
unless the concerned parties succeed in reaching some cooperative agreements.
The need for more water led all of the three co-riparians of the Euphrates/
Tigris basin to proceed with extensive irrigation and hydroelectric power generation
projects. Therefore, One of the major keys to the geopolitical competition for the
waters of the Twin Rivers, especially the Euphrates, can be found in the tremendous
reservoirs and storage capacity all three countries developed for themselves. There
are numerous large and small dams, barrages and diversion canals which have been
built, or planned, for the purpose of controlling the flows of both rivers in Turkey,
Syria and Iraq. The most important feature of such efforts to harness the
Euphrates/Tigris waters is the lack of coordination among co-riparians as opposed to
the need for integrated water plans in the basin. This feature can be explained by
mutual distrust and lack of confidence because of political, ideological and cultural
differences.
The Euphrates/Tigris basin, with all its competing national and economic
pressures, provides a clear example of the strategic importance of water as a scarce
88


commodity. It exemplifies how fateful the rivalry over shared waters can be. There is
a growing tension among the three co-riparians of the Euphrates and the Tigris
Rivers: Turkey, Syria and Iraq over their waters. In 1974, Iraq threatened to bomb
the Syrian Al-Thawrah Dam and massed troops along the Iraqi-Syrian borders.
Turkey blocked the flow of the Euphrates River in January 1990 and used its water
as a political weapon against both Syria and Iraq, the two downstream countries. It
seems that this is likely to happen again in the future if the Euphrates/Tigris waters
continue to be used by its co-riparians as a political weapon.
Turkey, the upstream riparian of both the Euphrates and the Tigris, claims an
absolute right to use the waters of the two rivers within its territory in whatever way
it thinks suits its own purposes and interests. Syria and Iraq, the two downstream
riparians, claim that their prior use of the two rivers water give them acquired
historical rights that must be taken into consideration and fully respected by Turkey.
The three co-riparians are pursuing rival doctrines. Both Syria and Iraq consider the
Euphrates and the Tigris as international rivers that should be governed by the
international rules in this regard. But, Turkey considers the Euphrates and the Tigris
as transboundary rivers. Therefore, they can not be governed by the international
legal rules that govern international rivers. It is most likely that such opposing
positions in the presence of multiple and competing needs would result in conflict,
particularly in the absence of recognized criteria and mechanisms for determining
water shares.
89


There are only two partial agreements in regard to the Euphrates/Tigris basin:
the 1987 Turkish-Syrian Protocol and the 1990 Syrian-Iraqi Accord. However, the
absence of a comprehensive agreement between the three co-riparians of the
Euphrates/Tigris does not mean that the two rivers are not international rivers, as the
Turks claim. According to international law, they are international rivers. Therefore,
Turkey has to negotiate with both downstream riparians in regard to the use of the
two rivers waters. Any Turkish water project on the Euphrates/Tigris without prior
consultation with Syria and Iraq is a violation to the principles of established
international law.
One of the major characteristics of the water problem in the Euphrates/Tigris
basin is the use of water as a political weapon and a pressure card to solve other
problems. In other words, the link between water problems among the
Euphrates/Tigris co-riparians and politics is very clear (e.g., the Kurdish issue, the
dispute between Turkey and Syria over the Province of Alexandaretta and the
political and ideological rivalry between the two competing wings of the Baath
Party in Syria and Iraq).
The Turkish GAP project has very serious effects on both Syria and Iraq. It is
expected that this project will divert as much as half of the Euphrates waters into
irrigation canals. Similar plans for the Tigris will follow. Of course, if Turkey has
the right to use the Euphrates/Tigris waters, it does not have the right to deny the
peoples of the two downstream riparian countries the water they have been using for
90


centuries. Obviously, the Turkish position violates the international law and the rules
of justice.
Disputes over water resources do not necessarily lead to conflict. Rather,
some may lead to cooperation. The likelihood of cooperation or conflict depends
on the fact that partners must feel that their interests will be taken into account. A
solution to the dispute over the Euphrates/Tigris waters can be obtained by applying
the principles and rules applicable to similar disputes which determine the rights and
obligations of each riparian country. A good example in this regard is the 1944
agreement between the U.S., the upstream riparian, and Mexico, the downstream
riparian, in regard to the Colorado, Tijunana and Rio Grande Rivers. This agreement
was concluded after the U.S. abandoned the Harmon Doctrine and adopted instead a
flexible approach (TMFA, 1996:28-29).
It seems that only cooperation and integrated planning among the three
riparians will assign each of them the best available amount of water resources.
Interested scholars recommend that the governments of the three riparians of the
Euphrates/Tigris basin should recognize the need to take a reciprocal approach to the
development of the available water resources. They argue that if water rights and
concerns are not cooperatively addressed, then the prevailing critical conditions
would inevitably increase the existing tensions and may even lead to conflict.
Therefore, they stress that broader approaches to solve water problems among the
three co-riparians of the Euphrates/Tigris basin are urgently needed.
91


Appendixes


Full Text

PAGE 1

COOPERATION AND MISBEHAVIOR IN WIRELESS AD HOC NETWORKS by Mahmoud Aljdawi B.Sc., Sebha University, 2001 A thesis submitted to the University of Colorado Denver In partial fulfillment of requirements for the degree of Master of Science Computer Science 2010

PAGE 2

This thesis for the Master of Science degree by Mahmoud Aljdawi has been approved by Bogdan Chlebus Ilkyeun Ra Min-Hyung Choi DeceMber 1-S/) 2o/o Date

PAGE 3

Aljdawi, Mahmoud (M.S., Computer Science) Cooperation and Misbehavior in Wireless Ad Hoc Networks Thesis directed by Associate Professor Bogdan Chlebus ABSTRACT We consider self-organized wireless ad hoc networks that do not rely on a preexisting infrastructure such as routers in wired networks or access points in managed wireless networks. Each node participates in routing by forwarding data for other nodes, and so the determination of which nodes forward data is made dynamically based on the network connectivity. Each node is its own authority so cooperation between the nodes cannot be taken for granted. Nodes may strive to maximize their own benefits by enjoying network services and at the same time minimizing their contribution. Such selfish behavior can negatively impact the network's performance unless a mechanism that makes the nodes to cooperate is provided. In this thesis, we present some protocols and mechanisms that can enforce nodes to cooperate and forward the others' packets. We first introduce the watchdog

PAGE 4

and path-rater mechanisms which identify misbehaving nodes and then help the routing protocol to avoid these nodes. Second, we present a protocol which is based on selective altruism and utilitarianism and makes misbehavior unattractive. After that, we discuss a generic mechanism based on reputation which enforces cooperation among the nodes to prevent selfish behavior. We present also a cheat-proof, credit based system provides incentive for nodes to cooperate and report actions honestly. A cooperation-optimal routing-andforwarding protocol which consists of two sub protocols for routing and forwarding is presented. The two sub-protocols work together to provide incentives for nodes to forward packets. This thesis surveys recent research on selected aspects of wireless ad hoc networks. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Bogdan Chlebus

PAGE 5

CONTENTS Figures ............................................................................................. X Tables ............................................................................................. XI Chapter 1. Introduction .................................................................................... 1 1.1Mobile Ad Hoc Networks ................................................................... 2 1.2 Wireless Mesh Networks ................................................................... 3 1.3 Wireless Sensor Networks .................................................................. 3 1.1 Malice and Selfishness ...................................................................... 3 1.2 Encouraging Nodes Cooperation ......................................................... .4 2. Dynamic Source Routing with Watchdog and Path Rater. ............................... 5 2.1 Introduction ................................................................................... 5 2.2 Route Discovery .............................................................................. 6 2.3 Route Maintenance .......................................................................... 6 2.4 Watchdog ...................................................................................... 7 2.4.1 Ambiguous Collisions ..................................................................... 7 2.4.2 Receiver Collisions ........................................................................ 8 2.4.3 False Misbehavior. ......................................................................... 9 2.5 Path rater. ...................................................................................... 9 3. Confidant Protocol. .......................................................................... 11 v

PAGE 6

3.1 Introduction .................................................................................. 11 3.2 Components of The Protocol .............................................................. 11 3.2.1 The Monitor ............................................................................... 12 3.2.2 The Trust Manager. ....................................................................... 13 3.2.3 The Reputation System .................................................................. 13 3.2.4 The Path Manager ........................................................................ 14 3.3 Good put. ...................................................................................... 14 3.4 Overhead ..................................................................................... 15 3.5 Utility ......................................................................................... 15 4. Core Mechanism ............................................................................. 16 4.1 Introduction ................................................................................. 16 4.2. Reputation .................................................................................. 16 4.2.1 Subjective Reputation .................................................................. .16 4.2.2 Indirect Reputation ....................................................................... 17 4.2.3 Functional Reputation ................................................................... 18 4.2.4 Combination of Reputation Information for Multiple Functions .................. 18 4.3 Network Entities ........................................................................... 19 4.4 Reputation Table ............................................................................ 19 4.5 The Watchdog Mechanism ................................................................ 19 4.6 Scenarios in Executions .................................................................... 20 VI

PAGE 7

4.6.1 Execution when no Misbehavior is detected ......................................... 20 4.6.2 Execution when Misbehavior is detected ............................................. 21 4.6.3 Request Made by misbehaving node .................................................. 21 4.7 Updates and Distribution .................................................................. 21 4.8 Enforcing Cooperation ..................................................................... 22 4.9 Application of Core to Route Discovery ................................................. 23 4.10 Application of Core to Packet Forwarding ............................................. 24 5. Sprite System ................................................................................. 25 5.1 Introduction ................................................................................. 25 5.2 The Payment Scheme ...................................................................... 26 5.3 Credit for Forwarding Messages ......................................................... 27 5.4 Cheating on Submitting Receipts ......................................................... 27 5.5 Motivating Nodes to Forward Messages ................................................ 27 5.6 Preventing False Receipt. ................................................................. 29 5.7 Message Forwarding ....................................................................... 30 5.7.1 Sending a Message ....................................................................... 31 5.7.2 Receiving a Message .................................................................... .31 5.7.3 Computing Payments .................................................................... 33 6. Corsac Protocol .............................................................................. 34 6.1 Introduction ................................................................................. 34 VII

PAGE 8

6.2 The Routing Protocol ...................................................................... 35 6.2.1 Source Node's Test Signals ............................................................ 35 6.2.2 Intermediate node's test Signals ........................................................ 36 6.2.3 Route Information Forwarding ......................................................... 36 6.2.4 Protocol for the Destination Protocol.. ................................................ 37 6.3 Packet Forwarding .......................................................................... 38 6.3.1 Routing Decision Transmission Phase ................................................. 38 6.3.2 Data Transmission Phase ................................................................ 38 7. Commit Protocol ............................................................................. 40 7.1 Introduction ................................................................................. 40 7.2 Network Model. ............................................................................ 42 7.3 Modeling Routing as a Game ........................................................... .43 7.4 The Goals of Commit Protocol.. ......................................................... 44 7.4.1 Individual Rationality ................................................................... 44 7.4.2 Truthfulness ............................................................................... 44 7.4.3 Energy Efficiency ........................................................................ 44 7.4.4 Limited Message Overhead ........................................................... .45 7.5 The Protocol Functions .................................................................... 45 7.5.1 Winner Determination .................................................................. 45 7.5.2 Payment Computation ................................................................... 45 VIII

PAGE 9

7.5.3 Billing ..................................................................................... 45 7.6 The Pricing Scheme ........................................................................ 46 7.7 The Protocol Specification ............................................................... .48 7. 7.1 Route Discovery .......................................................................... 48 7.7.2 Data Transmission ....................................................................... 49 7.8 Example ..................................................................................... 51 8. Conclusion .................................................................................... 53 References ....................................................................................... 59 IX

PAGE 10

LIST OF FIGURES Figure 2.1 Ambiguous Collisions ....................................................................... 8 2.2 Receiver Collisions .......................................................................... 8 3.1 The Architecture of a Node in the Confidant Protocol.. ............................... 12 5.1 The Architecture of Sprite System ....................................................... 26 5.2lllustration Payment (version 1) .......................................................... 28 5.3 lllustration Payment (version 2) .......................................................... 29 5.4 The Full Version Payment Scheme ....................................................... 30 5.5 The Pseudocode of Sending a Message in Sprite System ............................ 31 5.6 The Pseudocode of Receiving a Message in Sprite System .......................... 32 7.1 Example of Cheating Node Behavior. ................................................. .4 7 7.2 Example of Network Topology .......................................................... 51 X

PAGE 11

LIST OFT ABLES Table 8.1 The Features of the Protocols ............................................................. 55 XI

PAGE 12

1. Introduction The wireless ad hoc network can be defined as a decentralized wireless network. This type is called ad hoc because it does not rely on preexisting infrastructure, such as routers in wired networks or access point in managed wireless networks. In this type of networks the participation of each node in routing is done by forwarding data for other nodes. The first type of wireless ad hoc networks was the "packet radio" networks which were developed in the 1970s. This type of wireless ad hoc networks was sponsored by the Defense Advanced Research Projects Agency. Since the ad hoc wireless networks are decentralized, they can be suitable for applications that do not rely on central points. The decentralized nature of wireless ad hoc networks makes them more scalable that wireless managed networks. Moreover, the minimal configuration and the quick deployment of the ad hoc wireless networks make them suitable for emergency situations such as natural disasters or military conflicts. The dynamic and adaptive routing protocol that these networks have would enable ad hoc networks to be formed quickly. 1

PAGE 13

Based on their application, the wireless ad hoc networks can be classified into three types: Mobile Ad Hoc Networks, Wireless Mesh Networks, and Wireless Sensor Networks 1.1 Mobile Ad Hoc Networks The mobile ad hoc network can be defined as a self-configuring network of mobile nodes connected by wireless links. The node in this type of networks is free to move independently in any direction and changes its links to other nodes frequently. The main challenge in building a mobile ad hoc network is how to provide each node with the information that makes it able to route traffic. The mobile ad hoc networks have become an active research topic sine the 1990s as a result of the growth of laptops and Wi-Fi wireless networks. The mobile ad hoc networks can be divided into three main types: Vehicular Ad Hoc Networks which are used by vehicles to communicate with other vehicles or with roadside equipment, Intelligent Vehicular Ad Hoc Networks which help vehicles to behave intelligently during specific situations such as accidents, and Internet Based Mobile Ad Hoc Networks: In this type of networks the mobile nodes are connected to some fixed Internet-gateway nodes. 2

PAGE 14

1.2 Wireless Mesh Networks The wireless mesh network can be defined as a communication network consists of radio nodes organized in a mesh topology meaning each node in the network may act as an independent router. 1.3 Wireless Sensor Networks The wireless sensor network can be defined as a network consists of autonomous sensors that are spatially distributed to monitor physical or environmental conditions such as temperature, sound, vibration, pressure, motion or pollutants. The wireless sensor networks were developed at the beginning for military applications such as battlefield surveillance. After that, they were applied in some industrial and civilian areas. These applications include industrial process monitoring and control, machine health monitoring, environment and habitat monitoring, healthcare applications, home automation, and traffic control. 1.4 Malice and Selfishness Two types of uncooperative nodes can be identified: faulty/malicious nodes and selfish nodes. The term faulty/malicious nodes means the broad class of nodes that are either faulty and therefore cannot follow a protocol, or are intentionally malicious and try to attack the system. Selfish nodes are economically rational nodes 3

PAGE 15

whose objective is to maximize their own welfare, which is defined as the benefit of their actions minus the cost of their actions. In other words, the misbehavior of a node is considered as a selfish behavior if it aims at obtaining an advantage that can be quantitatively expressed in the units of wireless networking or in a related incentive system. Any other misbehavior of a node is considered to be malicious. 1.5 Encouraging Cooperation among Nodes Because forwarding a message incurs a cost (of energy and other resources) to a node, a selfish node needs incentive in order to forward others' messages. One possibility to provide incentive is to use a reputation system such as the one proposed by Marti et al [8]. In this system, a node monitors the transmission of a neighbor to make sure that the neighbor forwards others' traffic. If the neighbor does not forward others' traffic, it is considered as uncooperative, and this uncooperative reputation is propagated throughout the network. Another possibility to provide incentive is to use credit (or virtual currency) or micro payment. Buttyan and Hubaux [3] proposed a solution of this type in and then presented an improved result based on credit counters in [4]. For both proposals, a node receives one unit of credit for forwarding a message of another node, and such credits are deducted from the sender (or the destination). This thesis surveys recent research on selected aspects of wireless ad hoc networks. 4

PAGE 16

2. Dynamic Source Routing with Watchdog and Path Rater This protocol was presented by S. Marti, T.J. Giuli, K. Lai, and M. Baker in their paper "Mitigating Routing Misbehavior in Mobile Ad Hoc Networks" [8]. 2.1 Introduction The protocol improves the throughput in an ad hoc network when some nodes agree to forward packets, but they fail to do that. In this protocol, the nodes are categorized based on their dynamically measured. The neighbor is a node that within wireless transmission range of another node. The neighborhood consists of all the nodes that are within wireless transmission range of a node. We assume that the communications between the nodes are bidirectional which means if a node B is capable of receiving a message from a node A at timet, then node A could instead have received a message from node Bat timet. We also assume that our wireless network supports promiscuous made operation which means if a node A is within the range of a node B, it can overhear communications to and from B even if those communications do not directly involve A. In this protocol, the route paths are discovered when a source sends a packet to a destination for which the source has no path. Because of that, this protocol is referred to as "on-demand" one. The protocol consists of two main functions: route discovery and route maintenance. 5

PAGE 17

2.2 Route Discovery In this function, when a source node S wants to communicate with a destination node D, then S brings a route discovery by broadcasting a route request packet to all its neighbors. This packet contains the address of the destination node D. Each one of the neighbors that received the route request packet adds its address to it and broadcast it again. This operation continues until the packet reaches the node D. The destination node D sends a route reply packet to the source nodeS to inform it of the discovered route. The D node can either use the reverse path to send its reply or it can initiate a new route discovery to S. There can be many routes from S to D which means S may receive multiple route replies from D. 2.3 Route Maintenance This function takes care of link breaks. The link breaks happen when two nodes in a path are no longer in transmission range. When an intermediate node detects a link break during forwarding a packet to the next node in the route path, it sends back a message to the source notifying it of the link break. In this case, the source tries another path if it has one or it starts the route discovery again if there is no extra path to the destination. Watchdog and path-rater are two techniques used on top of the dynamic source routing protocol in order to detect and discourage any misbehavior. 6

PAGE 18

2.4 Watchdog This technique identifies the misbehaving nodes. Assuming there is a path from node S to D through intermediate nodes A, B, and C. Each node on this path can listen to the transmission made by its neighbors. In other words, when A transmits a packet for B to forward to C, A can tell if B transmits the packet. The watchdog method maintains a buffer of recently sent packets. Each overhead packet is compared with the packet in the buffer. If there is a match, meaning the packet has been forwarded on, the packet in the buffer is removed and forgotten by the watchdog. However, if a packet has been in the buffer for longer than certain timeout, then watchdog classifies the node which are responsible for forwarding the packet as a misbehaving node and sends an alert message to the source node notifying it of this misbehaving node. The main advantage of dynamic source routing protocol with watchdog and path rater techniques is that the misbehavior can be detected early during the forwarding level. However, watchdog technique might not detect the misbehavior in some cases. The following are some cases that make the watchdog technique unable to detect the misbehaving nodes. 2.4.1 Ambiguous Collisions This problem happens when a node cannot hear the transmission of its neighbor on the same path. As it is depicted in Figure 2.1: 7

PAGE 19

1 Figure 2.1: Node A does not hear 8 forward packet 1 to C, because 8's transmission collides at A with packet 2 from the sourceS. [8] A collision between two packets may happen at node A while it is listening to the transmission of node B. In this case, node A cannot decide whether the collision was a result of forwarding the packet by node B or if another node in the neighborhood caused this collision. In order to deal with this problem, node A has to watch node B for a certain amount of time. During this time, if node A could not hear that node B is cooperating by forwarding the packets, then node B is considered as a misbehaving node and A sends a message to the source node notifying it of the misbehavior of node B. 2.4.2 Receiver Collisions The receiver collision happens while node A is listening to node B to know if it sends the packet to node C or not. During this operation, node A hears node B forwarding the packets to node C. However, node A does not know if node C received the packets or not. In Figure 2.2, the packet is not receive because of the collision that happens at node C between packet 1 from node B and packet 2 from node D. 0 ....... l ..... Figure 2.2: Node A believes that 8 has forwarded packet 1 on to C, though C never received the packet due to a collision with packet 2. [8] 8

PAGE 20

2.4.3 False Misbehavior This problem is caused by false report from some node telling that some other node is misbehaving while in fact it is not. Node A for example may send a report to the source node saying that node B is misbehaving node while in fact B is a cooperating node. Based on this report, the source nodes S considers B as misbehaving while A is the real misbehaving node. 2.5 Path Rater This technique avoids routing packets through misbehaving nodes. The path rater technique is applied by each node in the network. The node uses the knowledge of misbehaving nodes which was collected by the watchdog to choose the most reliable path. Every node in the network manages a rating for its neighbors. To this end, a node calculates the path metric by averaging the ratings of all the nodes on the path. This metric is used to compare the reliability of different paths and choose the shortest length path. The path with the highest metric is chosen if more than one path to the destination are discovered. The ratings are assigned to the nodes as follows: A node is given a "neutral" rating of 0.5 when it is discovered by the path rater. Each node gives itself a rating of 1.0. The rating of each node on the chosen path is incremented by 0.01. 9

PAGE 21

Each neutral node cannot be given more than 0.8 as a rating value. The rating value of a node that is connected to a link break is decremented by 0.05. A neutral node cannot be given a negative value. The rating values of the nodes that are not on a chosen path are not modified. 10

PAGE 22

3. Confidant Protocol The results of this chapter were taken from the paper "Performance Analysis of the Confidant Protocol (Cooperation of Nodes-Fairness In Dynamic Ad-Hoc Networks)." By S. Buchegger and J. Y. Le Boudec. [2] 3.1 Introduction: The Confidant protocol uses selective altruism and utilitarianism to make misbehavior unattractive by detecting and isolating misbehaving nodes. The protocol is an extension of source routing protocol for mobile ad-hoc networks. Confidant protocol is based on the following two ideas: First, learning from observed behavior where "neighborhood watch" is employed and nodes are warned by observing what happens to other nodes in the neighborhood. Second, learning from the reported behavior where the nodes in the neighborhood share information about the misbehaving nodes. The nodes also use this information later when they want to forward data packets. 3.2 Components of the Protocol In Confidant protocol, each node has the following components: the monitor, the reputation system, the path manager, and the trust manager. 11

PAGE 23

Reputation System evaluating alarm updating event count threshold xceeded Trust Manager updating ALARM table (ot enoug evidence ............................. I M orutor Path Manager managing path trusted evaluating Figure 3.1: The Architecture of a Node in the Confidant Protocol [2] 3.2.1 The Monitor (Neighborhood Watch) In a wireless ad hoc network, nodes must be able to detect any unusual behavior. In the monitor technique, the node detects any misbehavior by the other nodes in the neighborhood. This detection is done by listening to the transmission of these nodes. The node can also keep a copy of the currently forwarding packet and at the same time listen to the node that should forward this packet. This strategy makes the nodes able to detect any change happens to the contents of the packet. The monitor keeps watching the neighborhood and when misbehavior occurs, the monitor calls the reputation system. 12

PAGE 24

3.2.2 The Trust Manager The main role of the trust manager is to deal with incoming and outgoing alarm messages. The trust manager of a node sends an alarm message to warn the neighbors of misbehaving nodes. The node generates outgoing alarms after having experienced, observed, or received a report of misbehavior. Each node has a list of friends who receive these alarm messages. These incoming alarm messages are filtered according to the trust level of the sender. The following are the components of the trust manager: Alarm Table: Information about the received alarms is stored in this table. Trust Table: The trust levels of nodes in the neighborhood are managed in this table. Friend List: This list contains the friend nodes that the node sends alarm messages to. Trust is important especially when a node making decisions such as providing or accepting information about a new route, accepting a new node as a part of a route, and being a part of a discovered path. 3.2.3 The Reputation System Each node has local rating lists and sometimes black lists. These lists could be exchanged with friends. Each node checks the black list to see if its neighbor is on 13

PAGE 25

this list before sending or accepting any information from it. False accusations can be avoided by using timeout where lists of nodes that have cooperated for a certain amount of time are used. The problem of scalability and how to avoid lists growing too big can also be addressed by using timeout technique. In this protocol, a table contains the neighbor nodes and their rating is managed by the reputation system. The rating of a node is changed if this node has showed a misbehavior many times during a specific period of time. The path manger takes action if the rating falls out of a tolerable range. 3.2.4 The Path Manager The path manager does the following: ranks the paths based to the reputation of the nodes in that path, deletes the paths that contain misbehaving nodes, makes actions on receiving a request for a route from a misbehaving nodes, and makes action on receiving request for a route containing a misbehaving node (these actions could be ignoring the request or alerting the source node). 3.3 Good put In a network with n nodes, the resulting total good put G is the data forwarded to the current destination for each node i and it is defined as: L PacketsReceived G = --------------L Packetsoriginated 14

PAGE 26

3.4 Overhead The total overhead 0 in a network of n nodes is defined as follows: L ALARM 0 = ---------------------L RREQ + RREP + ERROR By using this ratio we can determine how much extra overhead is caused by the Confidant protocol in compare to the overhead when the protocol is not used. Where ALARM are the alarm messages, RREQ are the route request messages, RREP are the route reply messages, ERROR are the error messages. 3.5 Utility Utility can be defined as the ratio of originated to transmitted packets. We assume that c1 is the cost of forwarding a packet, br is the benefit when receiving a message as a destination, b5 when having an own packet received by the destination. Thus the utility u of a node i can be defined as: ui = br # PacketSreceived + bs # PacketSsent_successfully Cr Packets transmitted The utility of a network consists of n nodes is defined as the follows: 15

PAGE 27

4. Collaboration Reputation Mechanism (Core) This mechanism was studied by P. Michiradi and R. Molva in paper [9]. 4.1 Introduction The core implements a mechanism to assess a reputation. This mechanism is used to enforce cooperation among the nodes of a mobile ad hoc network to prevent selfish behavior. In this mechanism, each node keeps track of other nodes' collaboration using a technique based on assessing reputation. The reputation of each node is calculated based on the rating of this node. The rating of a node is increased when it cooperates and it is decreased when it misbehaves. 4.2. Reputation There are three types of reputation in the Core mechanism: subjective reputation, indirect reputation, and functional reputation. 4.2.1 Subjective Reputation Subjective reputation is the reputation that is calculated directly from the observations that the subject node makes. From the point of view of subject Si, a subject's reputation at a time is calculated using a weighted mean of the observations' rating factors which lends relevance to past observations. The past observations are 16

PAGE 28

given more relevance to have sporadic misbehavior in recent observations affect less influence on the evaluation of the final reputation value. False detections can be avoided by watching link breaks and misbehaving nodes. The following formula is used to calculate the subjective reputation: In the above formula, sj is a neighbor of si. ( Sj It) is the subjective reputation value calculated at time t by subject si on subject si with respect to the function f, p(t, tk) is a time dependent function that gives higher relevance to past values of ak, and ak is the rating factor given to the k-th observation. The used scale goes from -1 to + 1 where -1 means that the observed result and the expected result do not match, and + 1 means that the observed result and the expected result match. If either the number or the quality of observations that are collected during a period of time t are not sufficient, then the final value of the subjective reputation is set to 0, which denotes a neutral impression. Since ak E [ -1,1] and p(t, tk) is a normalized value, also E [-1,1]. 4.2.2 Indirect Reputation The indirect reputation of subject Sj collected by si at timet for function f is denoted by Where f denotes the routing or the forwarding function. The 17

PAGE 29

indirect reputation takes only positive values. As a result of that, denial of service attack which usually based on broadcasting negative ratings is prevented. 4.2.3 Functional Reputation The functional reputation can be defined as a subjective and indirect reputation calculated on different functions f each time. A global subject's reputation is added to this type of reputation. The following formula (sj lf(packet forwarding)) for example represents the subject Si evaluating the subject reputation of subject Sj on the packet forwarding function while the formula represents Si evaluating Sj on the routing function. The two resulting values after that are combined together to calculate the global reputation value of the subject Sj. 4.2.4 Combination of Reputation Information for Multiple Functions The following formula is used to combine reputation information: = L wk. + k Where wk is the weight associated to the functional reputation value and is the global reputation value that is calculated in every node. The value of wk must be carefully chosen because it has direct effect on the global reputation value. The operation of packet forwarding has more impact than the operation of routing on the overall performance. However, both operations must be executed. 18

PAGE 30

4.3 Network Entities Each mobile node in the network si has a set of reputation tables and watchdog mechanism which are used to provide collaborative reputation mechanism. The reputation table and watchdog mechanism make each node able to watch and classify the other nodes in the network. The resulting the classification is used to encourage the nodes and obtain a strong cooperation among the nodes in the network. The nodes can be classified into three types: a requester which is a node asking for an execution of a function f, A provider which is a node that executes the function f, and a trusted node which is a node that has positive reputation value. 4.4 Reputation Table The reputation table can be considered as a data structure within each node in the network. In this table, each row represents the reputation values of the nodes in the neighborhood. Each row in this table is divided into four parts: a unique identifier of the node, the subjective reputation values that have been made on the node, the indirect reputation values that are reported by the other nodes in the neighborhood, and the functional reputation values that the node has calculated. 4.5 The Watchdog Mechanism The watchdog mechanism is a technique used by each node to detect misbehaving nodes. When a monitoring node wants to follow the execution of a 19

PAGE 31

function by another node, it runs the watchdog especially to this function and waits for the result. The watchdog does the following: First, it stores the expected result in a temporary buffer maintained in each node. Second, it compares the observed result with the expected result. If they match meaning the function is properly executed, then the expected result is removed from the buffer and the watchdog waits for the next function to be executed. If the function is not correctly executed or if the expected result remains in the buffer for more than a certain fixed time, a negative reputation value is given to the observed node in the reputation table. 4.6 Scenarios in Executions There are two types of entities considered in this protocol: a requester and one or more providers. The requester and the providers must be within the same wireless transmission range. When the protocol is executed, one of the following scenarios occurs. 4.6.1 Execution when no Misbehavior is Detected In this scenario, the requester executes the function f and then it activates the watchdog to watch the execution off. After that, the requester waits for a specific time out. When the result of the watchdog shows that the requested function was correctly executed, then the requestor releases the watchdog. The result of the function execution contains the cooperating nodes that followed the protocol. This 20

PAGE 32

result is used by the requestor to update its reputation table. After that, the requester becomes idle. 4.6.2 Execution when Misbehavior is Detected In this scenario, the requester executes the function f and then it activates the watchdog related to the provider for the required f. After that, the requester waits for a specific time out. The result of the watchdog will be negative because the provider does not cooperate. The reputation of the provider in the reputation table is given negative value. After that, the requester becomes idle. 4.6.3 Request Made by Misbehaving Node When a node receives a request for the execution of a function f, the node first checks the reputation value of the requestor. If the reputation value of the requester is negative, then the node does not execute the requested function. The node also can notify its neighbors of this misbehaving requester. 4.7 Updates and Distribution The following is description of the mechanism used to update and distribute reputation information. There are two times when the reputation tables can be updated: in the request stage and in the replay stage. Only the value of subject reputation may be updated in the former case. If the provider did not cooperate in this stage, the observation is given a negative value and the reputation value of the 21

PAGE 33

provider is decreased. If there is no misbehavior, then reputation values will not be updated. In the latter case, the values of the indirect reputation are the only values that are updated. In this case, the reply message brings reports about the cooperating nodes. These reports cause making the indirect reputation of the cooperating nodes positive. Because of a possible attack, only positive rating factors can be distributed among the nodes while the negative rating factors are evaluated locally. Giving negative rates makes it easy for misbehaving nodes to distribute false information and create denial for service attack [7]. If a node is idle for most of the time except when it has to communicate, its reputation gets decreased, even if it cooperates during the other times. 4.8 Enforcing Cooperation Next we explain how reputation is used to enforce cooperation among nodes. The reputation reflects the cooperative behavior of nodes where the negative reputation causes classifying the node as a misbehaving node and the positive reputation causes tagging the node as a cooperating node. Moreover, the execution of a function that is requested by any requestor depends on the reputation value of the provider in the reputation table. The execution of the function is denied if this reputation value is negative. It is hard for a node to build a good reputation because getting a positive rating requires receiving reply message which contains all the nodes 22

PAGE 34

that cooperated to correctly execute the requested function. However, a node is given negative reputation value each time the watchdog gives a negative result. 4.9 Application of Core to Route Discovery We want any node in an ad hoc network to discover a route to any other node in the ad hoc network. This discovery can be done directly when the two nodes are within the same wireless transmission range or it can be done through one or more intermediate nodes. The node initiates a route discovery by broadcasting a route request message which can be received only by the nodes within the transmission range. The intermediate nodes that receive a route request message append their addresses to this message broadcast it again. When the route discovery is successful, the source node receives a route reply message with a sequence of nodes that it can reach the destination through. We can define the Core protocol as a layer on top of the dynamic source routing protocol. The misbehaving nodes that do not participate during the route discovery are detected by the watchdog mechanism. This detection happens during the request phase of route discovery. During the reply phase the source and the intermediate nodes are informed of the nodes that participated in route discovery. Base on this information the reputation values of the nodes are updated. Each node uses the reputation table to classify other nodes it receives information about. While the route requests that originated by cooperating nodes are properly serviced, the route requests of the misbehaving nodes are denied. In order to change 23

PAGE 35

its reputation value from negative to positive, a node has to be cooperative. The nodes that want to be serviced when they need to communicate have to participate in route discovery. 4.10 Application of Core to Packet Forwarding When the node finds a path from the source to the destination to the destination, it starts sending its packets through this path. The intermediate nodes on the path perform the packet forwarding by transferring the packets. The misbehaving nodes that refuse to forward the packets are detected by the watchdog. While the misbehavior of the nodes is detected in the request phase of packet forwarding, the source and the intermediate nodes are informed of the cooperating nodes that participate in packet forwarding during the reply phase. The reputation values in the reputation table are updated based on the cooperation of the nodes. This information is used later by the node to classify other nodes. Any cooperating node can execute the packet forwarding while the misbehaving nodes cannot do so. Cooperation is the only way for a node to change its reputation from negative to positive. Nodes have to participate in packet forwarding if they want their data packets to be forwarded later. 24

PAGE 36

5. Cheat-Proof, Credit-Based System This simple, cheat-proof, credit-based system (Sprite) was proposed by S. Zhong, Y. R. Yang, and J. Chen [10]. 5.1 Introduction As it can be seen in Figure 5.1, The Sprite system consists of the credit clearance service and a collection of mobile nodes. The nodes in this system send and receive messages through a wireless network. The sender node knows the full path to the destination of its packets. Since forwarding the packets costs the intermediate nodes some of their resources, the sender pays with credit to the network each time it sends something. When an intermediate node forwards packets for other nodes, it get some credit and so it can send its packets later. The node has to report to the credit clearance service the messages that it has forwarded. The main goals of the payment scheme are to thwart cheating actions and to afford incentive that encourages nodes to cooperate and forward each other's packets. The system does not require the total charge to the sender to be equal to the credit received by the intermediate nodes. In order to prevent cheating, credit clearance service charges the sender more than what it gives to the intermediate nodes. 25

PAGE 37

Credit Clearance Service Wide-Area Wireless Network I Node I I I Node 31 I Node21 Figure 5.1: The Architecture of Sprite System [10] 5.2 The Payment Scheme Only the sender is charged in this system. This can be explained as the follows: charging the destination can cause a Denial-of-Service attack on the destination where other nodes may send a large amount data. Sharing the cost between the sender and the destination still has the same problem where the sender may make agreement with the intermediate nodes and they can secretly return the payment the sender made back. However, if only the sender is charged, a node is discouraged sending useless messages. If the destination pays for the received messages, then the sender can get compensation from the destination. This compensation can be done in the application layer by the execution of the payment protocol. 26

PAGE 38

5.3 Credit for Forwarding Messages The amount of credit that a node receives depends on whether or not the forwarding action was successful. Forwarding is successful if and only if the message is received by the next node on the path. The credit clearance service decides that the node has forwarded the message if it received a valid receipt from the successor of that node. 5.4 Cheating in Submitting Receipts Because the mobile nodes could be selfish, they may choose not to forward others' messages or they may try some cheating actions if these actions could improve their resources. A selfish node may adopt one of the following cheatings: The node receives the message but it does not report the receipt. The message could also save the receipt but not forwarding the message. Another selfish action happens when the node falsely claims that it has received the message while it has not received the message. 5.5 Motivating Nodes to Forward Messages The credit clearance service gives more credit to the cooperating nodes that forward packets in order to motivate all the nodes to cooperate while misbehaving nodes are not given any credit. The credit clearance service works as follows: it determines the last node on the path that has received a packet. After that, the credit 27

PAGE 39

clearance service enforces the sender to pay f3 to this node and to pay a to each of the predecessors of this node where f3 < a. The successor of the last node on the path does not get any payment. As it can be seen in Figure 5.2, Because only the first three intermediate nodes submit their receipts, they are the only nodes that receive payments while nodes 1 and 2 get a payment of a for each. Node 3 gets a payment of f3. Node 4 and the destination do not receive any credit because they do not submit any receipt. The total amount that the sender pays is 2a + f3. Figure 5.2: Illustration of Payment (Version 1) [10] There is a probability of a collusion that can work against the above design if the last node (or the last K nodes) that received the message collude with the sender. The last node may do not report its receipt which caused the sender to save amount of a credit and at the same time the last node will lose an amount of f3. The sender may give an amount of f3 + E to the last node where E > 0. In this case, the last node will be better-off and the sender get an amount of a -( f3 + E ) In conclusion, the colluding group gets an amount of a -f3. The credit clearance service charges the sender an extra amount of credit if the destination node did not report its receipt. This strategy helps preventing this cheating action. The extra charge is given to credit 28

PAGE 40

clearance service itself rather than to any node. In this case, the colluding group will not be able to benefit from this cheating acfion. Figure 5.3 shows the revised amount that the sender pays, which is ( 4a + fJ)2{3. Figure 5.3: Illustration of Payment (Version 2) [10] 5.6 Preventing False Receipts The nodes submit receipts instead of full messages in order to save bandwidth and storage. In the presence of such a scheme for receipts, some nodes can try to cheat the system in different ways. A node may forward only the receipt and not forwarding the rest of the message. In addition, an intermediate node may wait until it has a fast connection to forward the false receipt in order to save its resources. Ways to prevent such attack depend on how the destination behaves. There are two considered cases. First, when there is a colluding between the destination and the intermediate nodes and second, there is no such colluding. In the first case, the destination submits a receipt of a message even the whole message is not received. To deal with this case, the intermediate nodes and the destination must pay for the message because the message is sending for the destination and the destination submitted a receipt for the message conforming that it has received the message. In the second case, the 29

PAGE 41

destination does not collude with the intermediate nodes and the intermediate nodes forward only the receipt of message instead of the whole message, therefore the destination does not receive the message. Based on the above scenario, the receipt will not be sent. This cheating action can be prevented by reducing the amount of credit given to the intermediate nodes if the destination does not report that it has received the message. By using this reduction of credit, the cheating nodes cannot get enough credit even to forward their receipts. In other words, the credit paid to each node is multiplied by y if the destination does not send a receipt conforming the receiving of the message when y < 1. Figure 5.4 shows the amount of credit that each node receives. The charge to the sender is reduced by y{3 instead of {3 for the nodes that do not send their receipts. Figure 5.4: The Full Version Payment Scheme [10] 5.7 Message Forwarding A public/private key pair of node ni is presented by ( PKi,SKi ). Sequence number matrix Seqi is maintained by each node ni where SeqiU, k) is the sequence number of message from sender nj to destination nk, observed by node ni. 30

PAGE 42

(sign5k( ), veri[Ypk( )) represents the digital signature that is attached with each message. 5.7.1 Sending a Message Assuming that node n0 wants to send message m that has sequence number seq0(0, d) to the destination node nd, through the path P. The signature, S, on (MD(m), P, seq0(0, d)) is computed by node n0 first where MD() is a message digest function. After that, n0 forwards the message (m, P, seq0(0, d), S) to the next node and increases the sequence numberseq0(0, d). The following is the pseudocode of sending a message: t:.m is the message payload. t:.n0 is the sender, nd the destination, and P the path. S +--sign5 K0(Md(m),P,seq0(0,d) Send (m, P, seq0(0, d), S) to the next node. seq0(0, d)++ 5.5 The Pseudocode of Sending a Message in Sprite System [10] 5.7.2 Receiving a Message When the node ni receives the message (m, P, seq, S), It first checks if the following three conditions are satisfied: the node ni is on the path, the sequence 31

PAGE 43

number of the message is greater than seqi(O, d), and the signature of the message is valid. If the conditions are satisfied, then the node ni saves message (M D(m), P, seq, S) as a receipt and forwards the message (m, P, seq, S) to the next node ifni is not the final destination of this message. If any of the conditions is not satisfied, then the message will be dropped. The following is the pseudocode of receiving a message: ll (m, P, seq, S) is the received message. ll 50 is the sender, nd the destination. if ((ni not in P) II (seq seqi(O,d)ll (verifYPKo((MD(m),P,seq),S) *TRUE)) drop the message else seqi(O, d) +-seq save (MD(m), P, seq, S) as a receipt if (ni is not the destination and decides to forward) send (m, P, seq, S) to next hop else drop the message. 5.5 The Pseudocode of Receiving a Message in Sprite System [10] 32

PAGE 44

5.7.3 Computing Payments The receipt (D, P, seq, S) is considered as valid if the following condition is satisfied: verifYPKo ( (D, P, seq), S) = TRUE. PK0 represents the public key of the sender. P = (n0 nv ... ne, ... nd) is the path that was used to send the packets. ne represents the last node on the path P that has submitted a valid receipt. Using these factors, the credit clearance service calculates the charge C that the node n0 pays, and the payment Pi that is given to each node ni as the follows: C = (d-l)a + f3-(d-e)yfl { a if i < e = d f3 if i = e = d pi = yfl if i < e < d yfl if i = e < d 33

PAGE 45

6. Cooperation-Optimal Routing and Forwarding Protocol (Corsac) The Corsac protocol was introduced by S. Zhong, L. E. Li, Y. G. Liu, and Y. R. Yang in their paper "On Designing Incentive-Compatible Routing and Forwarding Protocols in Wireless Ad-Hoc Networks." [ 11] 6.1 Introduction We refer to this protocol as a cooperation-optimal protocol for wireless ad-hoc networks with non-cooperative selfish nodes. In this protocol, there are two stages in which routing and forwarding occur in a node. These stages are the routing stage and the forwarding stage. In the routing stage, the routing decision is made by the nodes' actions. The routing decision consists of the forwarding actions of all nodes. These actions specify what each node supposed to do in the forwarding stage. In the forwarding stage, the node's utility is decided by the routing decision (what each node is supposed to do in this stage) and the nodes' forwarding actions (what each node really does in this stage). We assume that ai = (afr), aY)), where ar) is the node i's subaction in the routing stage, and aY) is i's subaction in the forwarding stage. We also assume that a denotes the actions of all nodes, aCr) denotes the routing subactions of all nodes, and aCt) denotes the subactions of all nodes during the packet forwarding. The routing 34

PAGE 46

decision R is defined as R = R(a
PAGE 47

The source nodeS picks a random number r0 Assuming that H is a cryptographic hash function, S uses the number of bocks in the session to computer= HfM/bl(r0). A message of the form (TESTSIGNAL, [S, D, r], [S, hi]) is sent by the node i at power levell where h1 indicates the encryption of [S, D, r, l, a5]. The key ks,D is used for the encryption. 6.2.2 Intermediate Node's Test Signals When an intermediate node i receives message of the form (TESTSIGNAL, [S, D, r], [P, h]) from a neighbor node, the following happens: A message of the form (ROUTEINFO, [S, D, r], [P, i, h']) is sent by the node i at power level Pctr The key ki,o is used to compute h' and protected by the message authentication code. In the case that the TESTSIGNA message is the first one that node i receives for the session (S, D, r), then i sends message of the form (TESTSIGNAL, [S, D, r], [i, hi]) where hi includes the encryption of [S, D, r, l, aiJ. 6.2.3 Route Information Forwarding When an intermediate node j receives message of the form (ROUTEINFO, [S, D, r]. [P, i, h]), the following happens: 36

PAGE 48

In the case this ROUTEINFO message is new for the node j, then node j uses the power level Pctr t send to send a message of the form (ROUTEINFO, [S, D, r], [P, i, h]). 6.2.4 Protocol for the Destination Node A cost matrix for each session (S, D, r) is maintained by the destination node D. This matrix contains the power levels and the costs of energy. When D receives message of the form (TESTSIGNAL, [S, D, r], h) from node P, it first decrypts h, and then uses the key kp,0to verify the MAC. After that, D saves the power level and the cost of energy in the cost matrix. When D receives message of the form (ROUTEINFO, [S, D, r], [P, i, h]), from node P, it first decrypts h, and then uses the key kp,0to verify the MAC. After that, D saves the power level and the cost of energy in the cost matrix. After D collects all the information about the link cost, it makes sure that the energy cost is not change. After that, the minimum power level for each link is chosen. Finally, D uses Dijkstra's algorithm to compute the lowest cost path from S to D. The computed lowest cost path is denoted by LCP(S, D) which is also the chosen path that is used to forward packets. The lowest cost path without node i is denoted by LCP(S, D; -i). The payment for one data packet to node i is defined as the follows: 37

PAGE 49

Pi = cost(LCP(S, D, -i))cost(LCP(S, D)-{i}) 6.3 Packet Forwarding The packet forwarding protocol consists of two sub-protocols: 6.3.1 Routing Decision Transmission Phase After the node D finishes the routing discovery phase, it sends message of the form ([S, D, r], LCP(S, D), P5 ((Pi,Pi) I i is an intermediate node on LCP(S, D)}). A digital signature is sent with the routing decision message along the reversed path of LCP(S, D). Pi denotes the power level that node i uses to forward data packets, and Pi denotes the unit payment node i receives. The routing decision is forwarded by each intermediate node at a power level that can reach the path LCP(S, D). 6.3.2 Data Transmission Phase After it receives the routing decision, the source nodeS makes sure that the digital signature is valid. After that, Senters the data transmission phase. In the data transmission, the source S sends data packets at the power level P5 while the intermediate nodes send data packets at the power level Pi. These power levels were computed in the routing decision. S sends out data packets in blocks where each block contains b packets. The sourceS sends out r[M/bl-m = HfM/bl-m(r0 ) with the last data packet in the m-th block. The source node S waits for a confirmation before 38

PAGE 50

sending the next block. The intermediate nodes forward the block of packets that sent by the source nodeS along the LCP(S, D) to the destination node D. The intermediate nodes finish sending the block and then they wait for a confirmation before they start forwarding the next block. After the destination D receives all the packets in a block, it decrypts r[M/bl-m and then it sends rrM/bl-m in clear-text back along LCP(S, D), as a confirmation of this block. After the intermediate nodes receive the confirmation of the m-th block, they verify that the condition r = Hm(rrM/bl-m) is satisfied. The intermediate nodes forward the confirmation using the path LCP(S, D). After the source nodeS receives the confirmation of one block, it starts sending the next block. The confirmation rrM/bl-m is sent by each intermediate node j the system in order to get a payment of Pj. b. m. 39

PAGE 51

7. Sender-Centric Truthful and Energy-Efficient Routing Protocol (Commit) The information of this chapter was taken from the paper which was presented to the International Parallel and Distributed Processing Symposium (IPDPS) by S. Eidenbenz, G. Resta, and P. Santi. [6] 7.1 Introduction This protocol considers the problem of establishing a route between source and destination, and sending packets through this route in ad hoc network with selfish nodes. There are side payments made to the forwarding nodes. These payments are used to motivate the nodes to follow the protocol specifications. In this protocol, nodes are supposed to participate in the protocol execution and follow the protocol specification. The messages must be routed along the most energy efficient path. This protocol is the first individually rational, truthful, and energy-efficient routing in ad hoc networks. In this protocol, a wireless network is considered. This network is used to access a specific service such as internet access. The nodes in this network do not have to be directly connected to the base station. Instead they can use other nodes as intermediate nodes in order to connect the base station. The customer who wants to be connected to the service will be called sender. The intermediate wireless nodes will be called relays, and the service provider will be called the destination. The intermediate nodes should be motivated to be cooperating and forward the packets of 40

PAGE 52

other nodes to make the network works successfully. The Ad HocVCG protocol which is mentioned in [ 1] is used to discover the route that will be used to send or receive the packets. The process of routing discovery is started by the sender node broadcasting the destination that it wants to send packets to. If there is any path to this destination, the sender receives a message indicating the path P and the cost of sending the packets through this path. The price that the sender pays to send its packets is distributed among the intermediate nodes. Each intermediate node receives that amount that makes it able to forward the packet. Both the sender and the destination must act truthfully in this protocol. The sender cannot withdraw the connection request after starting the route discovery phase. The reason of this restriction is that if the intermediate nodes in the path P would not be sure that they will be paid, they will1ose the incentive that encourages them to cooperate later in the route discovery phase. The basic idea of this protocol is used by the website PRICELINE. COM [12]. In this website, the customers provide the maximum amount of money they can pa.Y for a certain service such as a hotel reservation or a flight ticket. The request is automatically accepted, and the transaction takes place if there is a service available at the provided amount of money. The same thing happens in the scenario described above. The customers who want to access the service issues a connection request. In this request, the customers state the maximum amount of money they will pay for this 41

PAGE 53

service. A full commitment of the customer is represented by the connection requestthat is the reason why this protocol is called Commit protocol. The customer pays the corresponding amount if there is a connection can be made at cost less than what the customer proposed. The customers in this strategy can always control the amount they pay for exchanging the packets. The truthful in this protocol means that the nodes should always follow the specifications of the protocol. Individual rationality means that it is rational for the selfish node to cooperate during the execution of the protocol. 7.2 Network Model In this model, an ad hoc network consists of n nodes is considered. The communication graph G represents the links between the nodes in the network. The links are considered to be symmetric which means an edge between nodes v and w appears in G if and only if vis within w's transmitting rang, and w is within v's transmitting rang. The graph G is 2-connected which means from any node to the destination there are at least two node-disjoint paths. The nodes execute a topology control protocol to establish the communication graph. By the end of this execution, every node v will determine its transmitting rang Tv Tva is the power required to achieve a transmitting range Tv, where a is constant between 1 and 6. In order to update Vr, the topology control protocol is executed periodically. However, the same 42

PAGE 54

transmitting range rv is applied in the period of time between consecutive topology checks. 7.3 Modeling Routing as a Game The process of establishing a route between a source and a destination node is modeled as a game. In this game, a node can play only one role: source, relay, or destination. S denotes the sender, v or vi denotes an arbitrary relay node, and D denotes the destination. The destination node is neutral referee rather than an actually part of the game. It computes the minimum energy (S, D) path and the payments for the source and the intermediate nodes. The goal of this model is routing a path between the sender and the destination and then using this path to send packets in both directions. During the data session, the sender is charged for sending and receiving packets. The utility of playerS can be written as follows: u5 = m-c5(D) where m is the maximum per-packet price that Scan pay and c5(D) is the actual per packet price that S pays. If a node v took place in the data session, then its utility can be written as the follows: Uv = pay(v)-l(v) where pay(v) is the payment that v receives for forwarding each of the packets of the source node S. 43

PAGE 55

7.4 The Goals of Commit Protocol Commit is a protocol for incentive compatible and energy-efficient routing in ad hoc networks, and it has the following design goals: 7.4.1 Individual Rationality This property is satisfied if the node that is included in the protocol does not get a negative value for its utility. The goal of this property is to encourage the nodes to participate in the protocol. 7 .4.2 Truthfulness As described above, truthfulness is the strategy in which the nodes follow the protocol specification. In this strategy, the nodes declare their true type and send/relay the messages as prescribed. 7 .4.3 Energy Efficiency If there is a feasible communication between S and D, it must take place along the minimum energy cost path. The cost of energy for the path P can be defined as LveP,VE(S.D} l(v). As we mentioned before, energy efficiency is a key property in the ad hoc networks because the nodes in these networks are battery operated. 44

PAGE 56

7 .4.4 Limited Message Overhead One of the important goals of this protocol is minimizing the number of exchanged messages during the forwarding stage. 7.5 The Protocol Functions The designed protocol must be able to perform the following tasks: 7.5.1 Winner Determination If there is a winning path, it must be determined along with the communication that must be established. 7.5.2 Payment Computation If there is a winning path, then the price that S must pay for transmitting/receiving the packets and the payments for the intermediate nodes on this path must be determined. 7.5.3 Billing After the communication is done, the source node S must be charged and the intermediate nodes must be paid based on the computed prices. The destination node D performs winner determination and payment computation based on the information that it collected from the nodes. Billing is done 45

PAGE 57

by starting the data session. The payment method used in the Commit protocol can be defined as a distributed reverse second-price single item auction with reverse price where the senderS can be considered as the auctioneer that wishes to buy an item (the path from S to the D) at a maximum price ofm (the reverse price). The relay nodes can be considered as sellers. The reverse auction is second-price because the price that the sender pays to the winning group (the intermediate nodes) depends on the second best given offer. 7.6 The Pricing Scheme The following factors are defined and used to compute the winning path and the payments of the nodes: Cp denotes the energy cost of an arbitrary path from S to D (S, D)-path P. Where Cp = LveP,vE{S,D} l(V). The winning path can be defined as the path of minimum energy cost and it is represented by M P. For any node in the winning path, c(P-v) denotes the cost of the minimum energy (S, D)-path p-v that does not include this node v. We can define the payment for node v in the winning path MP as follows: pay(v) = c(P-v)-c(MP) + l(v). The trivial definition of the price that Spays for sending the packets along MP is c5(D) = LveMP,vE{S,o}Pay(v). However, this definition leaves space for a misbehavior to the nodes in M P. Because of the presence of the reverse price m, these nodes could declare a false type in order to make the c5(D) price less than m. 46

PAGE 58

In the example in Figure 7.1, the sender wants to pay at most 56 for each packet to be sent to the destination. Vz Figure 7.1: Example of Cheating Node Behavior if C5(D) is defined as Cs(D) = LveMP,vE(S,D}pay(v) [6] In the case that all the nodes declare their true types, the communication cannot be made because of the following: Since M P = { v11 v2 v3}, c(MP) = 26, c(p-vl) = c(P-v2 ) = c(p-v3) = 40, pay(v1 ) = 4026 + 5 = 19, pay(v2 ) = 4026 + 20 = 34, pay(v3 ) = 4026 + 1 = 15. The total payment is 68 which is above what the sender will pay (65), so the connection would not take place. Let us assume that the node v2 gives a false power level which is 30. The payments will be as the follows: pay(v1 ) = 4036 + 5 = 9, pay(v2 ) = 4036 + 30 = 34, pay(v3 ) = 4036 + 1 = 5. The total payment will be 48 which is below the payment that the sender proposes, so the communication takes place. In this case, 47

PAGE 59

defining c 5 (D) = LveMP,vE{S,D}pay(v) leads to not-truthful mechanism. To avoid this problem, we set c 5(D) = c(p-MP) where c(p-MP) is the cost of the minimum energy path that does not contain any of the nodes in M P. This path is called the global replacement path. With this new definition of c5(D), any false declaration from the nodes in M P will not affect c5(D) and the truthfulness of the mechanism is not impaired. The winning path M P is defined as feasible if c5(D) < m. The connection cannot be made if this condition is not satisfied. In general, the amount that is charged to the sender and the total amount that is given to the intermediate nodes are not equal. In other words, c(p-MP) =f:. LveMP,vE{S,o}Pay(v). In this case, it is said that the budget is imbalanced. The destination node D is responsible for making this balance. D gets the additional amount if c(p-MP) < LveMP,ve{s,o) pay(v), or it pays the difference if c(p-MP) > LveMP,vE{S,D} pay(v). 7.8 The Protocol Specification The Commit protocol can be divided into two stages: 7.8.1 Route Discovery In this stage, a limited flooding process computes the communication graph while the destination node D computes the winning path M P and the payments. After that, D sends the resulting path and the payments to the source nodeS. 48

PAGE 60

7.8.2 Data Transmission The senderS sends or receives the data packets and the payments along the winning path from the destination node D. This operation continues until the sender S ends the connection or until the topology is updated. First, S sends a route discovery message of the form RD(S, D, m) using power l(v). In this message, S declares that it wants to start a data transmission session to the destination node D. S indicates also the maximum amount which is m that it can pay for each data packet to be sent to the destination. Each intermediate node vk receives a message of the form RD(S, D, m, v11 l(v1), ... vK-v l(vK_1)). Vv ... vK-1 represents the path between the senderS and the node vK_1.mLr=-/l(vd represents the difference between the amount that S provides and the total cost of the path when vK receives the message. When the node vk receives messages, it builds up a local view of communication graph. Every time it receives information about the existence of an edge that it does not know about before, it adds this information to its local view. After that, vK appends the fields vK and l(vK) to the message that contains the new information and then it forwards this message with power l ( vK) to the next node on the path. The node vK cryptographically signs the two fields vK and l( vK) to prevent other nodes from altering them. Node vK also signs the field vK_1 to ensure that there is an edge between vK_1 and vK. The destination node D receives RD messages from all nodes on the path. After receiving all information, D does the following: 49

PAGE 61

Computes the minimum energy path MP = {S, v11 ... vK, D} from S to D. Computes the replacement path p-vi for each intermediate node vi in the minimum energy path. Computes the global replacement path p-MP. Computes the payment/premiums for S and the nodes in M P and checks if the condition c 5(D) = c(p-MP) < m is satisfied. Sends back the winning path, the payments, and the global replacement path to S using the reverse of the M P path. Cryptographically signs the messages to prevent the intermediate nodes from manipulating the payments. S uses the global replacement path to send a test packet In this packet, S asks each intermediate node v to sign its two neighbors. Finally, D sends a packet through the reverse M P path to S. In this packet, D tells S that it is ready to receive the packets so S can start sending its packets. The data transmission phase starts with S sending its data packets to D using the computed path. The payments of the intermediate nodes are included with the sent packets. The intermediate nodes forward the data packets and collect the payments at the same time. The data transmission phase terminates if one of the following two cases happened. First, if the source node S has completed sending its packets. Second, if the network topology is 50

PAGE 62

changed. If the second case happened, then S has to start the route discovery phase from the beginning. 7.7 Example To clarify the pricing scheme, we present the following example: Vs Figure 7.2: Example of Network Topology [6] In this example, the intermediate nodes are labeled with their power levels (types). The sender proposes a price of 100 to send its packets to the destination. The communication should take place via the path with minimum energy (the path with bold edges). 51

PAGE 63

The senderS wants to pay at most 100 units to connect the destination node D. The minimum energy path M P, the replacement path for each node on M P, and the global replacement path p-MP are computed by D where: MP == {v11 v3 v9 } c(MP) == 26 Since the computed price that S must pay c(p-MP) == 56 is less than the proposed price (100), then the minimum energy path M P is feasible. The following are the payments for the intermediate nodes on the in the chosen path: pay(v1 ) == c(P-v1)c(MP) + l(v1 ) == 31-26 + 5 == 10 pay(v3 ) == c(P-v3)c(MP) + l(v3 ) ==5526 + 20 == 49 pay(v9 ) == c(P-v9)-c(MP) + l(v9 ) = 3026 + 1 = 5 Since the total payment is 64 and S pays only 56 units, then the destination node D pays the remaining amount which is 8 units. 52

PAGE 64

8. Conclusion In this thesis, recent research on selected aspects of wireless ad hoc networks has been surveyed. The protocols and techniques that we presented in this thesis showed how the performance of the ad hoc network can be improved. The watchdog and path rater technique for example increase the throughput by 17% in a network with moderate mobility. During extreme mobility, the throughput is increased by 27%. The watchdog and pathrater technique also increase the percentage of overhead transmission from 9% to 17% in moderate mobility and from 12% to 24% in extreme mobility. Some protocols were simulated. For example, the authors of the Confidant protocol used the mobile ad-hoc simulator GloMoSim to simulate their protocol. The area of the simulation was 1000 m X 1000 m which presents the center of a town. The speed was between 0 and 20 mjs and the radio range was 250m. The sending capacity of the simulation was 2 M bps and the size of each packet was 64 B. The simulation was run for 900 s. The simulation results showed a significant improvement in the good put when the Confidant protocol is applied. Even with a 53

PAGE 65

fraction of misbehaving nodes as high as 60% the protocol is scalable in terms of the total number of nodes in a network and performs well. The Sprite system was evaluated using the library Crypto + +4.0. The mobile node that was used in the evaluation was a laptop with an Intel III processor at 866 MHz with Windows XP operating system. The length of a message payload was 1000 bytes. The evaluation showed that the overhead of the system was significant. It also showed that the nodes would cooperate and forward each other's messages unless their resources are extremely low. Corsac protocol was also implemented using the GloMoSim package. In this implementation, the nodes were distributed in an area of 2000 by 2000 meters. Each node had two transmission power levels at 7 and 14 dBm. The a value of each node is 1. The time interval between two sessions from the same node was set to 60 seconds. The number of packets in each session was between 1 and 10 and the size of each packet was 1024 bytes. The implementation showed that the Corsac protocol was providing incentives for nodes to forward packets in a manner that improves network's performance. 54

PAGE 66

The following table shows the features of the protocols that we have studied in this thesis. The Protocol Dynamic Source Protocol with Watchdog and Path Rater Confidant Protocol Core Mechanism Sprite System Table 8.1 The Features of the Protocols The Description The node in this protocol is always busy watching the other nodes in the neighborhood. This operation costs the node to spend its resources even while it is not forwarding packets. This protocol can be classified as an expensive protocol in terms of resources. The node in this protocol applies many systems in order to watch the behavior of the other nodes in the neighborhood. These systems work all the time to collect information about any misbehavior and to use this information later to route data through the cooperating nodes and ignore routing through the misbehaving nodes. Moreover, the node in this protocol sends alarm and notification messages each time it detects some misbehavior. All the above operations make the protocol a secure but at the same time they require the node to spend a lot of resources in order to done these operations. In this mechanism the node watches the nodes m the neighborhood and calculates their reputation all the time. In addition, the node sends messages to its neighbors each time it detects any misbehavior to notify them of the misbehaving node. This work makes the mechanism reliable and secure for sending the data but at the same time it requires the nodes to spend a big amount from their resources to obtain these reliability and security. This system adopts the strategy of charging the sender and paying the intermediate nodes. This strategy encourages the intermediate nodes to forward the packets of the other nodes because this forwarding gives them more credit. Moreover, the system prevents the nodes from sending useless messages because they have to pay for any message they send. The node in this system is given a credit for the amount of resources it 55

PAGE 67

spends for forwarding the packets of the other nodes. Even the source node that pays for sending its own packets will be given credit when it plays the role of an intermediate node. This protocol consists of two stages, the routing stage and the forwarding stage. The source node starts the communication by indicating the destination that it wants to send data to. The intermediate nodes on the path between the source and the destination forward the communication request until it reaches the destination node. The destination node computes the path Corsac Algorithm from the source to the destination, the cost of this path, and the payment that should be given to each intermediate node on the path. It can be noticed that only the nodes on the path between the source and the destination participate during the communication. The protocol encourages the intermediate nodes to forward the packets of the other nodes by giving them a payment for each packet they forward. Commit Protocol As in the previous protocol, the source node sends a request to communicate with the destination node. When the destination node receives the request through the intermediate nodes, it computes the minimum energy path from the source to the destination and the payments for the intermediate nodes on this path. The source node start sending its packets through the computed path and it also sends the payments to the intermediate nodes through the same path. Only the nodes that are on the path participate by forwarding the packets and they are given payments for this cooperation. Recommendations regarding applicability of these protocols need to take into account the following properties of the protocols: the first three protocols that used the reputation of the nodes to rout and forward data cost the nodes a lot of resources. The nodes it these protocols return the favorite by forwarding the packets of the cooperating nodes while they deny serving the misbehaving nodes. However, the last 56

PAGE 68

three protocols do not require the nodes that are not on the chosen path to do any activity. They also apply giving payments to the nodes on the path that forward the data packets so the nodes are always encouraged to forward the packet of the other nodes. In terms of evaluation and relative usefulness of the considered protocols, I rank them as the follows, from most useful to least useful: 1Payment Based Protocols: a. Sprite System b. Commit Protocol c. Corsac Algorithm 2Reputation Based Protocols: a. Dynamic Routing Source Protocol with Watchdog and Path Rater b. Core Mechanism c. Confidant Protocol The first three protocols took their positions based on the strategy they belong to which is the strategy of giving payment to the cooperation nodes. By using this strategy the nodes do not need to participate unless they are part of a chosen path so they spend their energy only when they are forwarding packets. 57

PAGE 69

On the other hand, the last three protocols deserved their positions also based on the strategy they belong to which is the strategy of watching the neighbors all the time. In this strategy the nodes are always spending their energy watching the other nodes in the neighborhood even when they are not part of a chosen path and they are not forwarding packets. Within each group, the protocols are evaluated based on their simplicity, from the simplest to the more complex. 58

PAGE 70

References 1. L. Anderegg and S. Eidenbenz. Ad-hoc VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In ACM MobiCom, San Diego, September 2003. 2. S. Buchegger and J. Y. Le Boudec, Performance analysis of the CONFIDANT Protocol (Cooperation of Nodes-Fairness In Dynamic Ad-Hoc Networks).ln Proceeding of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Lausanne, Switzerland, June 2002. 3. L. Buttyan and J.-P. Hubaux. Enforcing service availability in mobile ad hoc W ANs. In Proceeding of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ), Boston, MA, USA, August 2000. 4. L. Buttyan and J.-P. Hubaux. Simulating cooperation in self-organizing mobile ad hoc networks. In ACM/Kluwer Mobile Networks and Applications (MONET) Special Issue on Mobile Ad Hoc Networks, volume 8, October 2003. 5. Richard Dawkins. The Selfish Gene. Oxford University Press, 1989 edition, 1976. 6. S. Eidenbenz, G. Resta, and P. Santi, Commit: A sender-centric truthful and energy-efficient routing protocol for ad hoc networks with selfish nodes. International Parallel and Distributed Processing Symposium (IPDPS), 13, 2005. 7. Lei Guang and Chadi Assi. Cross-Layer Cooperation to Handle MACMisbehavior in Ad Hoc Networks. Concordia Institute for Information System Engineering, Concordia University, Montr'eal, Qu 'ebec, Canada, 2006. 8. S. Marti, T.J. Giuli, K. Lai, and M. Baker, Mitigating routing misbehavior in mobile ad hoc networks, In Proceeding of the ACM Conference on Mobile Computing and Networking (MobiCom), Boston, Massachusetts, USA, 2000. 59

PAGE 71

9. P. Michiradi and R. Molva, Core: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks. In Proceedings of the 6'h IFIP Communications and Multimedia Security Conference, Portoroz, Slovenia, Sep. 2002. 10. S. Zhong, Y. R. Yang, and J. Chen. Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks. In Proceeding of the IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, USA, March April2003. 11. S. Zhong, L. E. Li, Y. G. Liu, andY. R. Yang, On designing incentive compatible routing and forwarding protocols in wireless ad-hoc networks. ACM Springer Wireless Networks (WINET), Special Issue of Selected Papers of Mobicom 2005, 2007. 12. http://www. priceline.com. 2010. 60