Computer Science Mathematics
ComputerScience,1970-2008-Computer Science-2007.jsonl.gz.gz
Computer Science
d4ba102c5e75d93d8bc909f27db115bc9132c7b8
Neighbor Discovery in Wireless Networks:A Multiuser-Detection Approach

We examine the problem of determining which nodes are neighbors of a given one in a wireless network. We consider an unsupervised network operating on a frequency-flat Gaussian channel, where $K+1$ nodes associate their identities to nonorthogonal signatures, transmitted at random times, synchronously, and independently. A number of neighbor-discovery algorithms, based on different optimization criteria, are introduced and analyzed. Numerical results show how reduced-complexity algorithms can achieve a satisfactory performance.


Introduction
Of late, wireless networks, and in particular sensor networks, have been the object of a good deal of interest, also spurred by the manifold applications they can be associated with (see, for exam-if its amplitude, received by the latter, exceeds a preassigned activity threshold, say τ A . 2 Moreover, nodes cannot transmit and receive simultaneously on the same channel, 3 and the maximum number of active nodes is fixed and finite. We clarify that a neighbor relation between two nodes need not be bidirectional, since each node discovers those nodes it can receive from.
The organization of this paper is the following. In Section 2 we provide a model for the physical aspects of the networks, and we formulate our problem. ND algorithms are introduced in Section 3, and analyzed in Section 4. Section 5 shows some numerical results, while Section 6 concludes the paper.

Signal model and problem formulation
Our scenario is based on the transmission scheme illustrated in Fig. 1, which corresponds to node 0 searching its own neighbors among four other nodes. 4 In every time interval ("slot"), each node i, i = 0, 1, . . . , K, transmits its own signature, independently of the other nodes, with probability ε i , while otherwise (and hence with probability 1 − ε i ) it senses the channel. This probability is actually designed as a part of the algorithm, and it influences the ND algorithm performance, as we shall examine in our analysis.
The ND algorithm runs in a finite period, called a discovery session, whose duration is denoted T D . During T D , every active node transmits a number of signals containing one or more copies of than running ND periodically as an application program. 2 Note that this definition can be generalized: for example, one may define a neighbor as one whose power-tointerference plus noise ratio exceeds a given threshold. In this paper we stick to a more restrictive definition, which allows simpler algorithms. In general, any information gleaned through ND will help scheduling, or medium-access control, or routing algorithms to be more efficient, because they will be armed with neighbor information. 3 For simplicity, we disregard the more general case of nodes that can be in an idle state, i.e., they are neither receiving nor transmitting. 4 We consider node 0 to be the reference node. Since all nodes are at the same hierarchical level, the same analysis applies to any node. its signature. Each signal has duration T = T D /N, with N the number of slots in the discovery session. The network is assumed to be unsupervised, which implies that all nodes are independent and at the same hierarchical level: as a consequence, the ND algorithm is run in parallel by all nodes. Under the assumptions made in Section 1, the baseband representation of the signal received by node 0 in the time interval (n − 1)T, nT , n ∈ {1, 2, . . . , N}, is where α k denotes the channel gain, i.e., the complex amplitude of the signal received from node k and assumed to be constant during all the discovery session, s k (·) is the kth node signature, ψ k,n is a random variable taking value 1 if node k is transmitting at time n, and value 0 otherwise (so that P(ψ k,n = 1) = ε k ), and z(t) is additive white complex Gaussian noise having spectral density 2N 0 . We assume α k to be modeled by a complex circularly symmetric Gaussian random variable with variance 2σ 2 k . The signatures can be expressed as where s l,k ∈ {−1, +1} is the lth chip of the kth signature, L is the processing gain, T c = T /L is the chip duration, and φ(·) is the (unit-energy) chip waveform. 5 The slots devoted to channel sensing need not be adjacent: however, due to our flat-fading assumption, we may assume, without any loss of generality, a sensing phase of consecutive slots with intermittent other-users activity, with ν 0 the number of slots where node "0" is transmitting. Notice that M 0 is random (N is assumed fixed and node 0 has its own activity factor ε 0 ), but the value it takes is known to node 0. Hence, in all subsequent derivations we refer 5 The signatures are assumed to have unit energy.
Our problem is now reduced to determining the indexes k such that {|α k |} K k=1 exceed an "activity threshold" τ A , based on model (4).
Since z(t) is white Gaussian noise, the components of y(t) orthogonal to the subspace spanned by the signatures are irrelevant to our detection problem [8]. As a consequence, we might in principle adopt the signatures themselves, and their delayed versions, as an expansion basis for such a subspace. Alternatively, we may use the L−dimensional orthonormal basis to expand the signal in the interval (p − 1)T, pT . The two approaches are obviously equivalent, but the latter is mandatory in situations where the discovering node has no prior information as to the signatures of other users: although we do not deal blind ND in this paper, we choose this one due to its inherent flexibility.
Defining the scalar products with * denoting conjugation, we obtain a vector representation y p [y 1,p , y 2,p , . . . , y L,p ] T 7 of the signal received in (p − 1)T, pT : 6 Notice that the index n refers to consecutive time slots, while p refers to the time scale defined by the silent phase of node "0". 7 The symbol T denotes transposition operation The ND problem now consists of assessing, after observing the set of M 0 vectors y 1:M 0 {y 1 , . . . , y M 0 }, which ones, among |α 1 |, . . . , |α K |, exceed the "activity threshold" τ A .

ND algorithms
A sensible criterion for the selection of a ND algorithm consists of minimizing the probability of choosing, among the K network nodes under scrutiny, an erroneous set of neighbors of node 0.
Since there are 2 K such sets, each corresponding to one hypothesis H, this error probability is minimized by the maximum a posteriori (MAP) decision rule: where P (H) is the a priori probability of hypothesis H, and p(y 1:M 0 |H) is the probability density of the observations given H. As an example, if K = 2, the 4 hypotheses are shown in Table 1.
which has a complexity that grows exponentially with KM 0 .
To overcome this complexity obstacle, the decision on the neighbor set works as follows. We first obtain estimates of the instantaneous powers |α i | 2 of all nodes, next we decide that a node is a neighbor by comparing each of them with a threshold, i.e., where H 1 : The received instantaneous power exceeds τ 2 A .
H 0 : The received instantaneous power is below τ 2 A .
The performance of this test can be expressed through its probability P (i) F of a false-alarm and its probability P (i) M of a miss, defined as: These are related to the overall error probability through 8 Now, the maximum-likelihood (ML) estimators of the instantaneous powers can be obtained by jointly estimating α and the matrix sequence with † denoting Hermitian operation. Computing with α i the solution corresponding to Ψ 1:M 0 ,i , and recalling that ML estimates commute under nonlinear transformations, test (10) can be implemented by using Even with this receiver, implementation complexity would be unrealistic, and hence a further simplification is called for. Instead of dealing with the receive/transmit pattern related to the whole discovery session, we rather obtain estimates based on a single T -interval observation, which are then combined according to a suitable integration strategy.

Suboptimum ND algorithms
Consider again model (7). The ML estimate of Ψ p α, based upon the observation y p available in slot p, is where S + denotes the pseudo-inverse of the tall matrix S.
A closer look at this solution reveals that, since the interference from the other users is completely eliminated, at the price of some noise enhancement, reflecting the increase of the variance of its ith compo- It is interesting to notice that this estimate is noise-limited, but not interference-limited, implying that any receiver based on (15) is asymptotically efficient [10]; likewise, near-far resistance is granted [10].
Since there are M 0 sensing phases, the M 0 estimates resulting from repeated application of (15) should be combined to yield the final test statistic. Borrowing techniques from radar detection theory, reasonable combination criteria are coherent integration (CI), wherein an estimate of the instantaneous power is obtained as and incoherent integration (II) Notice that implying that both |α i | 2 II and |α i | 2 CI can be interpreted as biased estimators of the instantaneous power received in each slot from node i: biases can however be absorbed in the detection thresholds τ i , while what matters here is that they are both consistent in the mean square sense, a property that will be exploited later on. Inserting (17) and (18) into (10), and skipping factors that can be absorbed in the detection thresholds, we obtain the coherent detector (CD) and the Incoherent Detector (ID): DA, EB, ML: Neighbor Discovery in Wireless Networks February 5, 2008 Notice how the CD can also be interpreted in a different way. Indeed, it may be obtained by first pre-processing the observations so as to form the cumulative sum: and V diag(ν 1 , . . . , ν K ), then multiplying the new observation by S + and finally extracting the ith component to form the test statistic (21). Rewriting equation (23) in the form: , where I L is the L × L identity matrix, the CD is easily seen to be a member of the family of linear ND tests (LNDT), wherein a decision on the proximity of user i is made based on the rule: Thus, the CD (21) can be also interpreted as the zero-forcing (ZF) member of the family (26), obtained as the unique solution to the constrained minimization problem: with β = 0, which yields 9 where S i is the L × (K − 1) matrix obtained skipping the i−th column from S and P i denotes the projector onto the orthogonal complement of the column span of S i . For future reference we 9 Notice from (28) that the parameter β 2 has been set to where s i,⊥ denotes the projection of s i on the above orthogonal complement: needless to say, since , the noise power is enhanced by a factor (S † S) −1 i,i . The vector c i can be designed according to a number of different criteria. For example, in [12] an LNDT based on conventional matched filtering (MF), i.e., assuming has been proposed and analyzed for ND [12]. MF is indeed simple, but it results into interferencelimited performance, as we shall prove soon, nor does it retain the near-far resistance property granted by ML-based detectors.
A possible alternative to the ZF criterion is offered by the minimum-mean-output-energy (MMOE) strategy, first introduced in [11], wherein the vector c i is obtained as the unique solution to the following constrained minimization problem: namely: Due to the invariance of the decision rule to any positive scaling of the test statistic, an equivalent detector relies upon setting It might be worth recalling here that, since MMOE is itself asymptotically efficient. Likewise, it retains the near-far resistance property since the projection direction c i,M M OE tends to become orthogonal to those signatures whose amplitudes become increasingly large [11]. The advantage of (33) over ZF is that it easily lends itself to adaptive implementations in situations where the signatures of the active users are unknown. Even though we do not deal with adaptive ND in this paper, we anticipate that a number of reduced complexity algorithms, ranging from the O(L)-complex Least Mean Squares to the O(L 2 )-complex Recursive Least Squares, can be easily applied for adaptive MMOE implementation.

Analysis
From now on we assume that the node to be detected is node "1". Consider first the ID. The conditional false-alarm and miss probabilities in assessing the proximity of node 1 can be written as: with χ 1 M 0 p=1 |(S + y p ) 1 | 2 . Given |α 1 | and Ψ 1:M 0 , χ 1 is noncentral chi-square distributed with 2M 0 degrees of freedom and parameters ν 1 |α 1 | 2 and σ 2 n,1 = (S † S) −1 1,1 N 0 , implying where Q M 0 (·, ·) is the Marcum function of order M 0 . Using the series expansion of modified Bessel functions we obtain are the upper incomplete Gamma function and its regularized version, respectively, while ρ 1 is the signal-to-noise ratio after decorrelation, i.e.: We thus obtain the conditional measure: which should be averaged over ν 1 to yield the conditional probability of a miss given M 0 . Similar developments hold for P F , yielding are the lower incomplete Gamma function and its regularized version, respectively. Finally, from (43) we easily obtain: Consider now the test family (26). Notice that, since |g 1 | 2 is conditionally chi-square with two degrees of freedom, given α 1 , whereby, reproducing the same steps leading to (42) and (45), we obtain: where ρ eq represents the signal-to-interference-plus-noise ratio (SINR) at the output of the linear filter, i.e.: Relationships (48) and (49) are quite reminiscent of (42) and (45), respectively, one major difference being the dependency of the performance on ν 2 1 ρ eq , rather than ν 1 ρ 1 . Of course, the quadratic factor in ν 1 stems from the fact that linear detectors operate on a coherent combination of the observations, while ID combines the slot-by-slot estimates incoherently. Notice, however, that the above relationships represent conditional measures, given M 0 (i.e., given ν 0 ) and {ν i } K i=1 . If the discovery session is long enough, so that the matrix sequence Ψ 1:M 0 may exhibit its typical behavior, namely, if N(1−ε 0 ) ≫ 1, then the ν k 's tend in probability to M 0 ε k , whereby the unconditional performances may be obtained by averaging the corresponding conditional measures on the typical set of values of {ν k } K k=1 and M 0 only, implying: In this limiting situation, it is interesting to notice the relationship between the "cumulated" SNR's for ID and CD (i.e., the ZF of (28)), i.e. (see also (29) and subsequent comments): Thus, in terms of cumulated signal-to-noise ratio and for large N, ID seems to be preferable to CD, even though a global superiority cannot be claimed due to the different forms assumed by the respective false-alarm and miss probabilities.
So far no criterion has been given to select the decision threshold τ 1 . Notice, however, that the consistency of the estimates (17) and (18) allows devising the asymptotically optimum thresholds (those achieving minimum error probability for large N) from (19) and (20) in the form: For short discovery sessions, and under known activity factors of nodes to be discovered, optimum detection thresholds can be obtained by evaluating numerically the unconditional error probability, and then determining the points where it has a minimum.

Results
We consider here a fully loaded network with K + 1 = 7, each node being assigned a length-7 m-sequence. As in the previous section, we assume that node "0" has to decide on the proximity of node 1. Figure 2 assumes SNR 1 σ 2 1 /N 0 = 0 dB, N = 100, a power-controlled scenario wherein all nodes are received with the same average power, uniform activity factor (ε k = ε = 0.5), and an activity threshold equal to the median of the fading amplitude distribution, i.e., such that P(|α 1 | > τ A ) = 0.5. The figure represents the pair P M , P F for the various receivers examined so far. Interestingly, "conventional" MF suffers from the presence of the other nodes even in this rather benign situation, while MMOE, ZF (which coincides with CD rule) take advantage of their asymptotic efficiency: from now on, conventional MF will not be considered any longer. The interested reader is deferred to [12] for a fairly thorough performance assessment.
The reliability of the asymptotic approximation for long discovery sessions can be assessed through figures 3-5 for the CD, and through figures 6-8 for the ID, which refer to the same scenario as in Fig. 2. The curves of these figures represent: -The unconditional false alarm and miss probabilities obtained by simulation.
-The same pair obtained by a semi-analytical method, i.e., by estimating the averages of their conditional counterparts.
From the plots, it is evident that the asymptotic approximation tends to overestimate the performances in the interesting region of low error probabilities, while coming closer and closer to the true performance as N increases: notice that the approximation is extremely tight for N = 500, a realistic value indeed in real applications, which, for ǫ 0 = 0.5, corresponds to M 0 ≃ 250. However, it should be kept in mind that, for larger activity factors of the discovering node, the minimum value of N for the asymptotic behavior to be reached inevitably increases.
The validity of the approximations (52) and (53), yielding the asymptotically optimal thresholds for CD and ID, respectively, can be verified through Figs. 9 and 10, showing P (e) versus τ 1 for CD and ID, respectively, for some values of SNR 1 , ε=0.5, N = 500 and τ A such that P(|α 1 | > τ A ) = 0.5. These plots, obtained numerically, show that the error probability admits a unique minimum; moreover, the optimal values of τ 1 are surprisingly close to those resulting from an optimum value is practically independent of SNR 1 for CD, while being strongly tied to SNR 1 for ID. Fig. 11 is aimed at comparing CD and ID. It represents the error probability versus the signalto-noise ratio SNR 1 using the optimal thresholds for both receivers, and assuming again ε = 0.5, N = 500, and τ A as before. It is interesting to notice that CD outperforms ID for small signal-tonoise ratios, while ID is preferable for medium-to-large values of SNR 1 .

Conclusions
We have examined the problem of discovery which nodes are neighbors in a wireless network operating over a fading channel. The optimum Bayesian decision rule has been derived, showing that its complexity is practically prohibitive. Two suboptimum neighbor-discovery algorithms have been introduced, based on standard techniques of coherent and incoherent integration. We show how coherent integration may be viewed as a particular case of a family of algorithm akin to Linear Neighbor Discovery Tests (LNDT). Theoretical analysis allows one to understand the design of a system employing such algorithms according to constraints on error rate, signal-to-noise ratio and discovery session duration. Finally, algorithm optimization was considered, and formulas were derived for asymptotical optimum threshold.