text:
# Leadership Statistics in Random Structures

## Abstract

The largest component (“the leader”) in evolving random structures often exhibits universal statistical properties. This phenomenon is demonstrated analytically for two ubiquitous structures: random trees and random graphs. In both cases, lead changes are rare as the average number of lead changes increases quadratically with logarithm of the system size. As a function of time, the number of lead changes is self-similar. Additionally, the probability that no lead change ever occurs decays exponentially with the average number of lead changes.

Extreme statistics are important in science, engineering, and society as they dictate catastrophic events, systems robustness, financial indices, etc. The theory of extreme statistics provides a powerful analysis framework and prediction tool res ; jg . However, it is limited to ensembles of independent random variables. Even though most practical applications involve correlated random variables, such cases remain largely unexplored bm ; bkm ; mk .

We investigate extremal characteristics of two basic random structures: random trees and random graphs. Random trees appear in data storage algorithms in computer science hmm ; dek ; ws  and in physical processes such as collisions in gases vvd . Random graphs bb ; jlr  have numerous applications to theoretical computer science dek ; ws , social networks sp ; gn , and physical processes such as polymerization pjf .

We focus on the largest component, the leader, and ask: What is the size of the leader? How does the number of lead changes depend on time and system size? What is the probability that the leader never changes? Similar questions were investigated in growing networks mda ; kr , and related leadership statistics were studied in random graphs by Erdős and Łuczak tl .

Random trees and random graphs are special cases of aggregation processes and hence, we analyze them using the rate equation approach mvs ; sc ; jbm ; hez . Characterization of leadership statistics is sensible only for finite systems. We thus consider large yet finite systems for which the rate equation approach yields the leading asymptotic dependence on the system size aal ; jls ; ve .

Our main result is that the total number of lead changes $`L`$ grows as $`L(N)[\mathrm{ln}N]^2`$ with the system size $`N`$. This as well as other leadership statistics are universal as they characterize both random trees and random graphs. The time dependent number of lead changes $`L(t,N)`$ attains the scaling form $`(\mathrm{ln}N)^2F(x)`$ with the scaling variable $`x=\mathrm{ln}k_{}/\mathrm{ln}N`$ where $`k_{}`$ is the typical component size. Additionally, the probability that no lead change ever occurs decays as $`e^L`$.

We start with the simpler case of random trees. These are generated according to the following procedure. Initially, the system consists of $`N`$ single-leaf trees. Then, two trees are picked at random and attached to a common root. This merging process is repeated until a single tree with $`N`$ leafs emerges. We treat the merging process dynamically. Let $`n`$ be the number of trees. In the thermodynamic limit, the normalized density $`c=n/N`$ evolves according to $`\frac{d}{dt}c=c^2`$ because in every merger two trees are lost and one is gained (for convenience, the merger rate is set to unity). Subject to the initial condition $`c(0)=1`$ the density is $`c(t)=(1+t)^1`$ and given the simple relations between the number of trees $`n=N(1+t)^1`$, the average size $`m=1+t`$, and time $`t`$, we state our results in terms of time.

The size distribution is obtained similarly. Let $`n_k`$ be the number of trees with $`k`$ leafs. The normalized density $`c_k=n_k/N`$ evolves according to the Smoluchowsky rate equation $`\frac{d}{dt}c_k=_{i+j=k}c_ic_j2cc_k`$ with the monodisperse initial conditions $`c_k(0)=\delta _{k,1}`$. The rate equation reflects the fact that trees are merged randomly, independent of their size. It can be solved (using the generating functions technique for example) to give mvs ; sc

$$c_k(t)=\frac{t^{k1}}{(1+t)^{k+1}}.$$
(1)
In the long time limit, the size distribution attains a simple self-similar behavior

$$c_k(t)k_{}^2\mathrm{\Phi }(k/k_{}),\mathrm{\Phi }(x)=e^x$$
(2)
with the typical size $`k_{}t`$.

What is the average size of the largest tree (the leader)? Using the size distribution, we can answer an even more general question. Let $`l_r(t)`$ be the average size of the $`r`$-largest tree with the leader $`ll_1`$. From the cumulative distribution $`u_k=_{jk}n_j=Nt^1[t/(1+t)]^k`$ and the relation $`u_{l_r}=r`$, the size of the $`r`$th leader is

$$l_r(t,N)=\frac{\mathrm{ln}[N/rt]}{\mathrm{ln}[(1+t)/t]}.$$
(3)
There are two regimes of behavior. In the short time limit, $`t1`$, one has $`l_r(t,N)=1+\mathrm{ln}[N/r]/\mathrm{ln}[1/t]`$. Moreover, from $`n_kNt^{k1}`$ the first dimer appears at $`t_2N^1`$; the first trimer appears at $`t_3N^{1/2}`$ and then, there are of the order $`N^{1/2}`$ dimers, so this trimer results from the leading dimer with probability of the order $`N^{1/2}`$. Since almost every lead change introduces a new leader, the leader grows in increments of unity. At the crossover point, $`t1`$, the size of the leader varies logarithmically with the system size, $`l(t1,N)\mathrm{ln}N`$. In the long time limit, $`t1`$, the size of the leader grows linearly (up to a logarithmic correction) with time

$$l_r(t,N)t\mathrm{ln}\frac{N}{rt}.$$
(4)
What is the average size $`l_w`$ of the winner (the last emerging leader)? At what time $`t_w`$ does the winner emerge? Both quantities grow linearly with $`N`$: $`l_w\alpha N`$ and $`t_w\beta N`$. The curve $`\alpha =\beta \mathrm{ln}\beta `$ obtained from Eq. (4) has an extremum at $`\alpha =\beta =e^10.36788`$ thereby implying the bounds: $`\alpha ,\beta <e^1`$.

How many lead changes $`L(t,N)`$ occur as a function of time? As a function of system size? What is the total number of lead changes $`L(N)L(t=\mathrm{},N)`$? In our definition, a lead change occurs when two trees (none of which is the leader) merge to become larger than the leader. For short times, $`t1`$, we noted that $`L(t,N)=l(t,N)1`$. For long times, $`t1`$, consider the cumulative distribution $`u_kNt^1\mathrm{exp}(k/t)`$. Its growth rate immediately gives the rate by which the leader is surpassed, $`\frac{d}{dt}L(t,N)=\frac{d}{dt}u_k|_{k=l}`$. As $`u_l1`$, we have $`\frac{d}{dt}L(t,N)lt^2t^1\mathrm{ln}\frac{N}{t}`$ from which the time-dependent number of lead changes is

$$L(t,N)\mathrm{ln}t\mathrm{ln}N\frac{1}{2}(\mathrm{ln}t)^2.$$
(5)
Interestingly, this quantity obeys the scaling form

$$L(t,N)=(\mathrm{ln}N)^2F(x),x=\frac{\mathrm{ln}t}{\mathrm{ln}N}$$
(6)
with the quadratic scaling function: $`F(x)=x\frac{1}{2}x^2`$. The scaling variable is unusual: a ratio of logarithms, in contrast with the ordinary ratio underlying the size distribution (2).

To check these theoretical predictions, we performed large-scale Monte Carlo simulations. In the simulations, randomly chosen trees are merged repeatedly. Keeping track of the leader and averaging over many independent realizations, we observe a scaling behavior that is consistent with Eq. (6). However, as a function of the system size, the convergence is slow because the scaling variable involves logarithms.

We briefly mention a neat alternative derivation of the time-dependent behavior. The number of lead changes can be obtained from $`\frac{d}{dt}L=(\mathrm{\Delta }t)^1`$, where the time interval between successive lead changes $`\mathrm{\Delta }t`$ is estimated from $`l_1(t)=l_2(t+\mathrm{\Delta }t)`$. This approach confirms the scaling form (6) with $`F(x)=(x\frac{1}{2}x^2)/\mathrm{ln}2`$, i.e., there is a factor $`1/\mathrm{ln}2`$ discrepancy.

The time dependent behavior can be used to obtain the total number of lead changes. Substituting $`t_w=\beta N`$ into Eq. (5) gives

$$L(N)A(\mathrm{ln}N)^2$$
(7)
with $`A=F(1)=1/2`$. Both the leading asymptotic behavior and the $`\mathrm{ln}N`$ correction are confirmed numerically. Moreover, the numerical prefactor $`A=0.50(1)`$ agrees with the theoretical prediction (Fig. 2). Since $`L(t1,N)\mathrm{ln}N`$, the majority of lead changes occur when $`t1`$.

How is the number of lead changes distributed? What is the probability that no lead change occur? Let $`P_n(t,N)`$ be the probability that $`n`$ lead changes occur till time $`t`$. The flux surpassing the leader characterizes the evolution of the probability distribution $`\frac{d}{dt}P_n=(\frac{d}{dt}L)[P_{n1}P_n]`$. With the initial condition $`P_n(0,N)=\delta _{n,0}`$, the distribution is Poissonian

$$P_n(t,N)=\frac{[L(t,N)]^n}{n!}e^{L(t,N)}.$$
(8)
Consequently, the distribution of the total number of lead changes $`P_n(N)P_n(t=\mathrm{},N)`$ is also Poissonian: $`P_n(N)=\frac{L^n}{n!}e^L`$ with $`LL(N)`$ given by Eq. (7). Hence, the variance in the number of lead changes $`\sigma (N)`$ grows as $`\sigma (N)\sqrt{A}\mathrm{ln}N`$. Furthermore, the probability that no lead change occur (the survival probability of the first leader) $`S(N)P_0(N)`$ decays faster than a power-law but slower than a stretched exponential

$$S(N)=\mathrm{exp}[L]\mathrm{exp}\left[A(\mathrm{ln}N)^2\right].$$
(9)
The asymptotic $`N`$-dependence is confirmed numerically (Fig. 3).

We now consider graphs, grown randomly as follows. Initially, the system consists of $`N`$ single-node graphs. Then, two nodes are picked at random and a link is drawn between them. If they belong to two distinct graphs, the two become one. This process is repeated indefinitely. Let $`n_k`$ be the number of graphs of size $`k`$. The normalized density $`c_k=n_k/N`$ evolves according to the rate equation $`\frac{d}{dt}c_k=\frac{1}{2}_{i+j=k}ijc_ic_jkc_k`$ with the monodisperse initial conditions $`c_k(0)=\delta _{k,1}`$. The rate equation reflects the fact that two graphs are connected with rate proportional to the product of their sizes. This equation can be solved using generating functions to give jbm ; hez

$$c_k(t)=\frac{(kt)^{k1}}{kk!}e^{kt}.$$
(10)
At time $`t=1`$, the system undergoes a gelation transition: it develops a giant component that eventually takes over the entire mass in the system. Close to this gelation time the size distributions attains the scaling behavior

$$c_k(t)k_{}^{5/2}\mathrm{\Phi }(k/k_{}),\mathrm{\Phi }(x)x^{5/2}e^{x/2}.$$
(11)
The typical size diverges, $`k_{}(1t)^2`$, as $`t1`$. At the gelation time, the size distribution has an algebraic tail $`c_k(t=1)k^{5/2}`$. Hence, the cumulative distribution is $`u_kNk^{3/2}`$ and the criterion $`u_{l_w}1`$ gives the average size of the giant component (the winner), $`l_wN^{2/3}`$ bb . The time at which it emerges is $`1t_wN^{1/3}`$.

We estimate the size of the leader from the cumulative distribution, $`u_l=1`$. For $`t1`$, the size of the leader $`l(t,N)`$, the number of lead changes $`L(t,N)`$, as well as the number of distinct leaders are all approximately equal and the same as for random trees. The number of lead changes is of the order $`\mathrm{ln}N`$ in this phase; furthermore, $`L(t,N)\mathrm{ln}N`$ for $`t<1`$. The behavior near the gelation time $`1t1`$ is a bit more interesting. From the large-$`k`$ behavior, $`u_kN(1t)^2k^{5/2}\mathrm{exp}[k(1t)^2/2]`$, and $`u_l=1`$ we arrive at following implicit relation for the leader $`l(t,N)`$: $`l2(1t)^2\mathrm{ln}N3(1t)^2\mathrm{ln}l`$. Inserting the zeroth order approximation $`l^{(0)}=2(1t)^2\mathrm{ln}N`$ into $`\mathrm{ln}l`$ on the right-hand side of the above relation and ignoring $`\mathrm{ln}\mathrm{ln}N`$ terms yields the leader size

$$l\frac{2}{(1t)^2}\mathrm{ln}[N(1t)^3].$$
(12)
The rate by which the leader changes is estimated from $`\frac{d}{dt}L=\frac{d}{dt}u_k|_{k=l}l(1t)`$. Substituting Eq. (12) and integrating, the number of lead changes is

$$L(t,N)2\mathrm{ln}N\mathrm{ln}\frac{1}{1t}3\left[\mathrm{ln}\frac{1}{1t}\right]^2.$$
(13)
It attains the scaling form

$$L(t,N)(\mathrm{ln}N)^2F(x),x=\frac{\mathrm{ln}\frac{1}{1t}}{\mathrm{ln}N}$$
(14)
with the scaling function $`F(x)=2x3x^2`$. As this behavior holds up to time $`t_w`$, where $`1t_wN^{1/3}`$, the total number of lead changes grows according to Eq. (7) with $`A=F(1/3)=1/3`$. Furthermore, the distribution of lead changes is Poissonian as in (8) and the survival probability decays according to (9).

As terms of the order $`\mathrm{ln}\mathrm{ln}N/\mathrm{ln}N`$ were neglected, the scaling behavior and the leading asymptotic behavior may be realized only for extremely large systems. Moreover, the computational cost of random graph simulations is larger because graphs are chosen with probability proportional to their size. Nevertheless, we can confirm the predicted system size dependence of $`L(N)`$ (Fig. 2) and $`S(N)`$ (Fig. 3) numerically. The prefactor $`A=0.20(2)`$ is lower than the theoretical value $`A=1/3`$, perhaps due to the slow convergence.

Let us compare random trees and random graphs. They seem very different, e.g., the gelation transition occurs in one case but not in the other. Yet, they exhibit similar extremal characteristics. In both cases, the total number of lead changes $`L(N)`$ grows as $`[\mathrm{ln}N]^2`$ and the survival probability decays as $`\mathrm{exp}[L]`$. Moreover, even the seemingly distinct temporal characteristics can be reconciled, e.g., in both cases the size distribution attains the scaling form $`c_k(t)\mathrm{\Phi }(k/k_{})`$ when $`t\mathrm{}`$ (for random trees) and $`t1`$ (for random graphs). Of course, the actual time dependence of the typical scale is different: $`k_{}t`$ and $`k_{}(1t)^2`$, respectively. The size of the leader can be rewritten as $`lk_{}\mathrm{ln}[N/k_{}^\gamma ]`$ with $`\gamma =1`$ and $`3/2`$, respectively. Furthermore, Eqs. (6) and (14) can be reconciled by writing the scaling variable in the unified form $`x=\mathrm{ln}k_{}/\mathrm{ln}N`$.

We now restrict our attention to the survival probability $`S(N)`$ and supplement the leading behavior (9) with rigorous bounds. Consider random trees. A lower bound for $`S(N)`$ is obtained from a greedy scenario in which all merger events involve the leader till it reaches size $`N/2`$. The probability that the second merger involves the leading dimer is $`(N1)^1`$; the probability that the third merger involves the leading trimer is $`(N2)^1`$; etc. Thus, the greedy scenario is realized with probability $`_{j<N/2}\frac{1}{Nj}`$, thereby providing the lower bound $`S(N)>\frac{(N/2)!}{(N1)!}`$. An upper bound can be obtained by estimating the number of trees the size of the leader. There are of the order $`N^{1/2}`$ dimers when the first trimer is born, $`n_2(t_3=N^{1/2})=N^{1/2}`$. The leading dimer retains the lead with probability inversely proportional to the number of dimers, $`N^{1/2}`$. Similarly, this leading trimer retains the lead with probability proportional to $`N^{1/3}`$. Therefore the upper bound $`_{j<\mathrm{ln}N}N^{1/j}`$ is estimated as $`N^{\mathrm{ln}\mathrm{ln}N}`$ (the cutoff $`j<\mathrm{ln}N`$ is dictated by the size of the leader at the crossover time $`t1`$). Hence, the survival probability obeys

$$\left(\frac{e}{2N}\right)^{\frac{N}{2}}<S(N)<\mathrm{exp}\left[(\mathrm{ln}N)(\mathrm{ln}\mathrm{ln}N)\right],$$
(15)
where the lower bound was simplified using the Stirling formula. Note that the upper bound merely assures that the lead never changes in the early phase $`t<1`$ when the average number of lead changes is only $`\mathrm{ln}N`$.

For random graphs, the greedy scenario is again simple to analyze since the probability that in a system with a leader of size $`j`$ and $`Nj`$ monomers the probability that the next merger involves the leader is $`p_j=[j(Nj)]/[j(Nj)+\frac{1}{2}(Nj)(Nj1)]`$ or $`p_j=(2j)/(N+j1)`$. The product $`_{j<N/2}p_j`$ provides the lower bound. Asymptotically, the lower bound decays as $`\lambda ^N`$ with $`\lambda =(2/3)^{3/2}=0.544331\mathrm{}`$. On the other hand, repeating the above argument yields the same upper bound, so

$$\lambda ^N<S(N)<\mathrm{exp}\left[(\mathrm{ln}N)(\mathrm{ln}\mathrm{ln}N)\right].$$
(16)
The upper bound is again much closer to the actual asymptotic behavior.

In conclusion, random graphs and random trees exhibit similar leadership characteristics. As in random growing networks kr , lead changes are infrequent given that the overall number of lead changes increases only logarithmically with the system size. The time dependent number of lead changes approaches a self-similar form asymptotically. The convergence to the asymptotic behavior is much slower for extremal statistics compared with size statistics due to the various logarithmic dependences. Consequently, the asymptotic behavior may difficult to detect in practice, especially for random graphs.

To obtain the extremal characteristics, we employed the scaling behavior of the size distribution outside the scaling regime, namely, at sizes much larger than the typical size where, at least formally, statistical fluctuations can no longer be ignored. Interestingly, the resulting system size dependence for the various leadership statistics appears to be asymptotically exact. Further analysis is needed to illuminate the role of statistical fluctuations, for example by characterizing corrections to the leading behavior.

The virtue of the rate equation approach to analyzing extremal characteristics is its simplicity, robustness, and generality. It applies to general aggregation processes where the merger rate may depend in a complicated manner on the aggregate size or in situations where there is an underlying spatial structure. We find that the above leadership statistics extend to algebraic merger rates as well as to aggregation in one spatial dimension. This method is also applicable to other extremal features including for example laggard (smallest component) statistics. In the case of random trees, for instance, the total number of laggard changes grows logarithmically with the system size.

###### Acknowledgements.

We are thankful to Sidney Redner for many discussions and initial collaboration on this work. This research was supported in part by DOE(W-7405-ENG-36).


format: text

text:
# Observation-based Cooperation Enforcement in Ad hoc Networks

## 1 Introduction

An ad hoc network is a group of wireless mobile computers (or nodes), in which nodes cooperate by forwarding packets for each other to allow them to communicate beyond direct wireless transmission range. Ad hoc networks require no centralized administration or fixed network infrastructure such as base stations or access points, and can be quickly and inexpensively set up as needed. They can be used in scenarios in which no infrastructure exists, or in which the existing infrastructure does not meet application requirements for reasons such as security or cost.

So far, applications of mobile ad hoc networks have been envisioned mainly for crisis solutions (e.g., in the battlefield or in rescue operations). In these applications, all the nodes of the network belong to a single authority (e.g. a single military unit or a rescue team) and have a common goal. For this reason, the nodes are naturally motivated to cooperate.

With the progress of technology, however, it is becoming possible to deploy mobile ad hoc networks for civilian applications as well. Examples include networks of cars, provision of communication facilities in remote areas, and exploiting the density in urban areas of existing nodes such as cellular telephones to offload or otherwise avoid using base stations. In these networks, the nodes may not belong to a single authority and they do not pursue a common goal. In addition, these networks could be larger, have a longer lifetime, and they could be completely self-organizing, meaning that the network could be run solely by the operation of the end-users. In such networks, there is no good reason to assume that the nodes cooperate. Indeed, the contrary is true: some nodes may be disruptive and others may attempt to save resources (e.g. battery power, memory, CPU cycles) through “selfish” behavior.

In this paper we describe OCEAN, in which we focus on the robustness of packet forwarding: maintaining the overall packet throughput of an ad hoc network in the face of nodes that misbehave at the routing layer. We concentrate our efforts at the routing layer and do not attempt to address attacks at lower layers (eg. jamming the network channel) or passive attacks like eaves-dropping. We also do not deal (much) with issues like node authentication, securing routes, or message encryption. Instead, secure routing protocols ,,, are designed to combat those threats. OCEAN addresses an orthogonal issue – the encouragement of proper routing participation – and can be used in addition to secure routing protocols to respond to a more complete threat model. We also do not consider the collusion of nodes in a network, but merely the individual bad behavior of nodes.

OCEAN considers two types of routing misbehavior. The first, which we call *misleading*, is that a node may respond positively to route requests but then fail to forward the actual packets, misleading other nodes into unsuccessfully sending their traffic through it. Previous approaches at mitigating misleading routing misbehavior ,,, require nodes in the network to exchange reputation information about other nodes. If a node observes another node participating incorrectly, it reports this observation to other nodes who then take action to avoid being affected by the misbehavior and perhaps even punish the node by refusing to forward its traffic.

While these schemes have proved effective, exchanging second-hand reputation information opens up a new vulnerability, since nodes may falsely accuse other nodes of misbehaving. Making a decision about whether to believe an accusation requires authenticating and trusting the accusing node. Such trust maintenance could be performed offline or could be bootstrapped during network operations. In the former case, the network requires a priori trust relationships that may not be practical in truly ad hoc networks. In the latter case, bootstrapping trust relationships in ad hoc networks involves significant complexity and risk and may not be reasonable for a very dynamic or short-lived network.

OCEAN’s approach to this problem is to disallow any second-hand reputation exchanges. Instead, a node makes routing decisions based solely on direct observations of its neighboring nodes’ exchanges with it. This eliminates most trust management complexity, albeit at a cost of less information with which to make decisions about node behavior. To our surprise, though, we find that less information does not necessarily mean less performance. Using OCEAN we are able to achieve performance (packet throughput) comparable to that of approaches requiring second-hand information exchanges. On the positive side, OCEAN achieves this while being less complex and less vulnerable to false accusations. On the negative side, OCEAN is more sensitive to some parameter settings and does not punish misbehaving nodes as severely as systems using full-blown reputation information.

The second type of routing misbehavior we address, which we call *selfish*, is that a node may not even respond to route requests but may nonetheless send its own traffic through the network, unfairly preserving its resources while exploiting others’. This type of misbehavior can be hard to detect, except through observing the actual data forwarding behavior of neighboring nodes. In OCEAN, we again focus on detecting this misbehavior with only direct observations of neighboring nodes. We address the problem using simple, light-weight economic methods that, while not guaranteed to be fair, nonetheless generally result in reasonable performance.

Section 2 describes recent work related to the problem of managing misbehavior at the routing layer in ad hoc networks. Section 3 presents an overview of the modules used in OCEAN to mitigate such routing misbehavior. Section 4 describes a scheme to deter selfish behavior. Section 5 discusses the simulation results we obtained and compares OCEAN to reputation-based approaches. Section 6 gives more detail about node authentication issues in OCEAN. Finally, Section 7 concludes.

## 2 Related Work

Recently, the problem of security and cooperation enforcement has received considerable attention by researchers in the ad hoc network community.

The problem of securing the routing layer using cryptographically secure messages is addressed by Hu et al.  , Papadimitratos and Haas , and Sanzgiri et al. . Schemes to handle authentication in ad hoc networks assuming trusted Certificate Authorities have been proposed by Zhou and Haas , and Kong et al. . Hubaux et al.  employ a self-organized PGP-based scheme to authenticate nodes using chains of certificates and transitivity of trust. Stajano and Anderson  authenticate users by ‘imprinting,’ in analogy to ducklings acknowledging the first moving subject they see as their mother. In OCEAN, we do not attempt to secure the routing layer, although our techniques may be used in conjunction with many secure routing protocols to increase performance and robustness.

In contrast to securing the routing layer of ad hoc networks, some researchers have also focused on simply detecting and reporting misleading routing misbehavior. Watchdog and Pathrater  use observation-based techniques to detect misbehaving nodes and report observed misbehavior back to the source of the traffic. Pathrater manages trust and route selection based on these reports. This allows nodes to choose better paths along which to route their traffic by routing around the misbehaving nodes. However, the scheme does not punish malicious nodes; instead, they are relieved of their forwarding burden.

CONFIDANT  also detects misleading nodes by means of observation and more aggressively informs other nodes of this misbehavior through reports sent around the network. Each node in the network hosts a monitor for observations, reputation records for first-hand and trusted second-hand reports, trust records to control the trust assigned to received warnings, and a path manager used by nodes to adapt their behavior according to reputation information. In more recent work  , these researchers find that reputation schemes can be beneficial for fast misbehavior detection, but only when one can deal with false accusations, for which they propose a solution using Bayesian statistics. Our goal is to avoid the machinery for managing these reports and their associated trust issues entirely.

Peer-to-Peer (P2P) networks face a similar situation in which they rely on cooperation among self interested users. Recent studies have modelled and quantified the incentives and disincentives for cooperation in P2P networks (,). These results generally appear to support the feasibility of the approach.

Researchers have also investigated means of discouraging selfish routing behavior in ad hoc networks, generally through payment schemes ,,. These approaches either require the use of tamper-proof hardware modules or central bankers to do the accounting securely, both of which may not be appropriate in some truly ad hoc network scenarios. In the per-hop payment scheme proposed by Buttyan and Hubaux , the payment units are called nuglets and reside in a secure tamper-proof module in each node. They find that given such a module, increased cooperation is beneficial not only for the entire network but also for individual nodes. We rely on much of their work and likewise use a payment scheme. In our simple “chipcount” mechanism, further described in Section 4, each node keeps track of the number of packets it has forwarded for its direct neighbors and expects corresponding willingness from those neighbors to carry its traffic. The scheme can result in unfairness to some hosts, but its simplicity and performance may be appropriate in some scenarios.

## 3 Overview of OCEAN

OCEAN is a layer that resides between the network and MAC layers of the protocol stack, and it helps nodes make intelligent routing and forwarding decisions. We have designed OCEAN on top of the Dynamic Source Routing Protocol (DSR) , although many of its principles may also be useful in other ad hoc routing protocols. In this section we describe the components of OCEAN that detect and mitigate misleading routing behavior. Section 4 describes our techniques for mitigating selfish behavior.

The OCEAN layer, which may reside on each node in the network, hosts five components:

NeighborWatch: This module observes the behavior of the neighbors of a node. It relies on the omni-directional nature of the antenna and assumes symmetric bi-directional links. In particular, it tracks misleading routing misbehavior. When forwarding a packet, the module buffers the packet checksum, and then monitors the wireless channel after sending the packet to its neighbor. If it does not hear the neighbor attempt to forward the packet within a timeout (default 1ms), NeighborWatch registers a negative event against the neighbor node and removes the checksum from its buffer. On the other hand, on overhearing a forwarding attempt by the neighbor, NeighborWatch compares the packet to the buffered checksum, and if it matches, it registers a positive event and removes the checksum from its buffer. If the checksum does not match, it treats the packet as not having been forwarded. These events are communicated to the RouteRanker, which maintains ratings of the neighbor nodes.

The NeighborWatch module is not a guaranteed service. It suffers from all the same potential errors as the Watchdog , including, for example, the fact that observing a neighbor forwarding a packet does not guarantee that the packet is successfully received by the next node in the route.

NeighborWatch on a node tracks only this one type of behavior with neighbors directly interacting with it. There are many other events among neighbors that NeighborWatch could potentially track, but they are subject to too many vulnerabilities and thus become more complex to analyze. For instance, NeighborWatch on a node A could observe the success and failure rates of its neighbors attempting to forward traffic between themselves. Failure of a neighbor, B, to forward a packet from some other neighbor, C, could trigger a negative event registration against B on A. Unfortunately, only B knows for sure whether its refusal to forward C’s traffic is due to misleading behavior on B’s part or is instead B’s legitimate response to C’s previous misbehavior toward B.

RouteRanker: Every node maintains ratings for each of its neighboring nodes. The rating is initialized to Neutral and is incremented and decremented on receiving positive and negative events respectively from the NeighborWatch component. We have found that the system performs more satisfactorily when the absolute value of the negative decrement is larger than the positive increment. Once the rating of a node falls below a certain threshold, Faulty Threshold, the node is added to a faulty list. The faulty list represents a list of all observed misbehaving nodes. A route is rated good or bad, based on whether the next hop in the route belongs to the faulty list or not. One can imagine a finer ranking between routes, where good routes are further differentiated, but our simple binary discrimination between good and bad routes proves to be reasonably effective. The default parameters we use in OCEAN are tabulated in Table 1.

Rank-Based Routing: The Rank-Based Routing module applies the information from NeighborWatch in the actual selection of routes. To make it possible to avoid routes containing nodes in the faulty list, we add a variable-length field to the DSR Route-Request Packet (RREQ) called the avoid-list. The avoid list is a list of nodes that the RREQ transmitter wishes to avoid in its future routes. On re-broadcasting an RREQ, a node appends its faulty list to the avoid list of the RREQ packet. Any node receiving an RREQ checks the RREQ avoid list. Depending upon the avoid list and the RREQ-route, a node decides whether to suppress the RREQ, or honor the RREQ by either re-broadcasting it or replying with a DSR Route-Reply. If the intersection of the avoid list and the DSR route in the RREQ packet is non-void (i.e. a node which was requested to be avoided is in the route), the RREQ packet is suppressed. Similarly, a DSR Route-Reply (RREP) is honored only if the route in the RREP does not contain a node in the locally-maintained faulty list. Otherwise, the RREP is simply dropped.

In this way, each node along the route makes its own local decision about nodes to trust, and a node has control only over routes that go directly through it. Nodes may tamper with the avoid lists, in particular with a Rushing Attack, but in Section 5 we describe the attack and show through simulation results that the protocol is fairly robust against this kind of avoid list tampering. The avoid list could also be made tamper-proof with increased overhead, in the context of cryptographically secure protocols.

Malicious Traffic Rejection: This module performs the straight-forward function of rejecting traffic from nodes it considers misleading. We employ the policy of rejecting all traffic from a misleading node so that a node is not able to relay its own traffic under the guise of forwarding it on somebody else’s behalf.

Second Chance Mechanism: The Second Chance Mechanism is intended to allow nodes previously considered misleading to become useful again. Without a second chance, once a node is added to the faulty list, all future routes through it would be avoided, giving that node no opportunity to demonstrate its “goodness.” This may be unfairly harsh on a node, especially since the NeighborWatch module is not guaranteed to be correct in its judgments. A node may simply have been experiencing transient link failures, or it may have needed to restart its network interface. To account for such problems, we use a timeout-based approach where a misleading node is removed from the faulty list after a fixed period of observed inactivity. Even though the node is removed from the faulty list, its rating is not increased to neutral, so that it can quickly be added back in the event of continued misbehavior. This timeout value is called the Faulty Timeout.

## 4 Selfish Behavior

In this section we describe how OCEAN attempts to mitigate selfish routing behavior in ad hoc networks. The general idea is to punish nodes for their selfish behavior, by rejecting their traffic, in the hopes that this threat will act as a deterrent.

Unfortunately, it can be hard to detect selfish behavior through observations of the routing protocol itself, since there are many undetectable techniques through which a node can avoid becoming visible as a potential router. A few examples of such manipulation of routing-related messages (specific to DSR), which can go undetected, are

1. Dropping the Route Request (RREQ). Inappropriate dropping of RREQs can easily go undetected, since RREQs are broadcast, are not acknowledged, and can legitimately be dropped in some circumstances.
2. Adding too many nodes to the route in the RREQ packet. If a node adds many other nodes to a RREQ packet, the resulting path will appear to be undesirably longer than paths through nodes that have not tampered with the RREQ. The result is that paths through such a nodes are unlikely to be chosen.
3. Adding a non-existent route in the RREQ packet. If a node modifies the path in the RREQ such that it does not exist, then traffic will not reach the misbehaving node.

Because such manipulations of the routing protocol may go undetected, if not otherwise secured through heavier-weight cryptographic means, the best evidence of a node’s cooperation is the actual number of packets it forwards. A decision about whether to forward a node’s packet can be based on its past forwarding performance. This creates a loose packet-forwarding economy between nodes. Similar economy-based approaches ,,  require the use of tamper-proof hardware modules or centralized bankers for secure accounting.

OCEAN instead relies only on direct observations of interactions with neighbors to measure their performance. Every node maintains counters called chipcounts for each neighbor. A chipcount can be thought of as a bank balance in a bank hosted by the node that maintains the chipcount. A node earns chips at a node upon forwarding a packet on behalf of that node. Similarly, a node loses chips with a node it asks the node to forward a packet. When deciding whether to service a forwarding request, a node checks its chipcount for that neighbor. If the chipcount falls below a threshold, the node denies the request.

We have experimented with two trade-based schemes: optimistic and pessimistic. In the optimistic scheme, a node A increments the chipcount for a node B whenever node B accepts a packet from node A, regardless of whether B actually forwards the packet. The pessimistic scheme, on the other hand, increments the chipcount for node B only when node B is observed to forward the packet. In both cases, node A will only know to ask B to forward traffic if B has previously participated in the route request protocol and is therefore on a route through A. If B fails to forward A’s traffic at this point, then the NeighborWatch module will detect the misleading behavior. The chipcount scheme, instead, detects behavior where B selfishly asks A to forward traffic, even if B has managed to escape being on any routes through A.

The pessimistic scheme suffers from a deadlock problem where two nodes may not forward packets for each other for a long time because one node fails to observe the other node forwarding a packet on his request. On the other hand, an optimistic scheme could be too lenient on the misbehaving nodes, since the chips for these nodes are incremented even though the nodes do not forward packets.

This trade-based scheme may suffer from unfairness to nodes on the periphery of the network. These nodes may be punished because they do not receive sufficient opportunity to forward packets for others. This can cause the throughput of the network to fall significantly, and it can cause the network to “shrink” in upon itself as the interior neighbors of the peripheral nodes themselves appear to become peripheral nodes. To address this problem, we add a tunable parameter called the Chip Accumulation Rate (CAR). CAR is the rate at which all chipcounts in the network are increased per unit time. Thus, even when a neighbor does not forward any packets for a node, it will eventually have a non-zero chipcount value and can thus forward traffic at some reduced rate.

Setting an appropriate CAR value requires a trade-off. An infinite CAR value would allow selfish nodes to enjoy full freedom in relaying their packets, since they will never run out of chips at any node. On the other hand, a zero CAR value suffers from the unfairness to peripheral nodes and the reduced network throughput for cooperating nodes described above. In our simulations, using high mobilities and a topology that places many nodes on the periphery, we find that having a low CAR value punishes selfish nodes much more than the cooperating nodes, which indicates that at least the trade-off plays in our favor.

## 5 Simulation Results

In this section, we demonstrate that mitigating routing misbehavior and selfish behavior through the use of direct observation of nodes can often be as effective as techniques deploying second-hand node reputation. We first describe our simulation environment and then go on to compare the throughput of OCEAN in the presence of misleading or selfish nodes against a network using second-hand reputation information.

We implemented OCEAN and its variants in GloMoSim , a commonly-used simulator in the ad hoc research community. These simulations model radio propagation using the realistic two-ray ground reflection model and account for physical phenomena such as signal strength, propagation delay, capture effect and interference. The Medium Access Control protocol used is the IEEE 802.11 Distributed Coordination Function(DCF). The parameters we use for the simulations are given in Table 2. All results have been plotted after taking an average over 20 simulation runs. The ratio of the standard deviation and the average was around 1.35 for highly mobile scenarios and around 0.70 for low mobility scenarios. We simulate only connections longer than two hops, since one-hop connections would artificially inflate our throughput figures (even in the face of 100% misleading nodes, we would see some throughput.) While the mobility model we simulate is not as realistic as we could hope for, it is very commonly used, making it possible for us to compare our work directly against others’ results. We hope to test our ideas in other models and real systems in the future.

We first consider the throughput of cooperating nodes in OCEAN in the presence of varying numbers of misleading nodes and compare it to the same network without OCEAN and also the same network without OCEAN but in which the nodes are merely selfish rather than misleading (Figure 1). We make this latter comparison because it helps us judge the potential utility of OCEAN. Any misbehavior-detecting protocol should not be expected to perform better than a network in which the nodes drop packets but do not actively mislead other nodes. This is because misbehavior detection can at most prevent nodes from being misled by others; it cannot force the misbehaving nodes to begin forwarding packets. We observe that OCEAN performs drastically better than the same network without OCEAN, and it can even sustain a performance close to the defenseless network with merely selfish nodes. It helps sustain 90% of the original throughput even when 25% of the nodes misbehave. As the percentage of the misbehaving nodes approaches 100%, the throughput inevitably falls to zero. At lower numbers of misbehaving nodes, OCEAN actually appears to perform better than the network with merely selfish nodes. This is because OCEAN also routes around nodes that drop packets because they are merely overloaded, not intentionally misleading.

We next compare the performance of OCEAN to a protocol, SEC-HAND, that uses second-hand reputation information. SEC-HAND is intended to represent the family of protocols that use second-hand reputation information. SEC-HAND uses ALARM messages between nodes to communicate information about misbehaving nodes (similar to those used in CONFIDANT ). We augmented the DSR Route-Error Packet to contain an “Alarm” field. The node in the Alarm field is advertised as misbehaving and all nodes overhearing the Alarm add the accused node to their respective faulty lists. SEC-HAND is otherwise like OCEAN, to make it possible to compare the techniques fairly.

We make our comparisons of OCEAN and SEC-HAND across varying values of the Faulty Threshold and varying degrees of mobility (in Figure 2). We vary the Faulty Threshold, because it controls the speed and the accuracy of misbehavior detection. A small (by absolute value) faulty threshold adds nodes faster to the faulty list, but also suffers from the problem of false positives. A large faulty threshold suffers from a slow detection speed. Detection speed is particularly important for OCEAN, since it needs to evaluate new neighbor nodes from scratch. Hence, faster detection should help OCEAN. SEC-HAND should tolerate slower detection speeds, since it keeps records of remote nodes and thus has more information available when a new node joins the neighborhood. Accuracy, on the other hand is critical for SEC-HAND, since SEC-HAND can spread false information in the network if the detection was not accurate. OCEAN should be more resilient to false detection, since bad information will be kept local.

We vary the degree of mobility, because we would expect SEC-HAND to perform better than OCEAN in highly mobile scenarios. High mobility implies a quickly changing neighborhood, and OCEAN nodes must must learn about new neighbors from scratch. On the other hand, SEC-HAND maintains ratings for remote nodes, which can be helpful in quickly judging new local nodes that were previously remote.

From the results, we find that at high Faulty Thresholds, SEC-HAND is indeed able to perform better than OCEAN at high mobilities, as expected. On the other hand, OCEAN outperforms SEC-HAND at low Faulty Thresholds because SEC-HAND is much more susceptible to false positives. At high mobility, OCEAN is more sensitive to the tuning of the Faulty Threshold parameter, while SEC-HAND performs well over a broader range of tunings. Both protocols perform better with lower mobility. Overall, if OCEAN and SEC-HAND both tune the faulty thresholds to suit themselves, OCEAN can outperform SEC-HAND (even for highly mobile networks). We conclude that, even in highly mobile networks, the network can perform reasonably well without the need to exchange second-hand information.

We further compare the performance of OCEAN and SEC-HAND in the face of transient failures (weak links) in Figure 3. Both of the protocols can incorrectly detect such failures as misbehaving node behavior and over-react accordingly. Because of this problem, OCEAN includes a parameter called Faulty Timeout, which controls the idle time before a neighbor declared misbehaving is given a second chance and is elevated to the status of being non-faulty (albeit with a low rating). Some protocols using second-hand reputation information never give nodes a second chance, but we also implement this feature in SEC-HAND, to provide fair comparison. A concern, however, is how quickly the protocols respond when the node given a second chance still proves to be misbehaving. In SEC-HAND, if the timed-out faulty node is multiple hops away, we need to wait for another ALARM message before the node is added back to the faulty list. In OCEAN, we only detect misbehavior of direct neighbors, which allows us to determine quickly, on subsequent traffic through them, whether to put misbehaving neighbors back on the faulty list. This is seen in a comparative degradation in SEC-HAND’s performance at low Faulty Timeout values.

We next examine the vulnerability of OCEAN if it is deployed over a protocol that does not secure control packets against tampering. The attack that a malicious node may attempt is called a Rushing Attack , whereby a node hurries a “tampered” route-request through itself. The next node along the path will forward this tampered route request and drop further instances of the same route request that come from other nodes. In this way, the malicious node can establish a route through itself because its route is the first seen by a downstream node, and it can later drop the data packets sent through it. The Rushing attack in OCEAN is illustrated in Figure 4. Note, though that if node R in the illustration had been the destination, the problem would have been avoided, since by default DSR requires destination nodes to reply to all route requests they receive. In that case, the good route would have been found.

However, in our simulations of random networks, this attack seemed to make little difference. Figure 4 also shows the throughput of the network when the malicious nodes tamper with the avoid lists. The throughput remains reasonable, since for the attack to be possible a relatively specific configuration of nodes is needed, which does not occur frequently, at least in random ad hoc networks. There are many other ways a malicious node may attack a network if the routing layer is not secured. However, we believe our experiments show that OCEAN does not add any new vulnerabilities that should significantly affect performance.

Another metric of evaluation for OCEAN is the throughput of the misleading nodes. Ideally, we would like the throughput of the misleading nodes to be as low as possible, to deter their behavior. Figure 5 plots the throughput of the misleading nodes in defenseless, OCEAN, and SEC-HAND networks. Unfortunately, we see that OCEAN is not very effective in thwarting the throughput of the misleading nodes. This is because the misleading nodes also use OCEAN to route around other misleading nodes or nodes that did not forward their packets. They were thus able to maintain a good (and sometimes better) throughput even when the network was using OCEAN. Even in SEC-HAND the misleading nodes are able to take advantage of the SEC-HAND modules, however SEC-HAND is better at punishing the misbehaving nodes, since the bad reputation of the misbehaving nodes spreads much faster.

We go on to examine the sensitivity of the throughput of these misleading nodes to varying Faulty Threshold and Faulty Timeout values. The results are in Figure 6. Interestingly, the throughput of the misleading nodes is almost constant with a varying Faulty Threshold. Since the malicious nodes also use OCEAN with the same parameters as the rest of the network, the positive and negative effects of decreasing the Faulty Threshold almost cancel each other out. On the other hand, increasing the Faulty Timeout thwarts the throughput of the faulty nodes, as one would expect, since the misleading nodes get fewer second chances.

Finally, in addition to considering networks with misleading routing behavior, we consider the performance of networks containing merely selfish nodes. We study the performance of the economy-based scheme proposed in Section 4 in a simulation that places many nodes on the periphery of the network (a 1500m by 300m rectangle). This topology emphasizes the problems that our economy scheme causes in terms of unfairness to peripheral nodes and reduced throughput for cooperating nodes. Figure 7 plots the throughput of the cooperating nodes and the selfish nodes with varying chip accumulation rates (CARs) under optimistic and pessimistic schemes.

At a low CAR value, the throughput of the cooperating nodes suffers a two-fold decrease, leading one to want to tune CAR to higher values. On the other hand, the throughput of selfish nodes changes by a factor of five to six, leading one to want to tune CAR to lower values, to adequately punish selfish nodes. Overall, we see that an optimistic scheme better suits these trade-offs than a pessimistic scheme. An “optimum” CAR value, though, may vary depending on network requirements, and there is no good mechanism in our simple scheme for preventing individual nodes from tuning CAR to whatever value best meets their selfish needs.

## 6 Authentication Issues

In the work we present in this paper, we assume that nodes do not spoof each other’s identities, since this would allow misbehaving nodes to exploit the good reputation of neighboring cooperating nodes. Since in reality it is easy to spoof IP addresses and even MAC addresses, this would imply the use of a cryptographically secure authentication mechanism, perhaps as provided through a secure routing protocol.

Unfortunately, we do not yet find a secure routing protocol that handles authentication in a manner that matches the spirit of OCEAN in being truly ad hoc and also manageably simple. Some secure routing protocols rely on pre-assigned certificates from common certificate authorities to authenticate nodes , but it may not always be possible in truly ad hoc contexts for nodes to hold such pre-assigned certificates from authorities that all nodes will respect. Efforts to develop on-the-fly certificate authorities within the network   appear either to be quite complex or to distinguish the role of certificate authority among a subset of nodes, which does not provide complete decentralization.

In OCEAN, we instead hope to give up the requirement for stable identities for nodes *at the routing level*, and instead merely prevent nodes from spoofing one another. To achieve this objective, nodes generate their own asymmetric key pairs, the public portion of which they can exchange with neighbors, using them perhaps merely to agree upon lighter-weight authentication secrets.

This mechanism, however, does not prevent a node from generating multiple identities rapidly and then discarding identities once the associated reputations have fallen below threshold. To deal with such short-term identities, we hope to leverage recent work on proof-of-effort mechanisms  . In the context of OCEAN, we could mandate that a new identity be accepted only if the identity-owner shows reasonable proof of recent effort in generating that identity. This would not require nodes to maintain stable identities for very long, but they would not find it advantageous to cycle through them fast enough to cause much havoc undetected.

## 7 Conclusions and Future Work

This paper presents the OCEAN techniques for detecting and mitigating misleading routing behavior in ad hoc networks. Our goal was to study how far we can get using only direct observations of neighbors. We find that this scheme works surprisingly well, in terms of network throughput, considering its simplicity compared to schemes that share second-hand reputation information throughout the network. Compared to such reputation schemes, OCEAN is more sensitive to the tuning of some parameters, and it fails to punish misbehaving nodes as severely, but it performs almost as well, and sometimes even better, across a wide range of degrees of mobility.

We also find that our chipcount scheme provides a simple first step at being able to deter selfish behavior in the network. However, this scheme is accompanied with network throughput deterioration. Further work is warranted to see if we can do a better job of using only directly-observable information to identify and deter selfish nodes without such significant reductions in the throughput of cooperating nodes.

We also understand that our random simulation models cover an unrealistically small sample of potential network behavior. We would like to simulate other more realistic models, and test our ideas in real systems if we have sufficient resources to do so.

Finally, we plan to study how we can provide more effective infrastructure-free authentication in ad hoc networks assuming that identities need not be entirely stable at the routing level, but that spoofing of other nodes is unacceptable.

## 8 Acknowledgments

We thank the students in CS444N for their initial efforts and input into this project. We especially thank Yan Liu who continued to work on this project after the class was over. We are very grateful to the Nokia Research Center for supporting this project. The project has also been supported in part by MURI award number F49620-00-1-0330 and the Stanford Networking Research Center.