正在加载图片...
in Appendix B are tight.From(18)and(48),we have partition,in each cell of areaM logn,randomly select a server of a class-i content that has not been replicated as E[M]=Θ log n a sender.Then the sender broadcasts the class-i content n27 (20) within the cell. Retrieval phase:The retrieval phase consists of Given a request state Q and a content class i,the number of 9W log2n timeslots.At the beginning of each timeslot of requests nik could be different for different k.Denote n the retrieval phase,we partition the unit square into cells Elni.We then choose a determinist value of possibly different sizes,for feasible retrieval pairs of different classes,using the same method as the one in log n M;=0 ∑1n (21) scheme I.After all feasible retrieval pairs are included in =1 the corresponding retrieval cells,we further divide each retrieval cell into hop-cells,each of area ).6 After for all Mi,k=1,...K.Since pi decreases with index i,we the partition,in each retrieval cell of area R2,randomly have M≥M≥.≥Mh.And it is easy to show that for select a feasible class-i retrieval pair.Then the server all i and k,ni ni logn and E [Mi]Mi logn,w.h.p..In is scheduled to deliver the requested class-i content to addition,letting (43)hold with equality,we have the client in a multihop manner along hop-cells in the 1 E[R,d4k」= (22) same retrieval cell.Each hop-cell is active once in every √E[M]Wo log n 9 timeslots.In each active hop-cell,if there exists a server of the requested class-i content,select it as a sender and a Similarly,given a request state Q and a content class i,we random node from its neighboring hop-cells as a receiver. will choose a determinist value Ri for all Rid,where Ri Then the sender forwards the content to the receiver until is given by it is retrieved by the client. 1 Ri=M:W logn (23) Theorem 4:Under Scheme II,the average delay of serving all nk requests is upper bounded by We choose W to be the R.H.S of (18).i.e.,W (K∑p)iogn) .Then,from (21)and (23).we can Proof:Under Scheme II,content delivery delay is com- posed of two parts:placement delay and retrieval delay. obtain Similar to the previous placement analysis,we first show 1 that each content ik will have at least Mi(21)copies at the (24) ogn∑-∑1n2)n end of the placement phase.For a server of a content ik,if it is scheduled to replicate content ik,on average Mi logn Since pi decreases with index i,we have R1≤B2≤…≤ nodes (at least Mi nodes)that reside in the same cell as the RI. server will receive the copies.Hence,according to Scheme Similarly,since it is more efficient to first replicate contents II,on averageM.logn copies over all contents are generated in the placement phase.Since each cell can be and transmit the replicas to all the selected servers and then deliver the replicas to all the clients with the help of these activated once at most every 9 timeslots,there are totally no servers,we conduct content delivery in two adjacent phases, less than an copies generated in each timeslot.It then follows i.e.,placement phase and retrieval phase. that the total time required for the placement phase is no Based on the above discussions,we propose the following greater than (∑)ogm timeslots. distributed scheme under slow mobility,for any request state Second,we show that the requests of all clients will be Q.Later,we will show that the proposed scheme can achieve satisfied at the end of the retrieval phase.It has been proved performance with a gap from the optimal performance up to a factor of log n. that if the area of each cell is no smaller than then each cell has at least one node w.h.p.[20].Therefore, Scheme II for slow mobility: each hop-cell contains at least one node and can guarantee Placement phase:The placement phases consists of the multihop transmissions. 9W log2n timeslots.At the beginning of each timeslot For a client of content ik,the probability that at least of the placement phase,we partition the unit square into one server moves into its retrieval range is 1(1RM cells of possibly different sizes,for contents of different Following a similar approach to the one in the proof of classes.Specifically,we first partition the unit square into Theorem 2,the probability can be approximated as MR?. cells for class-1 contents,each of area logn.For Recall that such kind of pairs are defined as feasible retrieval each cell which does not contain any unreplicated class- pairs of content ik.Once there exists a feasible retrieval pair 1 contents,we further partition it into smaller cells for of content ik in a cell of area R2,with at least probability class-2 contents,each of area Ma logn.The cell partition it is scheduled for transmissions along multiple hop-cells in a proceeds in this way for I rounds in total.After the timeslot.The probability of completing the content delivery of SNote that the placement phase under slow mobility is the same as that Note that we set the hop-cell area equalo)toensure that there under fast mobility.We present it here for the sake of completeness. is at least one node in it w.h.p.as noo [20].7 in Appendix B are tight. From (18) and (48), we have E [Mik ] = Θ n 1 2 n 2 3 ik log n PI i=1 PK k=1 n 2/3 ik !1/4 . (20) Given a request state Q and a content class i, the number of requests nik could be different for different k. Denote ni , E[nik ]. We then choose a determinist value Mi = Θ n 1 2 n 2 3 i log n PI i=1 PK k=1 n 2/3 i !1/4 , (21) for all Mik , k = 1, ..., K. Since pi decreases with index i, we have M1 ≥ M2 ≥ ... ≥ MI . And it is easy to show that for all i and k, nik ≤ ni log n and E [Mik ] ≤ Mi log n, w.h.p.. In addition, letting (43) hold with equality, we have E Rik,dik = 1 È E [Mik ] W¯ Q log n . (22) Similarly, given a request state Q and a content class i, we will choose a determinist value Ri for all Rik,dik , where Ri is given by Ri = Ê 1 MiW¯ log n . (23) We choose W¯ to be the R.H.S of (18), i.e., W¯ = Θ K log n PI i=1 p 2 3 i 3/4 . Then, from (21) and (23), we can obtain Ri = Θ 1 log n PI i=1 PK k=1 n 2/3 i 1/4 n 1/3 i . (24) Since pi decreases with index i, we have R1 ≤ R2 ≤ ... ≤ RI . Similarly, since it is more efficient to first replicate contents and transmit the replicas to all the selected servers and then deliver the replicas to all the clients with the help of these servers, we conduct content delivery in two adjacent phases, i.e., placement phase and retrieval phase. Based on the above discussions, we propose the following distributed scheme under slow mobility, for any request state Q. Later, we will show that the proposed scheme can achieve performance with a gap from the optimal performance up to a factor of log2 n. Scheme II for slow mobility: • Placement phase: The placement phase5 consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the placement phase, we partition the unit square into cells of possibly different sizes, for contents of different classes. Specifically, we first partition the unit square into cells for class-1 contents, each of area M1 n log n. For each cell which does not contain any unreplicated class- 1 contents, we further partition it into smaller cells for class-2 contents, each of area M2 n log n. The cell partition proceeds in this way for I rounds in total. After the 5Note that the placement phase under slow mobility is the same as that under fast mobility. We present it here for the sake of completeness. partition, in each cell of area Mi n log n, randomly select a server of a class-i content that has not been replicated as a sender. Then the sender broadcasts the class-i content within the cell. • Retrieval phase: The retrieval phase consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the retrieval phase, we partition the unit square into cells of possibly different sizes, for feasible retrieval pairs of different classes, using the same method as the one in scheme I. After all feasible retrieval pairs are included in the corresponding retrieval cells, we further divide each retrieval cell into hop-cells, each of area Θ log n n . 6 After the partition, in each retrieval cell of area R2 i , randomly select a feasible class-i retrieval pair. Then the server is scheduled to deliver the requested class-i content to the client in a multihop manner along hop-cells in the same retrieval cell. Each hop-cell is active once in every 9 timeslots. In each active hop-cell, if there exists a server of the requested class-i content, select it as a sender and a random node from its neighboring hop-cells as a receiver. Then the sender forwards the content to the receiver until it is retrieved by the client. Theorem 4: Under Scheme II, the average delay of serving all nK requests is upper bounded by Θ K PI i=1 p 2 3 i 3 4 log 5 4 n . Proof: Under Scheme II, content delivery delay is composed of two parts: placement delay and retrieval delay. Similar to the previous placement analysis, we first show that each content ik will have at least Mi (21) copies at the end of the placement phase. For a server of a content ik, if it is scheduled to replicate content ik, on average Mi log n nodes (at least Mi nodes) that reside in the same cell as the server will receive the copies. Hence, according to Scheme II, on average PI i=1 PK k=1 Mi log n copies over all contents are generated in the placement phase. Since each cell can be activated once at most every 9 timeslots, there are totally no less than 1 9 n copies generated in each timeslot. It then follows that the total time required for the placement phase is no greater than 9 PI i=1 PK k=1 n 2 3 i 3/4 (log n) 5 4 √ n timeslots. Second, we show that the requests of all clients will be satisfied at the end of the retrieval phase. It has been proved that if the area of each cell is no smaller than Θ log n n , then each cell has at least one node w.h.p. [20]. Therefore, each hop-cell contains at least one node and can guarantee the multihop transmissions. For a client of content ik, the probability that at least one server moves into its retrieval range is 1 − 1 − R2 i Mi . Following a similar approach to the one in the proof of Theorem 2, the probability can be approximated as MiR2 i . Recall that such kind of pairs are defined as feasible retrieval pairs of content ik. Once there exists a feasible retrieval pair of content ik in a cell of area R2 i , with at least 1 9 probability it is scheduled for transmissions along multiple hop-cells in a timeslot. The probability of completing the content delivery of 6Note that we set the hop-cell area equal to Θ log n n , to ensure that there is at least one node in it w.h.p. as n → ∞ [20].