Multiple—Symbol Differential Decision Fusion for Wireless Sensor Networks by Andre Lei B.A.Sc, University of British Columbia, 2005 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) April 2009 © Andre Lei, 2009 Abstract We consider the problem of decision fusion in mobile wireless sensor networks where the channels between the sensors and the fusion center are time—variant. We assume that the sensors make independent local decisions on the M hy potheses under test and report these decisions to the fusion center using dif ferential phase—shift keying (DPSK), so as to avoid the channel estimation overhead entailed by coherent decision fusion. For this setup we derive the optimal and three low—complexity, suboptimal fusion rules which do not re quire knowledge of the instantaneous fading gains. Since all these fusion rules exploit an observation window of at least two symbol intervals, we refer to them collectively as multiple—symbol differential (MSD) fusion rules. For bi nary hypothesis testing, we derive performance bounds for the optimal fusion rule and exact or approximate analytical expressions for the probabilities of false alarm and detection for all three suboptimal fusion rules. Simulation and analytical results confirm the excellent performance of the proposed MSD fu sion rules and show that in fast fading channels significant performance gains can be achieve by increasing the observation window to more than two symbol intervals. 11 Contents Abstract 11 Contents iii List of Figures vi List of Abbreviations . Operators and Notations VII’ x xi 2.2 Differential Detection 2.2.1 Multiple—Symbol Differential Detection 12 Acknowledgments . . 1 Introduction 1.1 Wireless Sensor Networks 1.2 Decision Fusion Literature Review 1.3 Thesis Contribution and Organization . 1.4 Related Publications 2 System Model arid Differential Detection 2.1 System Model 2.1.1 Processing at Sensors 2.1.2 Channel Model 2.1.3 Fusion Center Processing 1146899 10 11 12 12 111 2.2.2 Multiple—Symbol Differential Sphere Decoding 14 18 18 20 21 25 29 29 31 32 34 5 Numerical and Simulation Results . 5.1 Binary Hypothesis Testing 5.1.1 Error Probability 5.1.2 Constant False Alarm Probability 5.1.3 Receiver Operating Characteristic 5.1.4 Effects of Sensor Network Size 5.2 Multiple Hypothesis Testing 5.2.1 Error Probability Independent, Non—identically Distributed Effects of Sensor Reliability 5.2.4 Estimation Error of Channel Correlation Matrix 5.3 Computational Complexity 6 Conclusions and Future Work 6.1 Research Contributions 6.2 Future Work 3 Multiple—Symbol Differential Decision Fusion . 3.1 Optimal Fusion Rule 3.2 Chair—Varshney (CV) Fusion Rule . . 3.3 Fusion Rule for Ideal Local Sensors (ILS) 3.4 Max—Log Fusion Rule 4 Analysis of Suboptimal Fusion Rules . 4.1 Performance Bounds 4.2 CV Fusion Rule 4.3 ILS Fusion Rule 4.4 Max—Log Fusion Rule 40 40 41 43 44 45 47 48 50 52 5.2.2 5.2.3 Fading . . 53 54 56 56 57 iv Bibliography.58 V List of Figures 1.1 Wireless sensor network with K sensors: (a) Centralized scheme (b) Decentralized scheme 2 1.2 Serial topology sensor network 3 1.3 Tree topology sensor network 4 2.1 System model for MSDHT decision fusion 10 2.2 Sphere decoding illustration for differential block of N 4. . . . 17 4.1 Illustration of relationship between Zk and y for a = 1. Note that with the definitions in Section 4.4, b1 < 0, b2 > 0, /3 < 0, and/33>OaslongasPd>0.5andPf<0.5 35 5.1 Probability of error Fe vs. Eb/No for decision threshold ‘Yo = 0. K=8,M=2,Pd=0.8,Pf—0.01,BT=0.1,and i.i.d. Rayleigh fading 42 5.2 Probability of error Fe vs. Eb/No for decision threshold ‘yo = 0. K = 8, M = 2, Pd = 0.8, Pf = 0.01, BT = 0, and i.i.d. Rayleigh fading 43 5.3 Probability of detection Pd0 vs. Eb/No for a probability of false alarm of Pf0 0.001. K = 8, M = 2, Pd = 0.7, Ff = 0.05, BT = 0.1, and i.i.d. Rayleigh fading 44 5.4 Probability of detection Pd0 vs. probability of false alarm Ff0. K=8,M=2,Fd=0.7,Ff=0.05,BT=0.1,Eb/No=20 dB, and i.i.d. Rayleigh fading 45 vi 5.5 Probability of error Pe vs. number of sensors K. M = 2, Pd = 0.7, Pf 0.05, BT = 0.1, Eb/No = 20 dB, and i.i.d. Rayleigh fading 46 5.6 Probability of detection Pd0 vs. number of sensors K for a proba bility of false alarm of Pf0 = 0.001. M = 2, Pd = 0.7, Pf = 0.05, BT = 0.1, Eb/No 20 dB, and i.i.d. Rayleigh fading 47 5.7 Probability of missed detection Pm VS. Eb/No. M = 4, BT = 0, SNRS = —3 dB, and i.i.d. Rayleigh fading 48 5.8 Probability of missed detection Pm vs. Eb/No. M = 4, BT 0.1, SNR8 = —3 dB, and i.i.d. Rayleigh fading 49 5.9 Probability of missed detection Pm vs. Es/No for lbS fusion rule. M = 4, BT = 0.1,, i.i.d. Rayleigh fading, and SNR8 = —5 dB, —3 dB,0 dB,3 dB 50 5.10 Probability of missed detection Pm vs. Es/No. M = 4, BT = 0.1, SNR8 = —3 dB, and i.n.d. Rayleigh fading 51 5.11 Probability of missed detection Pm vs. SNR8 M = 4, BT = 0.1, Eb/No = 30 dB, and i.n.d. Rayleigh fading 52 5.12 Probability of missed detection Pm vs. Eb/No with channel cor relation error. M = 4, BT = 0.1, SNR8 = —3 dB, and i.i.d Rayleigh fading 53 5.13 Number of real multiplications per decision vs. Eb/No. M = 4, SNR8 = —3 dB, and i.i.d. Rayleigh fading 55 vii List of Abbreviations AWGN Additive white gaussian noise BER Bit error rate BHT Binary hypothesis testing CSI Channel state information CV Chair—Varshney DD Differential detection DPSK Differential phase—shift keying FC Fusion center FSK Frequency—shift keying ILS Ideal Local Sensor MHT Multiple hypothesis testing ML Maximum-likelihood MSD Multiple—symbol differential MSDD Multiple-symbol differential detection MSDSD Multiple-symbol sphere decoding MSDHT Multiple—symbol differential hypothesis testing 00K On—off keying PBPO Person by person optimization pdf Probability density function PEP Pairwise error probability PSK Phase—shift keying viii TDMA Time—division multiple access ROC Receiver operating characteristic RTS Repeated tree search SD Sphere decoding SE Schnoor—Euchner SNR Signal—to—noise ratio STS Single tree search WSN Wireless sensor network ix Operators and Notations HI Absolute value of a complex number Complex conjugate [.]T Matrix or vector transposition [.]H Matrix or vector Hermitian transposition R {.} Real part of a complex number t’ {} Statistical expectation Dirac delta function ü [•] Unit step function [X]3 Element of matrix X in row i and column j det (.) Determinant X x X identity matrix Kronecker product diag{Xi,. , Xx} Block diagonal matrix with matrices X1,. , Xx on its main diagonal P (.) Probabilities p (.) Probability density function x Acknowledgments Foremost, I would like to thank my supervisor, Dr. Robert Schober, for the constant guidance and support that he has provided. Without his helpful suggestions, advice and constant encouragement, this work would not have been possible. I would also like to thank my friends and colleagues for all the discussions, advice and laughter that we have shared throughout the years. Not only have you all helped me keep my perspective, but also my sanity during my ups and downs. Finally, I would like to thank my family who have always encouraged me and given their unconditional support throughout my studies at the University of British Columbia. ANDRE LET xi Chapter 1 Introduction 1.1 Wireless Sensor Networks Wireless sensor networks (WSNs) have been a topic of much interest because of their miliary and civilian applications which include target tracking, envi ronmental monitoring, control, and spectrum sensing [1—5]. Recently advances in the development of low-cost microsensors and an increased interest in cog nitive radio have renewed interest in WSNs and the decision fusion problem [6, 7]. In civilian applications, low-cost microsensors can be deployed for envi ronmental sampling, surveillance, and habitat monitoring, allowing WSNs to be used to solve various problems in different fields. For example, it has been shown that licensed spectrum is frequently underused [8]. Spectrum sensing can be employed to identify unused spectrum and thereby allow cognitive ra dios to operate when licensed users are idle, enabling more efficient use of the limited spectrum [4, 5, 9, 10]. Both spectrum sensing and cognitive radios depend on decision fusion, which provides a fault-tolerant and robust method of detection while also increasing detection performance by using observations from multiple sensors to arrive at a more reliable decision than can be achieved by individual sensors. 1 a) Figure 1.1: Wireless sensor network with K sensors: (a) Centralized scheme (b) Decentralized scheme. WSNs can be centralized or decentralized. Fig. 1.la shows a centralized sensor network containing K sensors and Fig. 1.tb shows a decentralized sensor network. In centralized detection, each sensor collects the information of inter est denoted by Xk [n] and transmits its raw observation to the fusion center (FC) for processing. Fusion within a centralized scheme is solved by classical hypoth esis testing, which makes a global decision on the current phenomenon being observed, i.e., the hypothesis under test H, i e M, M {O, 1,..., M — 1} [11]. Classical papers by Tenney, Sandell [12] and Tsitsiklis [13] introduced the decentralized detection problem, where sensors make independent deci sions based on signal processing of their individual observations. The decision, 8k [n], is then transmitted to the FC to arrive at a final estimate of H, i e M. Since the processing performed by both the sensors and the FC is threshold based [13], optimizing the system requires jointly optimizing the thresholds at all the sensors and the FC simultaneously, and is thus a complex problem. To reduce the complexity, a person by person optimization (PBPO) method is frequently used [11], which satisfies the necessary condition for optimality but does not guarantee a global optimal solution. PBPO attempts to optimize the processing at each sensor independently by fixing the processing rules at all H; 2 Phenomenon H, x1[ri] XK[fl] Sensor 1 Sensor 2 SK_1[fl] Sensor K Figure 1.2: Serial topology sensor network. other sensors and the FC while one sensor is being optimized. This process is repeated for the remaining K — 1 sensors and the FC. Although centralized detection performs best, each sensor is burdened with transmitting raw data to the FC, resulting in large power consumption and large communication bandwidth requirement. Therefore, in a wireless situation where sensors are battery operated and communication resources are limited, the decentralized scheme is of particular interest. In general there are three common WSN topologies, namely parallel, serial and tree [1]. The parallel configuration in Fig. 1.lb is the most common type of WSN considered in literature. K sensors receive a noisy observation of the phenomenon H denoted by xk[n] and, after processing the information, transmit their local decisions, sk[n], to the FC. The FC then makes a global decision based on the decision of K sensors and not the observations of each individual sensor, Xk [n]. Fig. 1.2 illustrates a general WSN in serial configuration. The 1st sensor within the WSN processes only its own observation whereas the remaining K — 1 sensors process both their own observations and the decisions made by the previous sensors. Thus, the kth sensor will fuse its observations with the decision from the (k — 1)th sensor to generate its own decision. The aggregated data, or the final decision, is presented by the Kth sensor of the WSN. A WSN in a tree topology is shown in Fig. 1.3. In its simplest form, 3 Phenomenon H 7nj x Sensor 1 Sensor 2 • , Sensor ( si[n] /s2[nJ xrKi+i[nj - - s11l[n] SK_1[flj. S[K][fl] XK[fl] I Sensor K Figure 1.3: Tree topology sensor network. sensors observe a phenomenon and transmit their decisions, Sk [nj, to the next sensor. The remaining [jJ sensors not only make their own observations of the phenomenon, but also receive a decision, Sk [n], from two sensors. Decision fusion is applied and the resultant decision after fusion is transmitted to the next sensor. The global decision is obtained at the E*lth level of the tree. 1.2 Decision Fusion Literature Review As mentioned previously, decentralized detection is an important task in WSNs [1, 11, 12, 14]. To limit complexity, the sensors usually make independent de cisions based on their respective observations and forward these decisions over 4 the wireless channel to a FC, which makes a final decision on the hypothe sis under test. Most of the existing literature on the decentralized detection problem assumes ideal error—free communication between the sensors and the FC. While this is a reasonable assumption for wired sensors, significant perfor mance degradations may occur if wireless sensors are employed. Therefore, the problem of fusing sensor decisions transmitted over noisy fading channels has received considerable interest recently. For example, channel aware decision fusion for phase—coherent WSNs employing phase—shift keying (PSK) modu lation was investigated in [15, 16]. In [17], channel statistics based fusion rules for WSNs employing on/off keying (00K) modulation were considered. The impact of fading on the performance of power constrained WSNs was stud ied in [18]. In [19], the performance of type—based multiple access strategies for fading WSNs was analyzed. Furthermore, the problem of optimal power scheduling and decision fusion in fading WSNs with amplify—and—forward pro cessing at the sensors was considered in [20]. Most recently, the impact of channel errors on decentralized detection was studied for PSK, 00K, and frequency—shift keying (FSK) modulation in [21]. Interestingly, existing work on decision fusion for noisy fading channels has mainly considered coherent (e.g., PSK) and noncoherent (e.g., 00K, FSK) modulation schemes. While the former are suitable for static fading channels, the latter are appropriate for extremely fast fading channels, where the fad ing gain changes from symbol to symbol due to e.g. fast frequency hopping. However, for applications where the fading gains change slowly over time due to the mobility of the sensors and/or FC, noncoherent modulation may not be a preferred choice due to the inherent loss in power efficiency compared to coherent modulation. On the other hand, coherent modulation requires the insertion of pilot symbols for channel estimation, which reduces spectral effi ciency and complicates system design. Thus, for conventional point—to—point communication systems, differential PSK (DPSK) is often preferred for sig 5 naling over time—varying fading channels [22]. While DPSK does not require instantaneous channel state information (CSI) for detection, the performance loss compared to coherent PSK can be mitigated by multiple—symbol differ ential detection (MSDD) if statistical CSI is available at the receiver [23—25]. This motivates the investigation of DPSK for transmission in WSNs and the design of corresponding fusion rules. 1.3 Thesis Contribution and Organization This thesis will consider the parallel topology shown in Fig. 1.lb, which has received the most interest in the literature, and make the following contribu tions: 1. Formulate the parallel decentralized M—ary hypothesis testing problem in time—variant fading channels. 2. Propose fusion rules that require at most statistical CSI but not any knowledge about instantaneous channel gains. 3. Consider fundamental limits on wireless sensor network performance by investigating performance upper bounds. 4. Estimate probabilities of false alarm and detection for some proposed fusion rules via analytical expressions. The following chapters will discuss the above contributions in detail. Chapter 2 introduces the system model for a parallel WSN where sensors employ M—ary DPSK (M-DPSK) to report their local decisions to the FC. The chapter will also briefly review MSDD of M—DPSK signals and explain the use of sphere decoding to reduce the complexity of MSDD. The latter concept is referred to as multiple—symbol sphere differential decoding (MSDSD). 6 In Chapter 3, the M—ary hypothesis testing problem is considered and the optimal multiple—symbol differential (MSD) fusion rule for sensors employing differential encoding is derived. The optimal fusion rule is found to be expo nential in both the number of sensors and the observation window size used for MSD decision fusion, and therefore we propose three suboptimal fusion rules with significantly lower complexity and good performance. All proposed fusion rules in this thesis only require statistical CSI but not any knowledge about the instantaneous channel gains. Chapter 4 considers the special case of (M = 2) binary hypothesis testing (BHT) and derives performance bounds valid for the proposed fusion rules. The two performance upper bounds consider the limiting cases, i.e., when the sensors are perfect and when the channel between the sensors and the PC is perfect. Additionally, exact or approximate analytical expressions for the probabilities of false alarm and detection for the suboptimal fusion rules are derived. The analysis allows the system performance to be estimated without resorting to time consuming simulations of the receiver characteristic curve (ROC) for each fusion rule. In Chapter 5, simulation and, where possible, numerical results are pre sented for the special case of BHT and the more general case of 4—ary multiple hypothesis testing (MHT). The performance gains achieved by increasing the observation window size, N, of the MSD fusion rules to more than two sym bols is shown to be significant. In particular, the performance of coherent detection with perfect knowledge of the channel gains can be approached for large enough observation window sizes. Finally, in Chapter 6 we provide some conclusions for this thesis, as well as several proposals for future work based on the results presented herein. 7 1.4 Related Publications • A. Lei and R. Schober. Multiple—Symbol Differential Decision Fusion for Mobile Wireless Sensor Networks. Submitted to the IEEE Transactions on Wireless Communications, Mar. 2009. • A. Lei and R. Schober. Multiple—Symbol Differential Decision Fusion for Mobile Wireless Sensor Networks. Submitted to IEEE GLOBECOM 2009, Mar. 2009. 8 Chapter 2 System Model and Differential Detection In this chapter, we introduce the WSN system model under consideration. Within the WSN, we will consider the transmission scheme used by the sensors, the fading and noise model used to model the corrupted signal observed by the FC and consider how the signal can be processed by the FC. Moreover, MSDD will also be considered in this chapter, focusing on a lower complexity alternative to MSDD referred to as MSDSD. 2.1 System Model Consider the parallel distributed multiple hypothesis testing problem where a set i’C {1, 2, ..., K} of K sensors are used to decide which one out of M possible hypotheses H, i e M, M {O, 1,..., M — 1}, is present. The a priori probability of hypothesis H is denoted by P(Hj, i M. Fig. 2.1 illustrates the system model which will be discussed in detail in the following subsections. 9 Detection ; uj[n] Mapping C a1[n] Diff. Enc. Detection UK[fl] Mapping C!) aK[n] Diff. Enc. Isi[n] ISK[flj Flat Flat Fading Fading Channel Channel •/ form blocks Yk[nl MSDHT 1 Figure 2.1: System model for MSDHT decision fusion. 2.1.1 Processing at Sensors At time n e each sensor k e )C makes an M—ary decision Uk [nj based on its own noisy observation Xk [n]. We assume that the K observations Xk [n], k e IC, are independent of each other, conditioned on the M different hypotheses. The sensors map their local decisions to M—ary PSK (M—PSK) symbols ak [n] {wIi e M}, wj ej2/M, such that hypothesis H corresponds to the PSK symbol w. The differential phase symbols ak[nj are differentially encoded before transmission over the wireless channel to obtain the absolute phase symbols Sk[fl] = ak[njsk[n — 1], (2.1) ... 10 where sk[fl} E {wIi e M}. This differential encoding operation facilitates detection without CSI at the receiver which is particularly useful for trans mission over time—variant fading channels [22]. In the context of WSNs, such time—variant channels may arise for example in vehicular WSNs with mobile sensors and/or mobile fusion centers [2], battlefield surveillance [3], or collab orative spectrum sensing with mobile nodes [9]. To keep our model general, we quantify the quality of the local decisions made by the sensors in terms of conditional probabilities Pk(ak[n] = wlH), i E M, j e M, k e C. 2.1.2 Channel Model The sensors communicate with the fusion center over orthogonal fiat fading channels using e.g. a time—division multiple access (TDMA) protocol. The received signal from sensor k at time n is given by Yk[T1] = /Phk[n]sk[n] + flk[fl], (2.2) where PK P/K with total transmitted power P, and hk [n] and k [n] de note the fading gain and zero—mean complex—valued additive white Gaussian noise (AWGN), respectively. The noise is independent, identically distributed (i.i.d.) with respect to both the sensors, k, and time, n, and has variance E { k [n] 2 } We assume independent, non—identically distributed (i .11. d.) Rayleigh fading with fading gain variances u E { I hk [n] 2 }, k e 1C. For the temporal correlation of the fading gains, we adopt Clarke’s model with cphh,k[)’] {hj[n + A]h[n]} = u Jo(27rBkTA), where Bk denotes the Doppler shift of sensor k and T denotes the time interval between two observations yk[n] and Yk [n + 1]. Note that if the sensors use TDMA to report their observations in a round—robin fashion to the fusion center, T is equal to T KT8, where T3 is the symbol duration. It is also interesting to observe that the effective Doppler shift BkT increases with decreasing data rate since T increases with decreasing data rate. 11 2.1.3 Fusion Center Processing Since the differential encoding operation in (2.1) introduces memory, symbol— by—symbol information fusion is not optimum. Instead, results from point— to—point communication systems suggest that the received signals should be processed on a block—by—block basis [23—25] and will be briefly discussed in the next section. Here, we adopt the same philosophy for information fusion and process blocks of N received signals Yk [yk[n—N+i] yk[n—N+2] •.. corresponding to blocks of N—i differential symbols ak [ak [n — N + 2] ak [n — N + 3] ... ak[n]]T, k e icC. Based on these blocks of received signals any one of the N — 1 differential symbols in ak can be detected and the corresponding MSD fusion rules will be discussed in the next chapter. 2.2 Differential Detection The detection of M—DPSK signals in point—to—point links can be accomplished easily by processing blocks of received symbols of length N = 2, and consider ing the phase difference between the current received symbol and the previous received symbol. This detection is known as conventional DD. However, as mentioned previously, if channel statistics are known, MSDD can be used to exploit the memory of the wireless channel thereby improving error per formance. Moreover, a low complexity algorithm known as MSDSD can be applied for detection of DPSK signals. 2.2.1 Multiple—Symbol Differential Detection The problem of MSDD of M—DPSK in additive white Gaussian noise has been addressed by Divsalar et al. in [23, 25]. Extensions to fading channels have been considered in [24], noting in the face of time—varying channels, conventional DD is limited by an error floor and the effects can be mitigated by 12 MSDD. Performance improvement over conventional DD is achieved by jointly detecting blocks of N received symbols simultaneously, thereby exploiting the correlation between phase distortions experienced by neighboring symbols [24, 26]. Adopting the previous notation and ignoring the subscript k for a single user point—to—point system, the received signal at the receiver is = + n, (2.3) where Sdiag{s[n—N+1]s[n—N+2]...s[n]},h[h[n—N+1]h[n—N+ 2] ... h[n]]T and n [n[n — N +1] n[n — N +2] ... []]T. With the received vector y being a Gaussian random vector process, the conditional probability density function of y, given the blocks of N — 1 differential symbols a, is given by [24] p(ya) = Ndt(R) exp (_rHR_lr). (2.4) Here, r [r[n — N + 1] r[n — N + 2] ... r[n]]T with r[n] y[n]s*[n] and R = PRhh+oIN, where [Rhh], = yhh[j—i]. To simplify our notation, we will address in the following the vth element of vectors y and a by y(v), 1 v N, and a(v), 1 ii N — 1, respectively. The maximum—likelihood (ML) decision for a requires maximizing (2.4). Eliminating all irrelevant terms, this is equivalent to maximizing a = argmax {_r”R’r} = argmax {2{ t,y()y*(v) [J a()}}a a 11=1 ii=ii+1 (2.5) where t, — [R’],L,,,. If blocks of received signals are properly processed, performance improves as the block size N 2 increases and approaches the performance of coherent detection for N —* cc [23, 26]. Applying (2.5) requires computing the argument for each candidate vector a, i.e., computational com plexity grows exponentially with N. To reduce the computation complexity of this problem, MSDSD was proposed in [27]. 13 2.2.2 Multiple—Symbol Differential Sphere Decoding The purpose of adopting sphere decoding is to reduce the number of candidate vectors a considered without excluding the ML solution. Considering again (2.5), maximization with respect to a is equivalent to maximization with re spect to the absolute phase symbols s [s(1) s(2) ... s(N)]T given that the phase ambiguity is fixed, e.g., s(N) = 1. The ML decision is equivalent to = argmin {SHUHUs} = argmin {IUsII2}, (2.6) s,s(N)=1 where U c (LFdiag{y})* is an upper triangular matrix and L is a lower triangular matrix obtained from the Cholesky factorization of R’ LLH [27]. The sphere decoder considers all candidate vector s that lie within a sphere of radius R, SHUHUS R2. (2.7) Since U is an upper triangular matrix, MUsh2 can be partially computed given some elements within s are fixed. Assuming (preliminary) decisions (1) for the last N — 1 components s(1), ‘‘ + 1 < 1 < N, we define the squared length N N 2 d1 = u1(t) . (2.8) t=v+1 u—1 For possible values of s(v), the condition N 2 d = us(v) + > u,(i) + d1 R2, (2.9) must be satisfied, where the computation of (2.9) uses the partially computed squared length d1 accounting for the squared length of the last N — 1 com ponents. For any s(v) with d > R2, any symbol s(l) for 1 < 1 < v — 1 will also have d > R2 and therefore can be eliminated early in the search process. Once a vector . is found to satisfy (2.7), the radius is updated to reflect the new radius, R2 = IIUhI2. This is repeated until no vector s is within a sphere 14 of radius R and the ML solution . is obtained. The algorithm is shown in [27, Fig. 1]. Fig. 2.2 shows a binary tree to illustrate the search for . in a 2—DPSK system with N = 4. The root node of the tree is a node without parents and represents the initial search, i.e., when s(N) = 1, to fix the phase ambiguity. Any nodes in the tree excluding the nodes at the top and bottom level of the tree can be referred to as either a parent or a child since these nodes spawn from nodes at a higher level of the tree and the nodes themselves can spawn M child nodes at a lower level. The last level (ii = 1) of the tree consists of only leaf nodes, nodes that do not have any children. MN_i leaf nodes represent the number of possible candidate vector s. In Fig. 2.2, the vectors [s(N — 1),... s(v + 1) s(zi)]T are provided beside each node. The following illustrates a search for the ML solution. 1. Starting at the root node, the Schnoor—Euchner (SE) search strategy is applied to estimate the node with the minimum incremental length, i.e., us(v) + and moves to that node [28]. This is repeated until a candidate is found, and the radius is updated. The initial search always produces one if R —* oo. As a result of the SE algorithm, M — 1 nodes can always be eliminated at the bottom level of the tree (ii = 1). Fig. 2.2a shows a possible path traversed by the sphere decoder. 2. Once a candidate is found, the search is repeated by moving up one level (v = 2) and M— 1 other child nodes spanned by the same parent are considered. We want to consider the next best child node that has the shortest incremental length other than the current .(v). This is shown in Fig. 2.2b. The squared length, d, at this new node is computed using (2.9) and compared with R. 3. In Fig 2.2c, it is assumed that d at this new node computed in step 2 15 is greater than R. Since (2.9) is not satisfied, all child nodes that are spawned from this node can be eliminated and they are not a possible ML solution. Furthermore, it is known from step 2 that the considered node has the next smallest incremental distance compared to (t’). As a result, the remaining M — 2 nodes considered in step 2 can also be eliminated since they, like the current node, would also not satisfy (2.9). Thus, we must move up one level (v = 3) and consider again child nodes that are spawned from the same parent. 4. Fig. 2.2d shows a new & satisfying (2.7). This new a is selected as the current best ML solution and the radius is updated. The previous . can then be eliminated as the ML solution. 5. Repeating step 2, another node must be compared to consider other candidate . that satisfy (2.7) to ensure no s is excluded, otherwise the solution obtained by the SD maybe sub—optimal. Fig. 2.2e shows that there are still 2 possible candidates. 6. Fig. 2.2f assumes that the squared length computed in the previous step does not satisfy (2.9) and therefore no other candidate s is left and obtained from step 4 is the ML solution. As illustrated in the above example, SD can reduce the complexity of MSDD by eliminating unnecessary comparisons. However, as will be shown later, the number of eliminations will depend on the channel signal—to-noise ratio (SNR). At low SNR the complexity of MSDSD is still quite high but decreases rapidly as channel SNR increases. Although methods such as early terminate [29] and K—best [30] algorithms have been proposed as a means to reduce complexity by finding a sub—optimal solution, we will only consider the case where R —* oc and the search terminates only when the ML solution is obtained. 16 S. + -r /‘&:; / I /1 / I / / I ,‘ ‘., N’j __—i+i II -r . ‘ -r I ++ r-rI I I I I I I I I —I III Iii Iii differential block of N = 4. / I. I Iii IIi Iii Figure 2.2: Sphere decoding illustration for 17 Chapter 3 Multiple—Symbol Differential Decision Fusion In this chapter, the optimal and several suboptimal fusion rules for the system model introduced in Chapter 2 will be derivied. For this derivation, it will be assumed that the fusion center has knowledge of both the statistical properties of the channel and the performance index Pk(ak[n] = wIH), i e M, j e M, of the sensors k e 1C. However, as will become clear in the following, for some of the considered fusion rules one or both of these conditions can be relaxed. We denote the indices of the differential symbols considered for detection by 1)0, e {1, 2, ..., N — 1}. To simplify the notation, we will drop the index of the differential symbol considered for detection wherever possible and denote it by ak = ak(vo). 3.1 Optimal Fusion Rule The optimal fusion rule based on the observations. y [yf y ... can be formulated as = argmax {log(P(Hy)) + o}, (3.1) H, ieM 18 where o, is a bias term which allows the prioritization of certain hypotheses. A bias may be useful for example in applications such as spectrum sensing for a cognitive radio where a missed detection is less desirable than a false alarm. Since we assume that fading and noise are independent across different sensors, the conditional probability P(HIy) can be rewritten as P(HIy) = p(yIH)P(H) = ñPk(YkIHi)P(Hi) (3.2) k=1 Pk(Yk) Furthermore, the conditional pdf pk(ykHj) of sensor k can be expanded as M-1 Pk(YJJHi) = pk(yklak = = w,IH) jO M-1 = pk(ykak)Pk(ak = wIH), (3.3) j=O akEA3 where A, contains all Mv_2 possible vectors ak with ak = w and the condi tional pdf pk(ykak) is given by (2.4). Combining (2.4) and (3.1)—(3.3), and omitting all irrelevant terms will yield the optimal MSD fusion rule (K fM_i = argrnax slog pk(yklak)Pk(ak = wH) J +/3H1zeM 1=1 \j=O akeA J = argrnax {lo( exp (2{ tyk()y(v)H1,ieM k=1 j=O akEA, 1L1 UbL+1 xflak()})Pk(akwiHi)) +}, (3.4) where ct + 1og(P(H)) denotes the new bias term. Discussion: Despite its optimal performance, the MSD fusion rule in (3.4) has several short—comings: (a) The complexity of the fusion rule in (3.4) is exponential in both K and N; (b) Because of the large dynamic range of the exponential functions in (3.4), especially for high channel SNRs (i.e., PKu/u, >> 1), the optimal fusion rule causes numerical problems, especially 19 in fixed point implementations; and (c) The optimal fusion rule requires sta tistical CSI (in the form of t) and knowledge of the sensor performance (in form of Pk(ak = w,IHJ), though we note that the coefficients are related to the coefficients of a linear predictor for the process Tk [n] and can be efficiently computed using adaptive algorithms [31, 32]. In light of the above—listed draw backs of the optimal fusion rule, there is a need to search for suboptimal fusion rules that do not have these drawbacks but still provide a good performance. 3.2 Chair—Varshney (CV) Fusion Rule The complexity of the optimal fusion rule can be significantly reduced by as suming that the double sum on the right hand side (RHS) of (3.3) is dominated by the ML vector k [àk(1) ... ak(N— i)]T which maximizes pk(yklak), i.e., pk(yklak) >> pk(ykak), ak ak, k e IC. This is a valid assumption for high channel SNR. In this case, the optimal fusion rule can be simplified to H = argmax {lo(Pk(Ykak)Pk(akHi)) (3.5) H,iEM k=1 where k = ak(z’o) denotes the element of àk which is considered for detection. We note that the ML vectors k, k E IC, can be efficiently obtained from Yk by applying the MSDSD algorithm in [27, Fig. 1], cf. Section 2.2.2. For binary hypothesis testing (M = 2), (3.5) can be expressed as a likelihood ratio = slog ‘‘ + log (3.6) and we decide in favor of H1 if exceeds threshold ‘Yo — /3k, and for H0 otherwise. Thus, (3.5) and (3.6) can be regarded as the MSD version of the familiar CV fusion rule [11]. Discussion: The complexity of the suboptimal fusion rules in (3.5) and (3.6) grows only linearly with the increase in the number of sensors K. Fur thermore, for sufficiently high channel SNR the average complexity of MSDSD 20 is polynomial in N [27], and thus, the complexity of the proposed fusion rule is also polynomial in N. Similar to the optimal fusion rule, knowledge of the sensor performance and, for N > 2, the statistical CSI, is required for the CV fusion rule. For N = 2, based on (3.5) it can be shown that statistical CSI is not required if the channels are i.i.d. (i.e., Rk = R, Vk). 3.3 Fusion Rule for Ideal Local Sensors (ILS) For derivation of the CV fusion rule it was implicitly assumed that the uncer tainty about the hypothesis at the fusion center originated only from the local sensor decisions, whereas the channel between the sensors and the fusion cen ter was assumed ideal. The opposite assumptions, however, can also be made, namely that the local sensor decisions are ideal, i.e., Pk(ak = wIH) = 1 and Pk(ak = wIH) = 0 for j i, and the uncertainty at the fusion center is due to the noisy transmission channel only. In this case, ak = a, Vk e IC, is valid and the optimal ML block decision rule for a is given by a argrnax {1o(Pk(vka)) + (3.7) where the bias /3 is determined by the trial symbol a a(zio) = w,, i M, and the hypothesis estimate H can be directly obtained from the relevant element a = à(vo) w of a. For the binary case, it is convenient to express (3.7) in terms of a likelihood ratio AILS = 1og (Pk2), (3.8) k=1 pk(ykla ) where à’ is that vector a e A3 which maximizes >L log(pk(ya)). In particular, H = H1 is chosen if AILS > 7o = i3o — /3k, and H; H0 otherwise. The computational complexity of the fusion rules in (3.7) and (3.8) is only linear in K but still exponential in N if a brute force search for all possible a is conducted. Similar to the CV fusion rule, the application of sphere decoding 21 is the key to reducing complexity further. For this purpose, we rewrite (3.7) as = argmin sHUUks — (3.9) s,s(N)=1 I.k=1 J s [s(1) s(2) ... s(N)]T contains the absolute phase symbols from which the elements of a are obtained as a(j) = s(j + 1)s*(j). Because of the phase ambiguity inherent in (3.9), we can set s(N) = 1 without loss of generality. The sum over k and the bias term ,i3 in (3.9) make a direct application of the MSDSD algorithm in [27] impossible. However, as will be explained in the following, a modified version of MSDSD can be used to solve (3.9) efficiently provided that /3 < 0, i e M. The latter condition can always be fulfilled by properly choosing aj, i e M. The modified MSDSD only examines candidate vectors that meet 3HUHU s — <R2. (3.10) Assuming we have found (preliminary) decisions .(l) for the last N — 1 com ponents s(l), ii + 1 7 N, we can define an equivalent squared length N K N 2 d1= u() —3ö[vo—ii—1], (3.11) l=v+1 k=1 =1 where and j3 is obtained from .(v0 + 1)*(vo) = a = w. Com paring (3.10) and (3.11), possible values for s(v) have to satisfy K N 2 us(v)+ uL() —i33[v0v]+d1R, (3.12) k=1 where /3 is determined by .(v0 + 1)s*(vo) a wj. Similar to the MSDSD in [27], once a valid vector . is found, i.e., ii = 1 is reached, the radius R is dynamically updated by R := d1, and the search is repeated starting with ii = 2 and the new radius R. If condition (3.12) cannot be met for some index ii is incremented and another value of s(v) is tested. Based on (3.10)—(3.12) 22 the modified MSDSD algorithm given by Algorithms 1 and 2 can be obtained. Consequently, with an initial radius of R —p the algorithm will always find a solution to (3.7). Discussion: The complexity of the ILS fusion rule is linear in K and for high channel SNR polynomial in N. While statistical CSI is still required for N> 2, the local sensor performance Pk(ak = wIH2), i e M, j E M, does not have to be known at the fusion center. Of course, the price to be paid for this advantage is a loss in performance compared to the optimal fusion rule. For N = 2, it can be shown based on (3.7) that statistical CSI is not required if the channels are i.i.d. 23 Algorithm 1 Pseudocode for MSDSI) for ILS Fusion Rule 1 function [1, d2] = MSDSD-ILS(U1,U2 Urc, MN, R, vo,fl) 2: 3: 4: 5: 6: 7: 8: 9: 10: SN := 1 2._ K 5 2 N 45=! UNN v := N — I for k = Ito K do q := l=v*1 u,s, end for [step, n,[ = flndBestILS(q,,..., q’, s4 u, M) search while search = I do d : + q5 2 if v = s’o then i :=mod(M + (step,,,.i (flv*l )—step(n), M) d :=d—flj end if if 4 <R and n,, M then 2,, s,, := if v I then 1’ := I’ — 1 for k = Ito K do q := usj end for [step,,,n,.j = flndBestlLS(q,,.... u, M) ehe R := 4’ 5’ := 5’ + 1 while n = M and search = I do ifv=N—1 thensearch:=Oelsev:=v+1endif end while n,, := n,, + I initial radius R, vector of bias term/I fix last component of initialize squared length start at component v = N — sum the last N — v components find with 12 candidate for comp. at v = N — update squared length find current estimated hypothesis a(s’o) = w, s bins length due to hypothesis i being the candidate check search radius and constellation size r store candidate component check if last component is reached move down to next component sum the last N — v components find the I” candidate for component at v first componetit reached store best estimated sequence so far update sphere radius move up to previous component move up until n,, M r terminate search if v = N — 1 else move up to prey. comp. count examined candidates for component at v 28: end if 29: else 30: if v=N—l then 31: search:=O 32: else terminate search if v = N - 5’ 5’ + I while n,, = M and search = I do if v = N — I then search := 0 else v := 5’ + I end if end while move up to previous component move up until n M x terminate search if v = N — I else move up to prey. comp. 37: end if 38: 39: end if 40: end while 41: end function count examined candidates for component at!’ Algorithm 2 Pseudocode for findBest used in MSDSD function [STEr, n] = flndBestlLS(q q’, u u, M) find order of M—PSK signal point to test according to SE stsstegy for m = 0 to M — I do d,,,2, := ue” + q 2 end for Compute all possible square length conthbutions step sort.0 .scending(d,,,,) returns step,. which contains values m sorted in order of increasing value of d,,, n, 1 counter of examined candidates for component v end function 24 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 1 := S 33: 34: 35: 36: 3.4 Max—Log Fusion Rule For high channel SNR (i.e., PKu/c1,>> 1, Vk e SAC) one of the exponentials in (3.4) will be dominant and the max—log approximation, which is well known from the Turbo—coding literature [33], can be applied H = argmax {max{lo(Pk(vkIak))+lo(Pk(ak=wiIHi))}+i} argrnax { max {2{ tVYkcu)Y(v)Yiak()}k=1 ,41V1L+1 =l) +log(Pk(ak =wIH))} (3.13) The max—log fusion rule in (3.13) is computationally more efficient and nu merically more stable than the optimal fusion rule in (3.4) since exponential functions are avoided in (3.13). However, if (3.13) is implemented in a straight forward fashion, its computational complexity is still exponential in N, since for every test hypothesis H, i e M, the maximum of log(pk(yak)) has to be found over all ak e A, j e M. However, the max—log fusion rule can be rewritten as H = argmax { (max{log(Pk(vkIa))+log(Pk(ak =wH))}) (3.14) where â is that ak E A3 which maximizes pk(yklak). à can be efficiently computed using sphere decoding. In particular, one simple method to obtain â, j E M, is by slightly modifying the MSDSD algorithm in [27, Fig. 1] by forcing a(vo) = w even when this does not produce the ML solution. This modified MSDSD must be applied M times and will be referred to as re peated tree search (RTS) MSDSD. However, a more efficient method can be obtained by noting that in RTS—MSDSD there are a large number of redun dant squared length computations. This is avoided if the SD obtains all à, j M, in a single search. We will refer to this as single tree search (STS) 25 MSDSD. The STS—MSDSD approach was proposed in [34] by introducing mul tiple radii for comparisons rather than just one radius representing the current best estimate of . Applying STS—MSDSD, we consider M different radii, [Ro R2 ... RM_1], correspond to M different à. Similar to the MSDSD algorithm in [27, Fig. 1], STS—MSDSD only examines candidate vector that meet the condition HrrHyr D2 8kJk(JkSk<11.j, where R3 is determined by .sk(vO + 1)s(vo) w3. Similarly, possible values of Sk(Y) have to satisfy both N 2 d = U,Sk(V) + > USk(/1) + d1 <R, 1)0 < L/ < M + 1 (3.16) 1LV+1 N 2 = ttSk(V) + uj(tL) + d÷1 R, 1 <ii < v (3.17) where Rmax = max R3. The condition (3.16) is necessary to ensure that when a is not the ML solution, it does not get eliminated early on in the search. Once a valid k is obtained, the radius R, is dynamically updated depending on (v + 1)(v). The pseudocode for this STS—MSDSD is given in Algorithm 3, where the functions findBest() and findNext() are given in [27, Fig. 1]. For the binary case, M = 2, (3.14) is equivalent to choosing H1 if likelihood ratio Am_iog exceeds threshold ‘yo = ,8o — /3, and H0 otherwise, where Amiog is defined as Am_iog = maxmin hog = (3.18) k=1 jEM ieM \Pk(ykkJk)Pk(ak = wjHo)) J Discussion: The complexity of the max—log fusion rule is linear in K and for high channel SNR polynomial in N. The implementation of (3.14) and (3.18) requires knowledge of the sensor performance Pk (ak = Hi), i e M, j E M. Furthermore, the complexity of the max—log fusion rule is higher than that of the CV and ILS fusion rules discussed in Sections 3.2 and 3.3, 26 respectively. For the max—log fusion rule MK vectors à, j e M, k have to be obtained per decision. In contrast, for the CV and ILS fusion rules, only K and one ML vectors have to be computed, respectively. In addition, in contrast to the CV and ILS fusion rules, the max—log fusion rule requires statistical CSI even for N 2 and i.i.d. channels. On the other hand, the max—log fusion rule achieves a superior performance compared to the CV and ILS fusion rules, cf. Chapter 5. 27 Algorithm 3 Pseudocode for MSDSD for Max—Log Fusion Rule 1: function [&] = MSDSD-ILS(U, M, N, , i’s) SN := I 4 := UNN F v := N—i u,ss Rn,ux := max{Ro Rat..t) (sn,step,., nJ = findBest(q, a,.,. M) search := I while search = 1 do := I5i,.,.e”” +q.I2d,.1 if ci, <R,,,, and n, 14 then 5, := 27: else if v == s’s then g := rnod{M + (,n,+t — ,n,), 14) else I := 1 end if if v == 1 and ci, <R then := max)Rs Ra,s) V := V + 1 while n,=M and search= ldo if v = N — 1 then search := 0 else s’ := s’ + I end if end while [m,.,step,., n,] = findNext(m,.step,, n,) etseif (v>s’sor(s’vsandd,<R))andn,M then V := V — I Uw3i [sn,,step,,n,] = findBest(q,.u,.,,M) mitial vector of radius R, fix last comp. of s initialize squared length start at romp. v = N — sum the last N — v components set maximum radius ‘find hestcandidate forcomp. atv=N- 1 • update squared length • check maximum radius and constetlatims size • store candidate comp. check which radius to compare check if last comp. reached and radius Re store heat estimated sequence so far update radius R5 • update maximum mdius move up to previous comp. • move up until n, M • terminate search if v = N — I else move up to prey. comp. find next component ate to examine check if need to compare radius R5 and constellation size move down to next comp. sum die last N — s’ componenu find heat candidate for comp. at s’ 28: 29: 30: 31: 32: 33: 34: 35: 36: if s’ = N — 1 then else search := 0 ifs’ v5 then s’ := v + 1 end if while n,= 14 and search= 1 do if s’ = N — I then search := 0 else v := s’ + 1 end if end while end if [m,,,step,., n,) = fiudNext(m,.,step,., n,) • terminate search ifs’ = N - • force to compare other 5(v) comp. ifs’ = s’o, else usove up move up until n, * M • terminate search if v = N — I else move up to prey. comp. 41: else 46: end if e := 5’ + I while n,= Ill and search= ldo if v = N — 1 then search := 0 else s’ := s’ + 1 end if • move up to previous compo. ‘move up until n, * 14 tenninate search if v = N — I else move up to prey. comp. end if 49: end while 50: end function 2: 3: 4: 5: 6: 7: 8: 9: 10: II: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 37: end if 38: else 39: 40: if v=N—l then search := 0 42: 43: 44: • find next component at s’ to examine terminate search ifs’ = N-I 45: end while 47: 48: [m,,step,,,n,,] = findNext(n,.step,,,n,.) • find next component at v to examine 28 Chapter 4 Analysis of Suboptimal Fusion Rules An analysis of the optimal fusion rule does not seem to be possible. Therefore, we concentrate in this section on the CV, ILS, and max—log fusion rules and on general performance bounds valid for any fusion rule. To make the analysis tractable, we assume M 2, i.e., M = {O, 1}, i.i.d. channels, i.e., o = a2, Bk = B, Rk = R, t = trn,, and pk(yklak) p(ykak), Vk E C, and identical sensors with probability of false alarm Pf P (ak = —1 H0) = Pk (ak = —1 H0) and probability of detection Pd P(ak = —1IH1)= Pk(ak = —1H1), V/v e SAC. 4.1 Performance Bounds Before considering specific fusion rules, we provide two performance upper bounds valid for any fusion rule including the optimal one. 1) Bound I: For the first bound, we assume that all sensors make correct decisions and decision errors at the fusion center are due to transmission errors only, i.e., ak = a, Vk e K, and zero bias, i.e., = = 0. In this case, the sensor network is equivalent to a point—to—point transmission with K—fold receive diversity and conventional MSDD [24, 25] is the optimal fusion rule. 29 Thus, the probabilities of false alarm and detection are given by Pf0 = BERVO and Pd0 = 1 — BERJ0, (4.1) where BERVO denotes the probability that a = a(z’o) was transmitted and a a, a E {±1}, 1 ‘Jo N — 1, was detected, i.e., BERLI0 is the bit error rate (BER) for 2—DPSK symbol a(vo) for point—to—point transmission and MSDD at the receiver. BERVO can be lower bounded as [26] BERVO > (PEPLIO + PEP,01)/2 1 vo N — 1, (4.2) where the pairwise error probability (PEP), PEPU, is the probability that vec tor s was transmitted and .(vo) [s(1) ... s(vo — 1) .(vo) s(ii0 + 1) ... s(N)]T, .s(v), was detected. The averaging over two error events in (4.2) is necessary, since, because of the differential encoding, a(v) a(vo) may be caused by either .(v) or (vo + 1). Note that in order to get performance upper bounds, we only count error events causing a single erroneous symbol, â(v) s(v), in (4.2). Taking into account the K—fold diversity, we obtain from [26, Eq. (12a)] for the PEP for the problem at hand PEP= [ (1 /)](K1) (+)k, (4.3) where p1, —t(PK + o) — 1, 1 v N. Eqs. (4.1)—(4.3) constitute a performance upper bound for any fusion rule with noisy sensors. This bound becomes tight for optimal decision fusion if transmission errors dominate the overall performance, which is the case for example at low channel SNRs and for highly reliable local sensors. 2) Bound II: For the second bound, we assume a noise—free transmission channel, i.e., the decision errors at the fusion center are caused by local decision errors at the sensors only. In this case, the CV fusion rule is optimum and the 30 corresponding probabilities of false alarm and detection are given by [11] Pf0 = (‘)P(i — Pf)K_ and Pd0 = ()P(i — Pd), (4.4) where K70, 0 K K, depends on decision threshold ‘Yo as follows — Klog (E) K70 = Pd(1-Pf) (4.5) log Pf(1—Pd) For realistic, noisy transmission channels, (4.4) constitutes a performance up per bound which becomes tight for high channel SNRs. 4.2 CV Fusion Rule Considering (3.6) the probabilities of false alarm and detection at the fusion center can be expressed as Pf0 = ()P(i —p0)K_i and Pd0 = ()P(1 —p1)K_i, (4.6) where P0 = P(H = H10) and P1 = P(H = H1). P0 and P1 can be expanded as P = P(H; = H1ak = —1)P(ak = —1lH) + P(H = HlIak = 1)P(ak = 1IH) = (4.7) where x0 = f and x1 = d, and BER1I0 is the BER of 2—DPSK for a point— to—point link without diversity and MSDD at the receiver. This BER can be approximated as [26, Table I, Eq. (12)] BERVO PEPL, + PEP01, 1 vo <N — 1, (4.8) PEPV = i — 1 (4.9) 2 /1+1/pv) For the special case of N = 2, (4.8) is exact, while it is an accurate approx imation for N > 2 and sufficiently high channel SNR. Using (4.6)—(4.9) the 31 probabilities of false alarm and detection for the CV decision rule can be com puted approximately (exactly) for N> 2 (N = 2). 4.3 ILS Fusion Rule The ILS decision in (3.7) is influenced by the local sensor decisions ak(l1), 1 k K, 1 v < N — 1, which makes an exact analysis for N > 2 intractable and renders both approximations and bounds loose. Therefore, in this subsection, we concentrate on the case N = 2. The probabilities of false alarm and detection can be expressed as Pf0 = P(à = —lIa)P(aIHo) and do = P(à = —1Ia)P(aHi), (4.10) where P(â = —1ã) denotes the probability that the fusion center detects a = —1, i.e., H H1, given the local sensor decisions a [a1 a2 ... aK]T. Furthermore, the conditional sensor decision probabilities in (4.10) are given by P(aIHo) pK_ko(l — Pf)k0 and P(aH1) = pK_ko(1 — PdY, where k0 denotes the number of elements of a that are equal to 1. Based on (3.8) P(â = —1ã) can be expressed as P(â = —ha) = Pr{—AILS < —7o}, which leads to c+joo = —1a) = -- f ILs(sIa)e°8 (4.11) c-joo where ILs(sIa) denotes the Laplace transform of the pdf of —AILS given a and ak = a, and c is a small positive constant that lies in the region of convergence of the integral. Closer examination of (3.8) for N = 2 reveals that AILS is a 32 quadratic form of Gaussian random variables, and can be expressed as AILS = {t2yk(1)y(2)} = -2(tyk(1)y(2) + tly(1)yk(2)) = -2(tal(hk(1) +nk(1))(hk(2) +nk(2))* +tlak(/hk(1) + nk(1))*(/Phk(2) + flk(2))) = uM(ã)u, (4.12) where u [/hi[n] + ni[n], s/hi[n — 1] + ni[n — 1], ..., i/hK[n — T -1] .-i- riK[n — 1]] and M(a) = diag{M1(),..., MK(aK)} with Mk(ak) = 2ak [1t]. Consequently, we obtain ‘FILS(sIa) l/det(12j.c + sIPvI(ã)), (4.13) where R ‘K ® R. We note that the integral in (4.11) can be numerically evaluated efficiently using e.g. Gauss—Chebyshev quadrature rules [35] c+joo Pr{—AIL5 < —‘yo} = — f c-joe JLS(C + c6Iã)[1 — jöj]e0}, (4.14) where 1’ILs(sIã) is given in (4.13) with s = c + c6 and S = tan(1ir). The selection of N and c affects the accuracy of the numerical method, with c selected to satisfy 0 < c < c0, where c0 denotes the smallest real part of all singularities of IILs(sIã), and N selected as large as possible to achieve a desired accuracy. Thus, the exact probabilities of false alarm and detection for the ILS fusion rule with N = 2 can be efficiently computed from (4.10)—(4.11), (4. 13)—(4. 14). 33 4.4 Max—Log Fusion Rule For the max—log fusion rule, the probabilities of false alarm and detection can be expressed as Pf0 = Pr{—Am_iog < —7oIHo} and Pd0 = Pr{—Am_iog < —7oIHi}, (4.15) cf. (3.18). Denoting the Laplace transform of the pdf of the negative log— likelihood ratio Am_iog by ‘Im_iog(8j11i), (4.15) can be rewritten as c+joo 1x = f m_iog(sIHi)e7°8 i e M, (4.16) c-joo where x0 fo and x1 = d0. Since Pf0 and Pd0 can be obtained by numerical integration from (4.16) if 1m_iog(sIHj) is known, the remainder of this section will be devoted to calculation of this Laplace transform. As the fading gains and noise samples in the different diversity branches are i.i.d., respectively, m_iog(8Ii) can be expressed as ‘Tm_iog(sHi) = (I(sIH))K, i e M, (4.17) where I(sH) denotes the Laplace transform of the pdf of Zk maxmin)’log (PYkIaFak wH0)• (4.18)jEMIEM \P(YkIà)P(àk=wiHl))J I2(sIH) can be rewritten as = (1 — P)I(sà = —1, a = 1) +P1I(sIa = —1, a = —1), i E (4.19) where x0 = f and x1 = d, and (sIa, a) denotes the Laplace transform of the pdf of zk given ak = a and a. For calculation of I(sà, a) it is useful to note that for M 2, (4.18) can be rewritten as — (max{p(yIà)(1 — Pf),p(yk?4)Pf} Zk — og max{p(ykâ)(1 — Pd),p(ykà)Pd} (4.20) 34 Using the definition y and assuming Pf < 0.5 and Pd> 0.5, we can show that (4.20) can be rewritten as ay<bi Zk ay + 432, b1 <ay , (4.21) 433, ay>b2 where log(Pf/Pd), /32 log((l — Pf)/Pd), /33 log((l — P1)/(1 — Pd)), b1 log(Pf/(1 — Pf)), and b2 log(Pd/(1 — Pd)). To arrive at (4.21) for a = —1, we have exploited = (4.22) For convenience (4.21) is illustrated in Fig. 4.1 for the case a = 1. Fig. 4.1 reveals that the max—log fusion rule soft—limits the log—likelihood ratios y of the individual sensors at the fusion center by taking into account the a priori values Pf and Pd. It is interesting to note that Fig. 4.1 can also be related to Zk ___/337 Figure 4.1: Illustration of relationship between zk and y for a = 1. Note that with the definitions in Section 4.4, b1 < 0, b2 > 0, < 0, and /33 > 0 as long as Pd > 0.5 and Pf < 0.5. 35 the CV fusion rule where b1 = b2 = 0 and a = 1 Zk = < 0 (4.23) L3’ >0 By denoting the pdf of y by py(y) and exploiting (4.21), we can express = —1, a) as = —1, a) = f e’py(ay) dy+f e_8 +2)p(ay) dy+f dy. —00 b2 (4.24) For calculation of p,(y), we distinguish in the following the cases N = 2 and N> 2. N = 2: For N = 2, the oniy possible error event leading to a = —1 is . = [—s(1) 1]T when s = [s(1) 1]T and y can be expressed as y = —rRE’rk8+ rR1k. In other words, y is simply the decision variable for conventional differential detection. Thus, the Laplace transform of p,(y) is given by [26, Eq. (27)] 12 / S) = 4.25 (s-i-vi)(s—v2 where v112 = (/i + i/Pu0 + 1)/2 with iio = 1. From (4.25) we can calculate p,(y) as () V12 (e_v1(y) + ev2(_y)). (4.26) V1 + V2 Combining (4.24) and (4.26) we obtain vv /e8I31+jb1 /1 — e(_s+vj)1Iz(sIa = —1, a) = I + e82 Vi+Vj ‘ Vi \ —s+v 1 — e_(8+z)j)b2’\ e_83_’01b2’\ + 1+ 1, (4.27) .s+vi I vi I where (i,j) = (1,2) and (i,j) = (2,1) for a = 1 and a = —1, respectively. N > 2: For N > 2 the problem is more difficult, since there are more than one possible error events that lead to a(ii0) = a = —1. The most likely error events are &, and V0+1 which differ from s only in positions v0 and 36 ‘Jo + 1, respectively. The corresponding likelihood ratios are denoted by y and Y2 To make the problem tractable, we assume that & and vO+1 are the only relevant error events, i.e., we neglect all other error events, which is a valid approximation for high channel SNRs. In this case, y is given by y = min{yi, y2}. In order to get closed—form results, we make the following two additional approximations: (a) y and Y2 are independent and (b) y and Y2 are identically distributed. Both assumptions are justified for high channel SNRs. By exploiting results from order statistics [36] and [26], we obtain for the pdf of y py(y) = 2p,,1(y)(l —P1(y)), (4.28) where py1(y) = v2 (e_v1(y) + e’2Yü(_y)), cf. (4.26), P1(y) fp1(x) dx, and v112 = (i + 1/p0 + 1)/2 with 1 < vo < N — 1. Combining (4.24) and (4.28) leads to the following closed—form expression for F(sa —1, a 1) and (sIa= —1,a= 1) = —1,a 1) 2 ( v12 )2 (e_s131 ((Vi +v2)e2b1 — e2’2)v1 + v2 v12 2v +e2 ((vi +v2)(e_(82)b1 — 1) + 1 — e_(8_v2)b1 viv(s — v2) v2(s — 2v) 1 — e_(8f21)b2 e_3v1b2 + v(s+2v) ) + 2v ) (4.29) F(sIa = —1, a = —1) = 2 ( v12 2 ((v1 +v2)e_v2b2 — e_2)2b2\v+vJ \ v1 2v +e2 ((vi +v2)(1 — e_(H2)b2) + e_(8+2)b1 — 1 viv(s+v v2(s+2v) e_(8_2’vi)bi — 1 e_81+2v1b1 + vi(s — 2v1) ) + 2v? ) (4.30) We note that a direct numerical integration of (4.17) is problematic since the inverse Laplace transform of m—1og (s H) has discontinuities (reflected e.g. by the first and last terms in the sum on the right hand sides of (4.27), (4.29) 37 and (4.30)). However, the terms corresponding to the discontinuities can be easily inverted in closed form, and the remaining term without discontinuities can then be inverted numerically, e.g. using the Gauss—Chebyshev quadrature rules mentioned in section (4.3). Specifically, I(sIH) can be decomposed to =0(sIH) + Cp,i’, (4.31) where P is the number of terms that contains discontinuities, I0(sfH) = I(sH) — Cp,jesJPi represents the term without discontinuities, and represent their respective coefficients defined earlier from the Laplace transform of the pdf of Zk. For (4.19), P = 4 and in the case where the WSN consist of K sensors, (4.17) can be expressed as, m_iog(8Hi) K (cp,iemi) = _iog(sIHi) + iiog(slHi).p=1 (4.32) The term ‘I_iog(sHi) represents all the discontinuities in Im_iog(sHi) and can be written as ( cp,iemi) K = (d1,d2,.. . , dp)c12•. .P1 dp (4.33) where the summation is taken over all sequences of integer d such that Z1d = K and ( K ) K! The inverse Laplace transform of (4.33) cand1,d2...,dp di!d2!...dp! easily be obtained, and by combining (4.16), (4.19), (4.27), (4.32), and the cor responding expression (4.29), (4.30) for N> 2, the probabilities of false alarm 38 and detection can be exactly (approximately) computed for N = 2 (N> 2) = ( d. , dp) .d1,d2 dp — [d1J,+... + dpJp,]) c+joo + f jog(8IHi)e708 , (4.34) c-joo where x0 = fo and x1 = d0 denote the probability of false alarm and detection respectively and —Iog (s I H) contains terms which can be inverted numeri cally. 39 Chapter 5 Numerical and Simulation Results This chapter presents numerical and simulation results for the proposed opti mal and suboptimal fusion rules. Binary hypothesis and non—binary hypothesis testing will be presented separately. For all results shown in this chapter, the middle symbol of the observation window is used for detection, i.e., iio = N/2, since this leads to the best performance. 5.1 Binary Hypothesis Testing In this subsection, in order to confirm our simulation results with the analytical results from Chapter 4, we assume M = 2, i.i.d. Rayleigh fading channels, identical sensors, and P(H0)= P(H1) = 1/2. All curves labeled with “Theory” (for N = 2) and “Approximation” (for N = 6) were generated using the analytical methods discussed in Chapter 4, while the remaining curves were obtained by computer simulation. 40 5.1.1 Error Probability In Figs. 5.1 and 5.2, we examine the error probability Fe Pf0(Ho) + (1 — P)P(H1of the suboptimal MSD fusion rules considered vs. Eb/No for BT = 0.1 and BT = 0, respectively. Here, Eb is the total received average energy per bit (from all sensors), and N0 denotes the one—sided power spectral density of the underlying continuous—time noise process. The decision threshold 70 = 0 was used for all fusion rules and K = 8, Pd = 0.8, and Pf = 0.01. In addition to the suboptimal MSD fusion rules, Figs. 5.1 and 5.2 also contain the two performance upper bounds introduced in Section 4.1. Furthermore, Fig. 5.1 also includes the performance of the optimal fusion rule for N = 2 (the optimal fusion rule is computationally not feasible for N = 6) and the error probability of the coherent max—log fusion rule for DPSK, whereas Fig. 5.2 shows the performance of the coherent versions of all three suboptimal MSD fusion rules. We note that these coherent fusion rules require perfect knowledge of the fading channel gains. Figs. 5.1 and 5.2 show that while the ILS fusion rule has the best performance for very low Eb/NO, where transmission errors significantly affects the overall performance, the CV and the max—log fusion rules yield a superior performance for medium—to—high Es/No. A comparison of Figs. 5.1 and 5.2 reveals that increasing the observation window size from N = 2 to N = 6 is more beneficial for fast fading (BT = 0.1) than for static fading (BT == 0). In the latter case, the performance gap between coherent detection and the respective MSD fusion rules is relatively small even for N = 2. In contrast, for BT = 0.1 and N 2 the performance of both the CV and the max—log fusion rules is limited by the high error floor caused by the fast fading. This high error floor is also seen under the optimal fusion rule, which yields a negligible performance gain compared to the max—log fusion rule for N = 2. For N = 6 this error floor is mitigated and both the CV and the max—log fusion rules approach Bound II for high Eb/No, i.e., performance is limited by local sensor 41 decision errors in this case and not by transmission errors. For the ILS fusion rule increasing the observation window to N > 2 is not beneficial and it even leads to a loss in performance for high Lb/No for BT = 0. This somewhat surprising behavior is caused by the local decision errors at the sensors, which were ignored for derivation of the ILS fusion rule. For N = 2, theoretical and simulation results in Figs. 5.1 and 5.2 match perfectly, confirming the analysis in Section 4. As expected from the discussions in Section 4, for N = 6, there is a good agreement between theoretical and simulation results for the CV and the max—log fusion rules at high Eb/No ratios, cf. Fig. 5.1 (for clarity of presentation the analytical curves for N = 6 have been omitted in Fig. 5.2). At low Lb/No ratios, the analytical results overestimate the actual Fe since the assumptions leading to the analytical result for N > 2 are less justified. 100 I I —e—————l’I=2(Sirnulation) . . — — —N=2(Theory) S —V—N=6(Simulatior) —, . N = 6 (Approximation) —I—— Optimal Fusion Rule (N = 2) Coherent Max—Log S 101 \ \ -,-,--e ----- 1- I \... 102 BoundI. Bound II 10 I I I 0 5 10 15 30 Eb/NO [dBj Figure 5.1: Probability of error Fe vs. Eb/No for decision threshold ‘Yo = 0. K = 8, M 2, Pd = 0.8, Pf = 0.01, BT = 0.1, and i.i.d. Rayleigh fading. 42 20 25 100 .I.j.. I —0--— N = 2 (Simulation) — — —N=2(Theo) —v— N =6 (Simulation) • . . . Coherent 10_i ;:::::::\:::::::‘ ,.- . .• / . .. y - - • \ CV —2 : :0 :: ::: : :: BoutdI . .. Boundil .10 •::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ‘.• I’ I I 0 5 10 15 20 25 30 Eb/NO [dB] Figure 5.2: Probability of error P vs. Eb/No for decision threshold 70 = 0. K = 8, M = 2, Pd 0.8, Pf = 0.01, BT = 0, and i.i.d. Rayleigh fading. 5.1.2 Constant False Alarm Probability Fig. 5.3 shows P as a function of Eb/NO for a fixed probability of false alarm of Pf0 0.001, which is achieved by adjusting decision threshold ‘Yo accordingly. Furthermore, K = 8, Pd = 0.7, Pf = 0.05, and BT = 0.1. In Fig. 5.3, the max—log fusion rule yields a superior performance compared to the other suboptimal MSD fusion rules but the CV and ILS fusion rules approach the max—log performance for high and low Eb/No, respectively. For N = 6, both the max—log and the CV fusion rules approach Bound II for high enough Eb/No, whereas for N = 2, these fusion rules as well as the optimal fusion rule are limited by transmission errors caused by fast fading. In contrast, the ILS fusion rule achieves a better performance for N = 2 than for N = 6. Fig. 5.3 43 shows again a good agreement between analytical and simulation results. 1 I I & N = 2 (Simulation) : : ———N=2(Theory) / I 0.9 V N =6 (Simulation) . .. . / . e — — N = 6(Approximation) . . I Optimal Fusion Rule (N =2) . 0.8 . _._. Coherent Max—Log 0.7 Max—Log . cv 0.6 . ./ : 0.5 ILS 0.4 0.3 / 0 0.2 4 0.1 : . I I I u 5 10 15 20 25 30 Eb/NO [dB] Figure 5.3: Probability of detection Pdo vs. Eb/No for a probability of false alarm of Pf0 = 0.001. K = 8, M = 2, Pd = 0.7, Pf = 0.05, BT = 0.1, and i.i.d. Rayleigh fading. 5.1.3 Receiver Operating Characteristic In Fig. 5.4, we show the ROC for the considered MSD fusion rules and the coherent max—log fusion rule for DPSK. K = 8, Pd = 0.7, Pf = 0.05, BT = 0.1, and Eb/No = 20 dB. Fig. 5.4 shows the superiority of the max—log fusion rule especially if low probabilities of false alarm are desired. Increasing N from two to six yields significant gains for both the max—log and the CV fusion rules. In fact, the max—log fusion rule with N = 6 bridges half of the performance gap between the coherent max—log fusion rule and the MSD max—log fusion rule with N = 2. On the other hand, for N = 2 the optimal fusion rule performs only slightly better than the max—log fusion rule. 44 1 ::i ::::::i .• . ._.—‘.. :: :7:::: : :———N=2(Theory) 0.4 :.y . . . __ N = 6 (Simulation) :.:::: :—e..———N=2(Siaiulation) — — N = 6 (Approximation) I : :::::: :—l——————QptirnalFusionRule(N=2) ::::::: :—x—CoherentMax—Log 10 i0 102 101 100 PJ Figure 5.4: Probability of detection P vs. probability of false alarm Pf0. K=8,M=2,Pd=0.7,Pf=0.05,BT=0.1,Eb/No=2OdB,and i.i.d. Rayleigh fading. 5.1.4 Effects of Sensor Network Size Figs. 5.5 and 5.6 show the impact of the number of sensors on Fe and Pd0, respectively, for Pd = 0.7, Pf = 0.05, BT = 0.1, and Es/No 20 dB. For Fig. 5.5, we optimized the decision threshold o for minimization of Fe for each fusion rule and each considered K. For Fig. 5.6, was chosen so as to guarantee Pf0 = 0.001. Figs. 5.5 and 5.6 indicate that the max—log fusion rule benefits more from an increasing number of sensors than the ILS and the CV fusion rules. In particular, the CV fusion rule shows a saturation effect for large K in Fig. 5.5. This is due to the fact that since the total Eb/No of all sensors is fixed, the channel SNR per sensor decreases as K increases. Therefore, the assumption of a perfect transmission channel, which was implicitly made for derivation of the CV fusion rule, becomes less justified as K increases leading 45 to a loss in performance. t Max—Log •.- I I I I 2 4 6 8 10 12 14 16 K Figure 5.5: Probability of error Fe vs. number of sensors K. M = 2, Pd = 0.7, Pf = 0.05, BT = 0.1, Eb/No = 20 dB, and i.i.d. Rayleigh fading. 46 I . . - . ::.- 0.9 0.8 .4.. ..... / 0.7 . . CV 0.6 1. ILS 1.t° / 0.3 —e—— N = 2 (Simulation) — — —N=2(Theory) 0.1 —v—— N = 6 (Simulation) • — — N = 6 (Approximation) : . Coherent Max—Log 0 I I I I I 2 4 6 8 10 12 14 16 K Figure 5.6: Probability of detection Pd0 vs. number of sensors K for a proba bility of false alarm of Pf0 = 0.001. M = 2, Pd = 0.7, Pf = 0.05, BT = 0.1, Eb/No = 20 dB, and i.i.d. Rayleigh fading. 5.2 Multiple Hypothesis Testing For the multiple hypothesis testing case, we assume that the local sensor observations are given by Xk [ri] = Uk [n] + k [n], k 1C, where Uk [n] e {—(M — 1), —(M — 3),..., M — 1} and ñk[fl] is real AWGN. Throughout this subsection, we assume identical sensors, P(HZ) 1/M, i E M, and M = 4. The sensor performance indices Pk(ak[n] = wIH), i E M, j E M, k e )C, depend on the sensor SNR, SNRS 47 5.2.1 Error Probability M—iIn Fig. 5.7, we show the probability of missed detection Pm = jO P(HIH)P(H) vs. Eb/No for the proposed suboptimal MSD fusion rules and the corresponding coherent fusion rules. Again Eb is defined as the total received average energy per bit (from all sensors) and K = 8, BT = 0, SNRS = —3 dB and i.i.d. Rayleigh fading channels. Similar to the binary hypothesis error probability curves in static fading (BT = 0), the ILS fusion rule performs best for very low E/N0, the CV and max—log fusion rules per form well in the middle—to—high Es/No region. With N 2 the performance is already relatively close to coherent detection and when the observation win dow is increased to N = 6, only a minor increase in performance is observed. Again it is observed that increasing the observation window size actually in creases the missed detection if the ILS fusion rule is used. On the other hand, in Fig. 5.8 where the proposed MSD fusion rules are shown for N = 2, 4, 6 when BT = 0.1, it is easily seen that increasing the observation window is beneficial. As the observation window is increased to N = 6, the CV and max—log fusion rules are able to reduce the inherent error floor caused by fast fading and its error rate approaches the performance limit due to decision errors made by the local sensors. From Figs. 5.7 and 5.8, we conclude that, for ILS fusion, increasing the observation size is not recommended. When the observation size is increased to N = 6, the performance degrades in static channels while in non—static channels only minimal improvement is observed while the complexity of the fusion rule increases dramatically. 48 C I2 j z o . Pm 0 c a . . 0 t- e+ 0 — • : : : : : : : : : . : : : : : : : : : : : : . , : : : : : : : : : : ° ‘ : 0 - ‘ 0 0 . 4 - C.,- ’ Pm 0 - L 0 0 (i D j z o Co CD - L V 1 0 la o 0 :u i IT IT C D Z Z Z iq — . — 0 0 Z1’1 1 1 1 ‘ - - ( D o 4 r p- c : : . : : : - I. . t ‘I L f I,,,, 7 I 010 .1.1.4.1. -1 . NR=—5dB10 — — — — -2 \ : NR=—3dB10 -3 SNR. = 3dB : SNR = 0dB10 1 0 — — —N=2 0 N =6 ::::::::::::: 0 5 10 15 20 25 30 Eb/No [dBJ Figure 5.9: Probability of missed detection Pm vs. Eb/No for ILS fusion rule. M 4, BT 0.1,, i.i.d. Rayleigh fading, and SNRS = —5 dB, —3 dB, 0 dB, 3 dB. Fig. 5.9 shows miss detection vs. Eb/No using ILS fusion for various SNRS. In the derivation of the lbS rule in Section 3.3, as SNR8 increases, i.e., with more reliable sensor decisions, the benefit of increasing the observation window size to N = 6 becomes more apparent. Therefore, if the sensors can be made more reliable, e.g., by time averaging the observation at the sensors to im prove SNR8, increasing the observation size can be considered for ILS fusion, otherwise a more conservative approach should be taken by using N = 2. 5.2.2 Independent, Non—identically Distributed Fading Fig. 5.10 shows the probability of missed detection vs. E/N0 for the proposed suboptimal MSD fusion rules and the corresponding coherent fusion rules with 51 010 . .4. 1 : CV10 : : : : : : : : : : : : : : : : : : : : . : : : : : : : : : : : : : — — ILS iO_2 ________________ • p N=2(i.i.d) •. — — —N=2(i.n.d) : . 0 N = 6 (i.i.d) : : : : : : .‘ : : : : : : : : : : : : :::——\I=6(j.n.d)::::::::::::::::: :::::::::::::.::.::::::: 0 5 10 15 20 25 30 35 40 Eb/NO [dBJ Figure 5.10: Probability of missed detection Pm VS. Eb/No. M = 4, BT = 0.1, SNRS —3 dB, and i.n.d. Rayleigh fading. the following parameters: K = 8, BT = 0.1, SNRS = —3 dB, and channel SNR of sensors k e {1, 2, 3, 4} was 3 dB higher than that of the remaining four sensors, i.e., the fading was i.n.d. As a reference, the performance in i.i.d. fading channels are also shown. Interestingly both the CV and max— log fusion rules show little performance degradation for i.n.d. fading for both considered observation window sizes. Although the ILS fusion rule also shows little degradation in missed detection performance, the negative effect of i.n.d. fading is more apparent as the observation window size increases. Since ILS fusion is limited by the fact that it is ignoring sensor reliability, weighting the sensors with more reliable channels effectively weights certain sensors more even though all sensors are identical and unreliable. In the extreme case if the sensors are not identical, and the SNR8 are lower at the sensors with higher 52 channel SNR, the missed detection performance can degrade dramatically. 5.2.3 Effects of Sensor Reliability 100 I..... .:::• ::..:::::::::.:::::::::..:;:.:.:::::::..:::.::: —e——N=2 —v-—N=6 —c’— Coherent lOl :: . .: :.:::: ... :::. ..:: : ::: :.:::. :::::::.EIS::::::::::::::::::: cv E .::::::::..::::: —12 —10 —8 —6 —4 —2 0 SNRS [dB] Figure 5.11: Probability of missed detection Pm VS. SNR8 M = 4, BT = 0.1, Eb/NO = 30 dB, and i.n.d. Rayleigh fading. In Fig. 5.11, we show the probability of missed detection as a function of SNRS for the proposed suboptimal MSD fusion rules and the correspond ing coherent fusion rules with the following parameters: K = 8, BT = 0.1, Es/No = 30 dB, and i.n.d. channel (four channels have a 3 dB higher SNR than the remaining four channels). For low sensor SNR, the CV fusion rule achieves a similar performance as the max—log fusion rule since the overall per formance is mainly affected by the unreliable sensors. However, the CV fusion rule is not able to fully exploit the increasing reliability of the sensors when the sensor SNR improves and is ultimately limited by an error floor caused by 53 transmission errors which are not optimally taken into account in the CV fu sion rule. With highly reliable sensors, the CV fusion rule is even outperformed by the ILS fusion rule, whose performance steadily improves with increasing sensor SNR. This is probably because the assumption on which the ILS fusion rule is based, namely error—free sensors, has become more and more justified at high sensor SNR. Nevertheless, the max—log fusion rule yields the best per formance among all considered MSD fusion rules, and closely approaches the performance of the coherent max—log fusion rule with N = 6. 5.2.4 Estimation Error of Channel Correlation Matrix 010 I — — — ci tirrial Corr. I’Ilatrix :: 0 Corr. Error = 0.02 0 Corr. Error = —0.02 CV 101 : : : : : : : . : : : : : : : : : : : : : : : : : : : : S —2 : ILS10 ::::::;::::::::;::::::::::::::% 4% 4% .4% : 1 Eb/NO {dB] Figure 5.12: Probability of missed detection Pm vs. Eb/No with channel cor relation error. M = 4, BT = 0.1, SNRS = —3 dB, and i.i.d. Rayleigh fading. In Fig. 5.12, we show the probability of missed detection as a function 54 of Es/NO for the proposed suboptimal MSD fusion rules and consider the ef fect of estimation error on the channel correlation matrix, Rhh, i.e., phh[A] = 2 Jo(2ir(B+ Le)T;\). K = 8, BT = 0.1, SNR8 = —3 dB, and a correla tion error 2i= ±0.02, i.e., the estimated fading bandwidth is BT = 0.08 and BT = 0.12, respectively. A small deviation is shown for all three fusion rules relative to the curve when the optimal matrix is used. For both max—log and ILS fusion rules a minimal increase in missed detection is observed. For low Eb/NO, the max—log fusion rule exhibits the largest missed detection differ ence since the channel errors are the limiting factor at this operating range. When ILS fusion is performed, the performance degradation when using a non— optimal channel matrix for detection has little impact on fusion performance. On the other hand, for the CV fusion rule at medium—to—high SNRs exhibits a larger performance degradation of approximately 1dB. This is due to the assumption of perfect channel conditions for the CV fusion rule. Nevertheless, all three proposed fusion rules show a high tolerance to estimation errors in the channel correlation matrix. 5.3 Computational Complexity In Fig. 5.13, we compare the complexity of the considered MSD fusion rules for N = 6 as a function of Eb/No with the following parameters: K = 8, M = 4, i.i.d. Rayleigh fading, and SNRS = —3 dB. The complexity is measured in terms of the (average) number of real multiplications required per decision. The dashed lines in Fig. 5.13 denote the number of multiplications required by the respective sphere decoders to find the first vector . and constitute the lower bounds for the actual complexity. Note that the lower bounds for the CV and ILS fusion rules practically coincide for the considered example. Fig. 5.13 shows that the CV fusion rule closely approaches the corresponding lower bound. In contrast, for the ILS and max—log fusion rules there is always 55 a considerable gap between the actual complexity and the lower bound even at high Eb/NO. For the ILS fusion rule, this gap is due to erroneous sensor decisions as can be observed from the comparison with the (hypothetical) case of ideal local sensor decisions. For the max—log fusion rule the gap is due to the fact that the sphere decoder does not only have to find the ML vector as for the CV and ILS fusion rules but also has to perform a constrained search over all ak with a(vo) = w3, j M, cf. Section 3.4. Nevertheless, all three suboptimal fusion rules have a significantly lower complexity than the optimal fusion rule. I I — Optimal Fusion Rule : —‘‘—CV —0--— ILS —f-—— ILS (Ideal Sensors) . . . . —e—— Max—Log 106 :;::::::: .::::::::.:: ::.;::::: ::..: i0 : : .: : : I : : : :.::. : I:::: : : : :.: I : :: I : : : : : :: : : : : : :1:: Max-44g — —:—:—:—:—:—:—:———N——————:—: 1:::::. :: : .: ::: ::. . : :: I : :1:::: :: : :1::::• :: I:: :: : :: III I ILS CV Eb/No [dB] Figure 5.13: Number of real multiplications per decision vs. Eb/No. M = 4, SNRS = —3 dB, and i.i.d. Rayleigh fading. 56 Chapter 6 Conclusions and Future Work 6.1 Research Contributions In this thesis, we have considered the distributed multiple hypothesis testing problem for mobile wireless sensor networks where sensors employ DPSK to cope with time—variant fading. We have shown that since differential mod ulation introduces memory, it is advantageous to consider fusion rules that base their decisions on an observation window of multiple symbol intervals. Specifically, we have derived the optimal MSD fusion rule (where complex ity increases exponentially with an increase in the number of sensors and the observation window size), and three suboptimal MSD fusion rules, where com plexity is linear in the number of sensors and, at high SNRs, polynomial in the observation window size. For binary hypothesis testing, performance bounds for the optimal fusion rule have been derived, and for the suboptimal fusion rules, exact or approximate expressions for the probabilities of false alarm and detection have been provided. Our simulation and analytical results show that for high and low channel SNR respectively, the performance of the CV and ILS fusion rules approach that of the optimal fusion rule. The proposed max—log fusion rule achieves a close—to—optimal performance over the entire SNR range 57 but has a higher complexity than the CV and ILS fusion rules. 6.2 Future Work There are several possible extensions of the work presented in this thesis and these are listed below. The first is to consider necessary modifications to the proposed fusion rules if they are adapted for different WSN topologies as discussed in Section 1.1, thereby giving a more generalized solution to the WSN decision fusion problem. The second is to consider whether our assumption of Rayleigh fading can be extended to other fading models. Rician fading should be investigated since there are viable scenarios where the FC and the sensors have direct line—of— sight. In particular, new sub-optimal fusion rules can be investigated since in Rician fading MSDSD is not optimal. A third area for futher development is error correction coding in WSN. The possibility of using error correcting codes to improve detection rates specifi cally at lower channel SNR can dramatically improve the CV fusion rule per formance. Moreover, coding can provide a means of reducing the problems related to faulty sensors that repeatedly send erroneous decisions due to sen sor malfunctions. 58 Bibliography [1] R. Viswanathan and P. K. Varshney. Distributed detection with multi ple sensors: Part I—Fundamentals. Proceedings of the IEEE, 85(1):54—63, January 1997. [2] L. Song and D. Hatzinakos. Architecture of wireless sensor networks with mobile sinks: sparsely deployed sensors. IEEE Trans. Veh. Tech nol., 56:1826—1836, July 2007. [3] A. Durresi, M. Durresi, and L. Barolli. Secure mobile communications for battlefields. In Proceedings of the International Conference Complex, Intelligent and Software Intensive Systems, pages 205—210, March 2008. [4] S. M. Mishra, A. Sahai, and R. W. Brodersen. Cooperative sensing among cognitive radios. In Proceedings of the IEEE International Conference on Communications (ICC’05), pages 11—15, Turkey, June 2006. [5] Z. Quan, S. Cui, A.H. Sayed, and H.V. Poor. Wideband spectrum sensing in cognitive radio networks. In Proceedings of the IEEE International Conference on Communications (ICC’08), pages 901—906, Turkey, May 2008. [6] A. D’Costa, V. Ramachandran, and A. M. Sayeed. Distributed classifi cation of gaussian space-time sources in wireless sensor networks. IEEE Trans. Commun., 22:1026—1036, August 2004. 59 [7] J. H. Kotecha, V. Ramachandran, and A. M. Sayeed. Distributed multi- target classification in wireless sensor networks. IEEE Trans. Commun., 23:703—713, April 2005. [8] R.W. Brodersen, A. Wolisz, D. Cabric, S.M. Mishra, and D. Willkomm. A cognitive radio approach for usage of virtual unlicensed spectrum. In Berkeley, CA: Univ. California Berkeley Whitepaper, July 2004. [9] J. Unnikrishnan and V.V. Veeravalli. Cooperative sensing for primary detection in cognitive radio. IEEE Trans. Signal Processing, 2:18—27, February 2008. [10] Z. Quan, S. Cui, and A.H. Sayed. Optimal linear cooperation for spec trum sensing in cognitive radio networks. IEEE Trans. Signal Processing, 2(1):28—40, February 2008. [11] p. K. Varshney. Distributed Detection and Data Fusion. Springer—Verlag, New York, 1997. [12] R. Tenney and N. Sandell, Jr.. Detection with distributed sensors. IEEE Trans. on Aerospace and Electronics Systems, 17(4):501—510, July 1981. [13] J. N. Tsitsiklis. Decentralized detection. Advances in Statistical Signal Processing, JAI Press Inc., 2:297—344, 1993. [14] R. S. Blum, S. A. Kassam, and H. V. Poor. Distributed detection with multiple sensors: Part IT—Advanced topics. Proceedings of the IEEE, 85(1):64—79, January 1997. [15] B. Chen, R. Jiang, T. Kasetkasem, and P. K. Varshney. Channel aware decision fusion in wireless sensor networks. IEEE Trans. Signal Processing, 52:3454—3458, December 2004. 60 [16] R. Niu, B. Chen, and P. K. Varshney. Fusion of decisions transmitted over Rayleigh fading channels in wireless sensor networks. IEEE Trans. Signal Processing, 54:1018—1027, March 2006. [17] R. Jiang and B. Chen. Fusion of censored decisions in wireless sensor networks. IEEE Trans. Wireless Commun., 4:2668—2673, Nov. 2005. [18] J.-F. Chamberland and V. Veeravalli. The impact of fading on decen tralized detection in power constrained wireless sensor networks. In Pro ceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 17—21, May 2004. [19] G. Mergen, V. Naware, and L. Tong. Asymptotic detection performance of type-based multiple access over multiaccess fading channels. IEEE Trans. Signal Processing, 55:1081—1092, March 2007. [20] T. Wimalajeewa and S. Jayaweera. Optimal power scheduling for corre lated data fusion in wireless sensor networks via constraint P50. IEEE Trans. Wireless Commun., 7:3608—3618, September 2008. [21] V. Kanchumarthy, R. Viswanathan, and M. Madishetty. Impact of chan nel errors on decentralized detection performance of wireless sensor net works: a study of binary modulations, Rayleigh-fading and nonfading channels, and fusion-combiners. IEEE Trans. Signal Processing, 56:1761— 1769, May 2008. [22] J.G. Proakis. Digital Communications. McGraw—Hill, New York, fourth edition, 2000. [23] D. Divsalar and M. K. Simon. Multiple-symbol differential detection of MPSK. IEEE Trans. Commun., 38:300—308, March 1990. 61 [24] D. Fung and P. Ho. Error performance of multiple-symbol differential de tection of PSK signals transmitted over correlated Rayleigh fading chan nels. IEEE Trans. Commun., 40:1566—1569, October 1992. [25] D. Divsalar and M. K. Simon. Maximum-likelihood differential detection of uncoded and trellis coded amplitude phase modulation over AWGN and fading channels—Metrics and performance. IEEE Trans. Gommun., 42:76—89, January 1994. [26] V. Pauli, R. Schober, and L. Lampe. A unified performance analysis framework for differential detection in MIMO Rayleigh fading channels. IEEE Trans. Gommun., 56:1972—1981, November 2008. [27] L. Lampe, R. Schober, V. Pauli, and C. Windpassinger. Multiple-symbol differential sphere decoding. IEEE Trans. Commun., 53:1981—1985, De cember 2005. [28] M.O. Damen, H.E. Gamal, and G. Caire. On maximum-likelihood de tection and the search for the closest lattice point. IEEE Trans. Inform. Theory, 49(10):2389—2402, October 2003. [29] A. Burg, M. Borgmann, M. Wenk, C. Studer, and H. Bolcskei. Advanced receiver algorithms for MIMO wireless communications. In Proceedings on Design, Automation and Test in Europe, volume 1, pages 593—598, March 2006. [30] Z. Guo and P. Nilsson. Algorithm and implementation of the k—best sphere decoding for MIMO detection. IEEE Trans. Commun., 24(3):491— 503, March 2006. [31] R. Schober, W. H. Gerstacker, and J. B. Huber. Decision—feedback dif ferential detection of MDPSK for fiat Rayleigh fading channels. IEEE Trans. Gomm’un., 47:1025—1035, July 1999. 62 [32] R. Schober and W. H. Gerstacker. Decision-feedback differential detection based on linear prediction for MDPSK signals transmitted over Ricean fading channels. IEEE J. Select. Areas Commun., 18:391—402, March 2000. [33] P. Hoeher, P. Robertson, and E. Villebrun. A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain. In Proceedings of the IEEE International Conference on Communications (ICC), pages 1009—1013, Seattle, June 1995. [34] J. Jalden and B. Ottersten. Parallel implementation of a soft output sphere decoder. Proc. of Asilomar Conference on Signals, Systems and Computers, pages 581—585, November 2005. [35] E. Biglieri, G. Caire, G. Taricco, and J. Ventura-Traveset. Computing error probabilities over fading channels: A unified approach. European Transactions on Telecommunications, 9:15—25, January-Feburary 1998. [36] H. David and H. Nagaraja. Order Statistics. Wiley, 2003. 63
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multiple--symbol differential decision fusion for wireless...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multiple--symbol differential decision fusion for wireless sensor networks Lei, Andre 2009
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Multiple--symbol differential decision fusion for wireless sensor networks |
Creator |
Lei, Andre |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | We consider the problem of decision fusion in mobile wireless sensor networks where the channels between the sensors and the fusion center are time—variant. We assume that the sensors make independent local decisions on the M hypotheses under test and report these decisions to the fusion center using differential phase—shift keying (DPSK), so as to avoid the channel estimation overhead entailed by coherent decision fusion. For this setup we derive the optimal and three low—complexity, suboptimal fusion rules which do not require knowledge of the instantaneous fading gains. Since all these fusion rules exploit an observation window of at least two symbol intervals, we refer to them collectively as multiple—symbol differential (MSD) fusion rules. For binary hypothesis testing, we derive performance bounds for the optimal fusion rule and exact or approximate analytical expressions for the probabilities of false alarm and detection for all three suboptimal fusion rules. Simulation and analytical results confirm the excellent performance of the proposed MSD fusion rules and show that in fast fading channels significant performance gains can be achieve by increasing the observation window to more than two symbol intervals. |
Extent | 1809645 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-11-09 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0068061 |
URI | http://hdl.handle.net/2429/14699 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_spring_lei_andre.pdf [ 1.73MB ]
- Metadata
- JSON: 24-1.0068061.json
- JSON-LD: 24-1.0068061-ld.json
- RDF/XML (Pretty): 24-1.0068061-rdf.xml
- RDF/JSON: 24-1.0068061-rdf.json
- Turtle: 24-1.0068061-turtle.txt
- N-Triples: 24-1.0068061-rdf-ntriples.txt
- Original Record: 24-1.0068061-source.json
- Full Text
- 24-1.0068061-fulltext.txt
- Citation
- 24-1.0068061.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0068061/manifest