1 An Approximation of the First Order Marcum Q-Function with Application to Network Connectivity Analysis Mohammud Z. Bocus, Carl P. Dettmann and Justin P. Coon Abstract 2 1 Anexponential-typeapproximationofthefirstorderMarcumQ-functionispresented,whichisrobusttochanges 0 in its first argument and can easily be integrated with respect to the second argument. Such characteristics are 2 particularly useful in network connectivity analysis. The proposed approximation is exact in the limit of small first v argumentof the Marcum Q-function, in which case the optimal parameters can be obtained analytically. For larger o values of the first argument, an optimization problem is solved, and the parameters can be accurately represented N using regression analysis. Numerical results indicate that the proposedmethods result in approximationsvery close to the actual MarcumQ-functionfor small and moderatevalues of the first argument.We demonstratethe accuracy 3 1 of the approximation by using it to analyze the connectivity properties of random ad hoc networks operating in a Rician fading environment. ] T I . I. INTRODUCTION s c The Marcum Q-function, defined as the integral [1] [ ∞ x2+a2 2 Q (a,b) = xexp I (ax)dx (1) v 1 Z (cid:18)− 2 (cid:19) 0 b 7 6 for a,b 0 where I (x) is the modified Bessel function of the first kind, is a fundamental function that arises 0 0 in the p≥erformance evaluation of a wide class of communication systems [1]–[3]. From a mathematical point 2 of view, this function represents the complementary cumulative distribution function (CCDF) of the power of a . 0 Rician distribution. The integral representation of the function given by (1) cannot be manipulated easily to provide 1 2 simple expressions for the performance of communication systems, especially when the function Q1(a,b) must be 1 integrated with respect to one of its arguments [1]. To solve this issue, numerous works have proposed alternative : v representationsof Q1(a,b) to facilitate analysis (see, e.g., [3], [4] and referencestherein). Exponential-typebounds, i provided they are tight, have been particularly attractive, especially when evaluating the bit error rate at high X signal to noise ratio (SNR) [3], [5]. In other situations, approximations may be more suitable than bounds [6], r a [7]. However, such approximations may have complicated mathematical structures and/or be inaccurate in certain domains of their arguments. In this paper, a simple exponential approximation of the first order Marcum Q-function is presented that yields small approximation error over a large domain in its two arguments. The approximation is designed such that it can be used in situations where Q (a,b) must be integrated over its second argument. In what follows, a heuristic 1 approach is first employed to find the right form of the approximation, which is parameterized by two functions of a. An analytical framework for determining the correct parameterization is then explored, which is shown to be accurate for 0 a 1. For a 1, the optimal parameterization is calculated numerically. Although the ≤ ≪ ≫ proposed approximation is useful in its own right, it is particularly helpful in situations where the Q-function must be integrated. To illustrate this fact, we present an example application of our results whereby the proposed approximation is used to analyze the connectivity probability of a random ad hoc network operating in Rician fading channels. M. Z. Bocus and J. P. Coon are with the Telecommunications Research Laboratory, Toshiba Research Europe Ltd., 32 Queen Square, Bristol, BS1 4ND, U.K.; tel: +44 (0)117 906 0700, fax: +44 (0)117 906 0701. (e-mail: [email protected]). C. P. Dettmann is with the University of Bristol School of Mathematics, University Walk, Bristol, UK, BS8 1TW. J. P. Coon is also with the Department of Electrical and Electronic Engineering, University of Bristol, BS8 1UB, U.K. 2 The structure of this paper is as follows. In Section II, the proposed approximation and means of deriving the optimal a-dependentparameters are presented.An example application of the approximation is given in Section III, while the accuracy of the approximation is presented in Section IV. Finally, some concluding remarks are given in Section V. II. APPROXIMATION OF Q1(a,b) By plotting Q (a,b) as a function of b for various values of a, it can be readily observed that Q (a,b) decays 1 1 exponentially with b, where the value of a roughly defines the shift of Q along the b-axis. Consequently, we 1 propose to approximate Q (a,b) by the function 1 Q˜ (a,b) = exp eν(a)bµ(a) (2) 1 − (cid:16) (cid:17) where ν(a) and µ(a) are nonnegative parameters dependent upon a. The key is to choose these parameters such that the accuracy of the approximation is high. As previously discussed, we are concerned with obtaining an approximation that is useful over the range of the argument b for some fixed a. Thus, we define the approximation error as the function ∞ E(a)= (Q (a,b) Q˜ (a,b))2db. (3) 1 1 Z − 0 Furthermore, we define µ(a) and ν(a) to be polynomials of order m, where a larger value of m yields a better approximation. Thus, we have µ(a) = µ +µ a+µ a2+ +µ am 0 1 2 m ··· ν(a) = ν +ν a+ν a2+ +ν am 0 1 2 m ··· in which case the approximation becomes Q˜1(a,b) = exp ePmn=0(µnlnb+νn)an . (4) − (cid:16) (cid:17) Thegoalis now to choosethe coefficients µ ,...,µ ,ν ,...,ν , independentof b, suchthatE(a) is minimized. 0 m 0 m { } Depending on the value of the argument a, this can be done analytically or numerically. A. Analytical Approach for Small Arguments First, consider the case where 0 a 1. It is logical to expand Q (a,b) and Q˜ (a,b) about a = 0 and equate 1 1 the coefficients term by term. Of co≤urse,≪if the expansionsfor Q and Q˜ converge and the correspondingcoefficients match to arbitrary order, then Q = Q˜. Since this is clearly not the case, it is advisable to equate coefficients recursively, from lowest to highest order. For example, let m = 4. To leading order, we have Q (0,b) = exp( b2/2) and Q˜ (0,b) = exp( eν0bµ0). It 1 1 − − follows that we should choose µ = 2 and ν = ln2 since this ensures the approximation is exact at a = 0. 0 0 − Next, we can equate the first order terms to obtain the equation1 µ lnb+ν = 0. But we see from (4) that this 1 1 formula implies there is no O(a) term in the second exponent of Q˜. Thus, we may take µ = ν = 0 to maintain 1 1 independenceof b. This processcan be continuedin a straightforward manner. However,when we equatethe fourth order terms, we obtain the equation µ lnb+ν = b2/32, and thus either µ or ν is dependent upon b, a condition 4 4 4 4 that is not allowed by our definition of the polynomials µ and ν. Instead, we can optimize E(a) over µ and ν by 4 4 differentiating with respect to each variable, setting the results to zero, and solving for µ and ν . This yields the 4 4 optimal fourth order polynomials 9 µ(a) = 2+ a4 8(9π2 80) − a2 45π2+72ln2+36C 496 ν(a) = ln2 + − a4 − − 2 64(9π2 80) − which are independentof b, and thus satisfy the conditionsof our approximation2. By substituting theseexpressions for µ(a) and ν(a) into Q˜ and evaluating the integral in (3) for small a, it is apparent that E(a) 7.5 10−5a8. ≈ × Thus, the fourth order result is very accurate for a 1, an observation that is corroborated by Fig. 1. ≪ 1The details of the calculations are straightforward but lengthy, and are thus omitted here for brevity. 2The symbol C denotes the Euler-Mascheroni constant, where C ≈0.5772. 3 10−2 10−4 10−6 ) a ( E 10−8 10−10 E(a)evaluatedusing(3) E(a)≈7.5×10−5a8 10−12 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 a Fig. 1. Approximation error derived from fourth order polynomial representation of µ(a) and ν(a) for small a. TABLEI SUITABLEν ANDµFORDIFFERENTa a ν µ 1.0000 −1.1739 2.0921 2.0000 −2.5492 2.7094 3.0000 −4.6291 3.6888 4.0000 −7.1668 4.7779 5.0000 −10.0339 5.9074 6.0000 −13.2014 7.0794 B. Numerical Approach for General Arguments While a closed-form expression for the coefficients of µ and ν can be obtained for small a, performing a similar analysis for larger values of a is somewhatproblematic. On that account, a numerical approach is followed instead. In particular, we propose to determine the appropriate values of µ and ν such that the following error is minimized: ∞ Eˆ = δ (Q (a,δβ) exp( eν(δβ)µ))2 (5) 1 − − Xβ=0 where δ is small and Eˆ E as δ 0. Such optimization problems can be solved using numerical techniques → → [8]. It should be noted that the problem of minimizing the error term defined in (5) is not a convex optimization problem. As such, numerical methods may not always converge to the global optimum. Nevertheless, we find that the observed optimum is often adequate, as illustrated in Section IV. Since Q (a,b) decays exponentially with b, we argue that we can ignore terms in the summation in (5) 1 corresponding to values of b larger than some b in order to facilitate optimization. This is particularly justified max by noting that we are interested in obtaining an accurate expression for Q that captures most of its mass. Thus, 1 the upper limit on the summation in (5) can be replaced by β = b /δ. As an example, we set δ = 10−4 max max and b = 12, and solved the above optimization problem using a line-search algorithm for several values of a. max Results are shown in Table I. Using the values listed in Table I, it is possible to derive an approximate expression for µ(a) and ν(a) using polynomial regression [9]. For instance, assuming that µ(a) is a polynomial of fourth order in a, the regression model for µ(a) can be expressed as µ(a ) = µ˜ +µ˜ a +µ˜ a2+µ˜ a3+µ˜ a4+ǫ (6) j 0 1 j 2 j 3 j 4 j j for j = 1,...,N where ǫ is the error in the approximation, µ˜ 4 are the estimation coefficients, and N is the number of observed instanjces (c.f. Table I). The above expres{sioi}ni=c1an be written in matrix form as µ = Aµ˜ +ǫ, 4 10 5 0 µ ν, −5 Optimizedvalueofµ Approx.valueofµfrom(7) −10 Optimizedvalueofν Approx.valueofνfrom(7) −15 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 a Fig. 2. Plots of µ(a) and ν(a) obtained through a numerical approach. The solid lines represent the optimized values, while the squares and circles show the approximate values from (7). T whereµ˜ = [µ˜ , ,µ˜ ]T andµissimilarlydefined,AisanN 5matrixwithkthcolumnbeing ak−1, ,ak−1 0 ··· 4 × 1 ··· N h i for k = 1,...,5, and ǫ = [ǫ , ,ǫ˜ ]T. Using ordinary least squares estimation, the coefficients can be obtained 1 N using µ˜ = ATA −1ATµ. Fo·r··m = 4, this approach yields (cid:0) (cid:1) µ(a) = 2.174 0.592a+0.593a2 0.092a3 +0.005a4 − − ν(a)= 0.840+0.327a 0.740a2 +0.083a3 0.004a4. (7) − − − Fig. 2 depicts the comparison between the optimized values (from Table I) and approximated values of the two parameters given in (7). It can be observed from the plots that the two sets of values are very close, indicating the suitability of the above two equations. Such approximations are convenient if fast computation of the parameters ν(a) and µ(a) are required. III. AN APPLICATION OF THE PROPOSED APPROXIMATION As previously stated, the presented approximation can be particularly useful when the CCDF of the power of a Rician channel needs to be integrated over the second argument. The power of a Rician channel is noncentral-χ2 distributed, whose CCDF is given by F (x) = Q √2K, 2ω−1(K +1)x (8) X 1 (cid:16) p (cid:17) where K is the Rice factor and ω is a channel dependent parameter. Given that a = √2K in this case and, in general, 1 K 10 [10], it follows that a < 5. On that account, the approximations of the parameters µ(a) and ≤ ≤ ν(a) presented above can readily be used. To demonstratethe useofthe proposedapproximationofthe MarcumQ-function, weconsiderthe analysisofthe full connection probability of a random ad hoc network, similar to the work presented in [11], [12]. Consider the connection probability of two nodes in a system, which we denote by H, given a minimum data rate requirement of R . By adopting an information theoretic definition of connectivity, we define 0 H = P log (1+γ h2) R (9) 2 | | ≥ 0 (cid:0) (cid:1) where h2 is the channel gain between the two nodes and γ is the SNR which is dependent upon the distance | | betweenthetwonodesandotherparameterssuchasthepathlossexponentandantennagains.Undertheassumption of a Rician fading channel with Rice factor K and a path loss exponent of two for illustration, we have H(r) = Q √2K,rα where r is the distance between the two nodes and α is a function of the system parameters. To 1 der(cid:0)ive the pro(cid:1)bability that the network is fully connected, it is necessary to average H(r) over the configuration 5 1 ExactValue 0.9 e−νbµwithoptimalparameters 0.8 e−νbµwithapproximateparameters Approximationin[7] 0.7 0.6 b) a,(0.5 1 Q 0.4 a=1 a=2 0.3 a=3 0.2 a=5 a=4 0.1 0 0 1 2 3 4 5 6 7 8 9 10 b Fig.3. Comparison oftheMarcum Q-functionwiththeproposed approximation andthat presented in[7].Forlarger a,theapproximation in [7] diverges from the actual curve for small b. Optimal parameters for the approximations are obtained by minimizing (5), while the approximate parameters are obtained from (7). space [12]. For a homogeneous system, this amounts to averaging H(r) over all distances between nodes. Such a calculation would involve an integral of the form (c.f., (19)-(21) in [12] for Rayleigh fading) r2 r2 rH(r)dr = rQ √2K,rα dr 1 Zr1 Zr1 (cid:16) (cid:17) r2 re−eν(rα)µdr ≈ Z r1 = 1λ−µ2 γ(2,λrµ) γ(2,λrµ) (10) µ (cid:18) µ 2 − µ 1 (cid:19) whereλ = eναµ, r and r are the minimum andmaximumdistancesbetweennodeswithin the system,andγ(x,y) 1 2 is the lower incomplete gamma function. The complete analysis of the full connection probability is beyond the scope of this letter. What is important to note is that without the approximation derived in this paper, solving the integral stated above would be very challenging if not impossible. IV. ACCURACY OF THE APPROXIMATION To demonstrate the accuracy of the proposed approximation, we compare the proposed method to an existing approximation in the literature [7] that generally yields small approximation error. The comparisons are shown in Fig. 3. For the approximation presented in [7], the value of k was set to 50 in equation (6) therein. It can be observed from the plot that, for small a, the proposed approximations are close to the Marcum Q-function. However, as a increases, divergence from the actual curve is seen for the approximation of [7]. Nevertheless, the proposed approximations still adequately represent the mass of the Marcum Q-function over the range of b values; consequently, our approximation is robust with respect to changes in a. For large values of b, we note that existing bounds and approximations in the literature often provide a more accurate representation of Q (a,b) compared to the proposed method. This can easily be observed graphically, but 1 we omit the results here due to space constraints. For applications that require a closer approximation for large b, the expressions in [4], [7] and references therein would be more appropriate. However, if the integral of the Marcum Q-function over the domain of the second argument is sought, the approximation presented in this paper is more suitable. WenextcompareEˆ forourproposedapproximationandthe onegivenin[7].ResultsshowninFig.4 fordifferent values of a demonstrate the accuracy of the proposed scheme. As mentioned in the previous section, the range of a values considered in the plot is the range that would typically be encountered in practice in communication systemanalysis.However,for the problemdefinedin (5), it is guaranteedthat the solutionwould minimize theerror term for any value of a. The reader should also bear in mind that the method presented in this paper minimizes 6 100 10−2 10−4 ˆE 10−6 10−8 ErrorwithOptimalνandµ ErrorwithApproximatedνandµfrom(7) Errorwithapprox.in[7] 10−10 1 1.5 2 2.5 3 3.5 4 4.5 5 a Fig. 4. Comparison of the approximation error Eˆ using the proposed approach and the one given in [7]. The proposed approximation remains robust to changes in a.) a particular definition of the approximation error. Depending on the application, other objective functions may be defined. V. CONCLUSION In this paper, a simple approximation of the first order Marcum Q-function was presented that can be used in network connectivity analysis. For small input argument a, an analytical approach was presented for finding the approximation parameters, while for larger a, a numerical procedure based on an optimization problem was proposed. Equations for approximating these parameters were then presented. Simulation results demonstrated that the approximations led to an accurate representation of the Marcum Q-function, especially for small values of b. As b tends to infinity however, existing bounds of Q (a,b) yield to a closer representation of the function. 1 ACKNOWLEDGEMENT TheauthorswouldlikethankToshibaTelecommunicationsResearchLaboratoryandtheEPSRC(grantEP/H500316/1) for their continued support. REFERENCES [1] M.K.SimonandM.-S.Alouini,“SomeNewResultsforIntegralsInvolvingtheGeneralizedMarcumQ-FunctionandtheirApplication to Performance Evaluation over Fading Channels,” IEEE Trans. Wireless Commun., vol. 2, no. 4, pp. 611–615, 2003. [2] C. O’driscoll and C. Murphy, “A Simplified Expression for the Probability of Error for Binary Multichannel Communications,” IEEE Trans. Commun., vol. 57, no. 1, pp. 32–35, 2009. [3] H. Fuand P.-Y.Kam, “Exponential-Type Bounds on theFirst-Order Marcum Q-Function,”in Proc. IEEEGlobal Telecommunications Conf. (GLOBECOM2011), 2011, pp. 1–5. [4] X.Zhao,D.Gong,andY.Li,“TightGeometricBoundforMarcumQ-Function,”ElectronicsLetters,vol.44,no.5,pp.340–341,2008. [5] M. K. Simon and M.-S. Alouini, “Exponential-Type Bounds on the Generalized Marcum Q-Function with Application to Error Probability Analysis Over Fading Channels,” IEEE Trans. Commun., vol. 48, no. 3, pp. 359–366, 2000. [6] N.DingandH.Zhang, “AFlexibleMethod toApproximateMarcumQ-FunctionBasedonGeometricWayofThinking,”inProc.3rd Int. Symp. Communications, Control and Signal Processing ISCCSP 2008, 2008, pp. 1351–1356. [7] P. C. Sofotasios and S. Freear, “Novel Expressions for the Marcum and One Dimensional Q-Functions,” in Proc. 7th Int Wireless Communication Systems (ISWCS) Symp, 2010, pp. 736–740. [8] B. Ake, Numerical Methods forLeast Squares Problems. Societyfor Industrial and AppliedMathematics, 1996. [Online]. Available: http://epubs.siam.org/doi/abs/10.1137/1.9781611971484 [9] A. R. Luxmoore, “Statistical Methods for Engineers and Scientists,” International Journal for Numerical Methods in Engineering, vol. 14, no. 2, pp. 313–313, 1979. [Online]. Available: http://dx.doi.org/10.1002/nme.1620140217 [10] J. Proakis, Digital Communications, 4th ed. McGraw-Hill Higher Education, Sept 2000, iSBN-13: 978-0072321111. [11] D. Miorandi, “The Impact of Channel Randomness on Coverage and Connectivity of Ad Hoc and Sensor Networks,” IEEE Trans. Wireless Commun., vol. 7, no. 3, pp. 1062–1072, 2008. [12] J. Coon, C. P. Dettmann, and O. Georgiou, “Full Connectivity: Corners, Edges and Faces,” Journal of Statistical Physics, vol. 147, pp. 758–778, 2012. [Online]. Available: http://dx.doi.org/10.1007/s10955-012-0493-y