According to equation(38),the upper-bound and lower-bound represented as of cx are(（esa-可+1and(a-可+1厂，respectively. F(x)=P{d(i,)<x} Since c 1 and cs >0 are arbitrary constants,we obtain that cx =1.Thus,(33)can be rewritten as P(d(i,j)<xRanki(j)=X)P(Ranki(j)=X). P(Rank,(j)-X=g+() 1 X=1 (41) (51) Now we analyze P[Ranki(j)=X}for three cases. Hence,the PDF can be expressed as Case 1:0<a<1.In this case,because of (29)and (30), fn(z,0)= dF(r） the sum of (41)is 1,which means that 2xxdx conl-o -∑Pd6)<Rak0)=月.PRomk.6)=R 1 2πrdc 9+C(qi,n)X= =1, (42) R台 Ca(qi;n)C(qi,n) where 1/2 c6<1 is constant.Therefore, =公宫哈era-e- con-<C(qi,n)<2c6n- x=1 2(qi+cxnl-oxa)xdr (43) which shows that C(gi,n)=cxn1-,where cx is related to 但 dIz2(X.n-X+1) cx and 1/2<cx<2.Hence,(33)can be rewritten as 2r(q+cxnl-aXa)xdz X=1 (52) 1 1 P(Ranki(j)=X) （9k+nl-aXa: where I(a,b)is the regularized incomplete beta function (44) and (a)holds due to equation (8.17.5)in [23].If gi> Case 2:a 1.We derive C(qi,n)and P[Ranki(j)=X} (2er)nz20,the PDF is as follow in the same way as in case 1.It can be obtained that fn(z,0) e(log0）imn→e品>1， ==m-2)X-1(1-x2)n-x n! C(g,n)=C(4,m)={e() limn→e=1, (45) 2qi+2mcxni-oXa and Xo (m-1)1 1 PI Ranki(j)=X=- +攻XC(,m=6 qi+XCi(qi,n) 2@白=m=e-x”+ (46 n (m-1)1 where 1/2<c<2. n 21)!(n-)x(x1--x Case 3:a>1.C(qi,n)and P{Ranki(j)=X}can also xk0+ be obtained in the similar way,and the results are C(qi,n)= θ(g-a)and 品会")6当 1 1 P(Ronk.()j=X灯=g+攻a-Xa=6+-x, ∑，2xx-m-xxa（ (m-1)1 (必)(-)-4 (47) where 1/2<c<2. ■ ”+ae-o+n Based on Lemma 4 and 5,the PDF of destinations is 2πq: 2ncx X8 obtained in the following theorem in polar coordinates. xqi Theorem 1 If node i is a source,and it selects qi destinations (53) based on (6).the location of each destination follows the distribution where Xo 克 ,a=器<(2e)1and坠ishe fn(,0)= (48) Tn a （4+nz2a lower-bound of cx which equals to 1/2.It should be noticed when0≤a<1,ad that the fn(,0)is uniform for different directions,and thus there is no in the expression of fn(,0).(a)in (53)holds n fn(x,0)=日 (49) due to the proof of Lemma 4 which shows that （9+nx2C(q,n) when a =1,and 乃-（产）-'1-)- -ci(ael-a)xo+1 (X-1)(n-X)！ X=X0+1 fn(x,0)=日 （9:+g-“nar2a (50) (54) when a>1 when a<(2e)-1.In the same way,it can also be proved that Proof:Firstly,we analyze the PDF for the case 0<a< ci(ael-a)xo+ina n (55) 1.For node i and its destination j,denoting the Cumulative h刚>a 78r Distribution Functions (CDF)of d(i,j)as Fi().it can be
6 According to equation (38), the upper-bound and lower-bound of cX are ⑨ 1 c5(c4−1) + 1❾2 and ⑨ 1 c5(c4−1) + 1❾−2 , respectively. Since c4 > 1 and c5 > 0 are arbitrary constants, we obtain that cX = 1. Thus, (33) can be rewritten as P{Ranki(j) = X} = 1 qi + C(qi, n)Xα , (41) Now we analyze P{Ranki(j) = X} for three cases. Case 1: 0 ≤ α < 1. In this case, because of (29) and (30), the sum of (41) is 1, which means that ❳n X=1 1 qi + C(qi, n)Xα = c6q 1−α α i C 1 α (qi, n) + c6n 1−α C(qi, n) = 1, (42) where 1/2 < c6 < 1 is constant. Therefore, c6n 1−α < C(qi, n) < 2c6n 1−α , (43) which shows that C(qi , n) = c 0 Xn 1−α, where c 0 X is related to cX and 1/2 < c0 X < 2. Hence, (33) can be rewritten as P{Ranki(j) = X} = 1 qi + c 0 Xn1−αXα = Θ ⑩ 1 qi + n1−αXα ❿ . (44) Case 2: α = 1. We derive C(qi , n) and P{Ranki(j) = X} in the same way as in case 1. It can be obtained that C(qi, n) = C1(qi, n) = ✚ Θ(log n qi ) limn→∞ n qi > 1, Θ(1) limn→∞ n qi = 1, (45) and P{Ranki(j)=X}= 1 qi + c 00 XXC1(qi, n) = Θ ⑩ 1 qi + XC1(qi, n) ❿ , (46) where 1/2 < c00 X < 2. Case 3: α > 1. C(qi , n) and P{Ranki(j) = X} can also be obtained in the similar way, and the results are C(qi , n) = Θ(q 1−α i ) and P{Ranki(j) = X} = 1 qi + c 000 X q 1−α i Xα = Θ ⑩ 1 qi + q 1−α i Xα ❿ , (47) where 1/2 < c000 X < 2. Based on Lemma 4 and 5, the PDF of destinations is obtained in the following theorem in polar coordinates. Theorem 1 If node i is a source, and it selects qi destinations based on (6), the location of each destination follows the distribution fn(x, θ) = Θ ⑩ n qi + nx2α ❿ , (48) when 0 ≤ α < 1, and fn(x, θ) = Θ ⑩ n qi + nx2C1(qi, n) ❿ , (49) when α = 1, and fn(x, θ) = Θ ⑩ n qi + q 1−α i nαx2α ❿ , (50) when α > 1. Proof: Firstly, we analyze the PDF for the case 0 ≤ α < 1. For node i and its destination j, denoting the Cumulative Distribution Functions (CDF) of d(i, j) as Fi(x), it can be represented as Fi(x) = P{d(i, j) < x} = ❳n X=1 P{d(i, j) < x|Ranki(j) = X}P{Ranki(j) = X}. (51) Hence, the PDF can be expressed as fn(x, θ) = dFi(x) 2πxdx = ❳n R=1 dP{d(i, j) < x|Ranki(j) = k} 2πxdx · P{Ranki(j) = R} = ❳n X=1 d Pn k=X n! k!(n−k)!(πx2 ) k (1 − πx2 ) n−k 2π(qi + c 0 Xn1−αXα)xdx (a) = ❳n X=1 dIπx2(X,n−X+1) 2π(qi + c 0 Xn1−αXα)xdx, (52) where Ix(a, b) is the regularized incomplete beta function and (a) holds due to equation (8.17.5) in [23]. If qi > (2eπ) αnx2α, the PDF is as follow fn(x, θ) = ❳n X=1 n! (X−1)!(n−X)!(πx2 ) X−1 (1 − πx2 ) n−X 2πqi + 2πc0 Xn1−αXα < n 2πqi ❳X0 X=1 (n − 1)! (X − 1)!(n − X)!(πx 2 ) X−1 (1 − πx 2 ) n−X+ n α ❳n X=X0+1 (n − 1)! 2πc0 X(X − 1)!(n − X)!Xα (πx 2 ) X−1 (1 − πx 2 ) n−X = n 2πqi ❳X0 X=1 (n − 1)! (X − 1)!(n − X)! ✏ aX0 n ✑X−1 ✏ 1 − aX0 n ✑n−X + n α ❳n X=X0+1 (n − 1)! 2πc0 X(X − 1)!(n − X)!Xα ✏ aX0 n ✑X−1 ✏ 1 − aX0 n ✑n−X (a) < n 2πqi + c1(ae1−a ) X0+1n α 2πc0 XXα 0 < n πqi , (53) where X0 = ➐ q 1 α i πn 1−α α ➓ , a = nx2 X0 < (2e) −1 and c 0 X is the lower-bound of c 0 X, which equals to 1/2. It should be noticed that the fn(x, θ) is uniform for different directions, and thus there is no θ in the expression of fn(x, θ). (a) in (53) holds due to the proof of Lemma 4 which shows that ❳n X=X0+1 (n − 1)! aX0 n ✁X−1 1− aX0 n ✁n−X (X − 1)!(n − X)! < c1(ae 1−a ) X0+1 , (54) when a < (2e) −1 . In the same way, it can also be proved that fn(x, θ) > n 2πqi − c1(ae1−a ) X0+1n α πc 0 XXα 0 > n 8πqi , (55)
wherec is the upper-bound of cx,which equals to 2.each side of Considering the fact that i has only 4 sides, Hence,fn(,0)=e()is proved when qi=w(nz20).the in the Theorem 2 is no greater than 2+2+4,which Moreover,if gi=O(nz2),after some similar mathematical is a constant.Thus the Conditions in Lemma 2 are satisfied. manipulations,the fn(x,can be represented as Similarly,the Conditions in Lemma 2 also hold in the case fn(z,0)=6(e-2a) 0<a<1 and a 1,and we do not show it in the following (56) proof for brevity. Consequently,the PDF for 0<a <1 is n We define gn(,0)=frfn(,0)drde when (,0)is (57)in where is a square region with side length r.If d V the difference between()and fn(,0)in Moreover,the fn(,for a 1 can be obtained in the can be derived as same way,and the results are shown in (49)and(50). ◆ rd+ According to Lemma 2 and Theorem 1,we analyze the Ifn(,0)-gn(,0)ldE< Ifn(,0)-gn(r,0)lxdrdo expression of the EMST]l in the following theorem. Jd-5 Cgr3 Theorem 2 When a =1,the expectation of the bound d3Ci(qi,n)' EMST in (11)satisfies (63) where<c<is constant.Thus,according to (53)and EMST VCi(q.n) qi w(log n), (58) (55),the condition 1 of Lemma 2 can be proved as follow 94 log n qi=O(logn). lfn(e,0)-9n(x,0)ldξ Furthermore,when 0<a 1,the expectation of the bound EMST in (11)satisfies Ifn(x,0)-gn(,0)xdrdo EMST=O(√a) (59) Finally,when a>1,the expectation of the bound EMST + nC1(qi.n) Ifn(,0)-gn(x,0)rdrdo in (11)satisfies 0(gfnl-a） g:=0(mg),1<a≤是， d+ fn(x,0)-gn(x,0)xdxde 合(gn学) g=w(n),1<a≤， Jd-5 EMST= o(4血n) g=0(m),是<a<2, 2% + ci(ael-)+x 6(g,2n学) g贴=w(m=),是<a<2, 2ncxcxqi ci(ael-a)xo+1(x+cx) 6(装) a≥2. < 2ncgr2 PCi(qi,n) + (60) cxex (64) Proof:Case 1:a =1.Based on Lemma 2 and Theorem 1,the EMSTI can be derived for different value of gi.If (a)holds because there are less than regions with side length r and d from the source.Moreover,considering the qi =w(logn),we prove that the lEMST]can be calculated relation between d and r in (62)and the maximum value of by (11)first.The network can be separated into some small square regions as in Lemma 2,and we assume that the side d is (64)can be bounded by length of the region which is d away from the source,is 2Tcgr2 (ael-a)o+1(④+x) r,where d>r.The number of destinations in this region is ∑C,n+ d c lower-bounded as ca(ae1-a)o+1(区+cx) (65) fa (E.0)de> xfn(r,0)drde= C8%r2 4rco log n + 2Ci(qi,n)' VesqiC1(qi,n) (61) =0(1): Therefore,the two conditions in Lemma 2 are satisfied.We whered≥Vncn),and÷<s<会is constant..tis denote that xt= necessary to guarantee that(61)is no less than 1,and therefore, Vnc)and the EMSTI is as dC(.Since a small r is needed for (which 2 、c8q1 EMSTI <c10c(d)vqi dxd0 satisfies Condition 1 in Lemma 2,r can be represented as Vqi+nCi(qi,n)x r=di C1(qi,n) (62) <2c1oc(d)nvqi t C(,n) csqi Moreover,d >r because qi =w(log n)=w(C1(qi,n)).Since d >r and r o da,there are at most 2+1 adjacent parts at <2coc(d)Ci(qi,n) (66
7 where c 0 X is the upper-bound of c 0 X, which equals to 2. Hence, fn(x, θ) = Θ( n qi ) is proved when qi = ω(nx2α). Moreover, if qi = O(nx2α), after some similar mathematical manipulations, the fn(x, θ) can be represented as fn(x, θ) = Θ x −2α ✁ . (56) Consequently, the PDF for 0 ≤ α < 1 is fn(x, θ) = Θ ⑩ max➜ x −2α , n qi ➟❿ = Θ ⑩ n qi + nx2α ❿ , (57) Moreover, the fn(x, θ) for α ≥ 1 can be obtained in the same way, and the results are shown in (49) and (50). According to Lemma 2 and Theorem 1, we analyze the expression of the kEMSTk in the following theorem. Theorem 2 When α = 1, the expectation of the bound kEMSTk in (11) satisfies kEMSTk = ✽ ❁ ✿ Θ ✏➮ qi C1(qi,n) ✑ qi = ω(log n), O ⑨ qi log n ❾ qi = O(log n). (58) Furthermore, when 0 ≤ α < 1, the expectation of the bound kEMSTk in (11) satisfies kEMSTk = Θ (√ qi). (59) Finally, when α > 1, the expectation of the bound kEMSTk in (11) satisfies kEMSTk = ✽ ❃❃❃❃❃❁ ❃❃❃❃❃✿ O q α i n 1−α ✁ qi = O(n α−1 α ), 1 < α ≤ 3 2 , Θ˜ ⑨ q α 2 i n 1−α 2 ❾ qi = ω(n α−1 α ), 1 < α ≤ 3 2 , O ✏ q α 2α−2 i n − 1 2 ✑ qi = O(n α−1 α ), 3 2 < α < 2, Θ˜ ⑨ q α 2 i n 1−α 2 ❾ qi = ω(n α−1 α ), 3 2 < α < 2, Θ˜ ⑨ √qi n ❾ α ≥ 2. (60) Proof: Case 1: α = 1. Based on Lemma 2 and Theorem 1, the kEMSTk can be derived for different value of qi . If qi = ω(log n), we prove that the kEMSTk can be calculated by (11) first. The network can be separated into some small square regions as in Lemma 2, and we assume that the side length of the region ξ, which is d away from the source, is r, where d > r. The number of destinations in this region is lower-bounded as ❩ ξ fn(x, θ)dξ > qi 2 ❩ r d 0 ❩ d+ r 2 d− r 2 xfn(x, θ)dxdθ = c8qir 2 d 2C1(qi , n) , (61) where d ≥ ➮ qi nC1(qi,n) , and 1 8π < c8 < 1 2π is constant. It is necessary to guarantee that (61) is no less than 1, and therefore, r ≥ d qC1(qi,n) c8qi . Since a small r is needed for gn(x, θ) which satisfies Condition 1 in Lemma 2, r can be represented as r = d ✃ C1(qi , n) c8qi . (62) Moreover, d > r because qi = ω(log n) = ω(C1(qi , n)). Since d > r and r ∝ d α, there are at most 2 α + 1 adjacent parts at each side of ξi . Considering the fact that ξi has only 4 sides, the ζ in the Theorem 2 is no greater than 2 α+2 + 4, which is a constant. Thus the Conditions in Lemma 2 are satisfied. Similarly, the Conditions in Lemma 2 also hold in the case 0 ≤ α < 1 and α > 1, and we do not show it in the following proof for brevity. We define gn(x, θ) = 1 r 2 ❘ ξ xfn(x, θ)dxdθ when (x, θ) is in ➮ ξ, where ξ is a square region with side length r. If d ≥ qi nC1(qi,n) , the difference between gn(x, θ) and fn(x, θ) in ξ can be derived as ❩ ξ |fn(x, θ) − gn(x, θ)|dξ < ❩ r d 0 ❩ d+ r 2 d− r 2 |fn(x, θ) − gn(x, θ)|xdxdθ = c9r 3 d 3C1(qi, n) , (63) where 1 8π < c9 < 1 π is constant. Thus, according to (53) and (55), the condition 1 of Lemma 2 can be proved as follow ❩ Ψ |fn(x, θ) − gn(x, θ)|dξ = ❩ 2π 0 ❩ 1 ➮ qi nC1(qi ,n) |fn(x, θ) − gn(x, θ)|xdxdθ + ❩ 2π 0 ❩ ➮ qi nC1(qi ,n) 0 |fn(x, θ) − gn(x, θ)|xdxdθ (a) < ❳ d 2πd r ❩ r d 0 ❩ d+ r 2 d− r 2 |fn(x, θ) − gn(x, θ)|xdxdθ + ❩ 2π 0 ❩ ➮ qi nC1(qi ,n) 0 c1(ae1−a ) X0+1(c 0 X + c 0 X)n 2πc 0 Xc 0 Xqi xdxdθ < ❳ d 2πc9r 2 d 2C1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X , (64) (a) holds because there are less than 2πd r regions with side length r and d from the source. Moreover, considering the relation between d and r in (62) and the maximum value of d is 1 2 , (64) can be bounded by ❳ d 2πc9r 2 d 2C1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X < 4πc9 log n ♣ c8qiC1(qi, n) + c1(ae1−a ) X0+1(c 0 X + c 0 X) c 0 Xc 0 X =o(1). (65) Therefore, the two conditions in Lemma 2 are satisfied. We denote that x † = ➮ qi nC1(qi,n) and the kEMSTk is as kEMSTk <c10c(d) √ qi ❩ 2π 0 ❩ 1 0 x ➱ n qi + nC1(qi, n)x2 dxdθ <2c10c(d)π √ qi ✧❩ x † 0 x √ n √qi dx + ❩ 1 x† ➱ 1 C1(qi, n) dx★ <2c10c(d)π ➱ qi C1(qi, n) , (66)