1596 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 For example,when the contact duration is uniformly dis-It can be verified that U(ti)is always a concave and increasing tributed as shown n(9,we have户nmis(T）='=景rmis(T), function for the three distributions we discussed above.Using which is smaller than the single user missing probability only by the Karush-Kuhn-Tucker (KKT)conditions [16],we have a constant factor. U()=c (16) III.NONSTATIONARY INTERCONTACT TIMES Until now,we have made the simplifying assumption that the for all nonzero optimal solutions 4.Note that =0 when intercontact times are stationary.This assumption is clearly not c.The energy cost cis a constant that can be obtained true.For example,one would expect the intercontact time pat- by solving the dual of(15).The optimal T*can then be solved terns late at night to differ significantly from the intercontact from time distribution during lunch hours or peak traffic hours.This implies that the optimal contact-probing interval will vary with )=关 (17) time.In the following sections,we study the contact arrival pro- cesses where the average contact arrival rate varies with time.In for a given Ai.In practice,we can set the parameter c instead this case,we assume that the contact arrival rate is constant over of N to achieve a certain tradeoff point between energy and some short time period of duration L.As before,we assume the missing probability.A larger value of c means energy is more contact durations are i.i.d..This assumption will be justified in precious(smaller N)and less energy will be used in the M time Section VI. slots.Consequently,the overall contact-missing probability will be larger.Once the parameter c is set,we can use(17)to calcu- A.Problem Formulation late the optimal T*based on the estimate of Ai for a time slot i. This solution minimizes the missing probability over all time, We divide the time to slots with equal duration of L.We de- subject to energy constraints,which are determined by the en- note the average contact arrival rate in the ith time slot as Ai. ergy cost c. We proved in Theorem 1 that using a constant con- Example /Let the contact duration distribution be uniform. tact-probing interval of T is optimal during the ith time L=1 h,and N is the number of times the device can probe slot.In this case,the expected number of contacts captured in 24 h.Then,the optimal contact-probing interval T*for the during time period i will be Ai(1-Pniss(T).However,to arrival rate.入zis minimize the overall contact-missing probability,the optimal probing intervals Ti could be different for different time slots AC that have a different arrival rate of Ai.Intuitively,more energy (18) u入 should be spent in time slots with high arrival rates to capture more contacts so that the overall contact missing probability by(I7).If the:are all equal,.then clearlyT=装，∀i.There- can be minimized. Consider the problem of maximizing the number of contacts ore,c=学（装）2 and Pi(T)=裴when T≤a captured over M time slots,given a constraint on the total en- ergy used in the M time slots.This problem is equivalent to min- B.Discussion imizing the contact-missing probability over the M time slots. In Section II,we show that a constant probing rate is optimal As each probe consumes equal energy,the constraint on total for stationary processes,and the optimal tradeoff points can energy consumption can be converted to a constraint of total be derived from (1).In this section,we show that the average number of probes used in the M time slots.Assume that the de- vice can take N probes during the M time slots.We can then missing probability can be further reduced when the contact arrival rate is time-varying.When the contact arrival ratesAi formulate the following optimization problem to find the op- are different in different time slots,we can use adaptive contact timal probing interval T for each time slot: probing to redistribute the limited probing energy according to the contact arrival rate.For a time slot with high contact Maximize 入(1-Pmis(T) arrival rate,we can increase the probing rate and reduce the missing probability so that most contacts arriving in this time i=1 M slot can be captured.When the contact arrival rate is low,the ≤N T≥0 i. (14) contact-probing rate can be reduced since the number of missed s.t i=1 contacts入：LPmiss(T)will be small for a small入i,even if Pisquite high.In this way.the overall missing probability Defining variable ti as 1/Ti and Ui(i)=Ai(1-Pmiss(1/i)), (can be minimized.However,the missing the optimization in(14)can be recast as M AL probability for time slots with low arrival rates could be very M high in this case. Maximize Ui(xi) We now make two observations regarding the the optimiza- =1 tion in (14).First,when the contact arrival rates are equal for all M time slots,it is not necessary to use different probing intervals S.t Lx≤N x≥0 Vi. (15) in different time slots,and a constant probing rate is optimal. In this scenario.the solution to (14)reduces to the solution for1596 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 For example, when the contact duration is uniformly dis￾tributed as shown in (9), we have , which is smaller than the single user missing probability only by a constant factor. III. NONSTATIONARY INTERCONTACT TIMES Until now, we have made the simplifying assumption that the intercontact times are stationary. This assumption is clearly not true. For example, one would expect the intercontact time pat￾terns late at night to differ significantly from the intercontact time distribution during lunch hours or peak traffic hours. This implies that the optimal contact-probing interval will vary with time. In the following sections, we study the contact arrival pro￾cesses where the average contact arrival rate varies with time. In this case, we assume that the contact arrival rate is constant over some short time period of duration . As before, we assume the contact durations are i.i.d.. This assumption will be justified in Section VI. A. Problem Formulation We divide the time to slots with equal duration of . We de￾note the average contact arrival rate in the th time slot as . We proved in Theorem 1 that using a constant con￾tact-probing interval of is optimal during the th time slot. In this case, the expected number of contacts captured during time period will be . However, to minimize the overall contact-missing probability, the optimal probing intervals could be different for different time slots that have a different arrival rate of . Intuitively, more energy should be spent in time slots with high arrival rates to capture more contacts so that the overall contact missing probability can be minimized. Consider the problem of maximizing the number of contacts captured over time slots, given a constraint on the total en￾ergy used in the time slots. This problem is equivalent to min￾imizing the contact-missing probability over the time slots. As each probe consumes equal energy, the constraint on total energy consumption can be converted to a constraint of total number of probes used in the time slots. Assume that the de￾vice can take probes during the time slots. We can then formulate the following optimization problem to find the op￾timal probing interval for each time slot: (14) Defining variable as and , the optimization in (14) can be recast as (15) It can be verified that is always a concave and increasing function for the three distributions we discussed above. Using the Karush–Kuhn–Tucker (KKT) conditions [16], we have (16) for all nonzero optimal solutions . Note that when . The energy cost is a constant that can be obtained by solving the dual of (15). The optimal can then be solved from (17) for a given . In practice, we can set the parameter instead of to achieve a certain tradeoff point between energy and missing probability. A larger value of means energy is more precious (smaller ) and less energy will be used in the time slots. Consequently, the overall contact-missing probability will be larger. Once the parameter is set, we can use (17) to calcu￾late the optimal based on the estimate of for a time slot . This solution minimizes the missing probability over all time, subject to energy constraints, which are determined by the en￾ergy cost . Example 1: Let the contact duration distribution be uniform, h, and is the number of times the device can probe in 24 h. Then, the optimal contact-probing interval for the arrival rate is (18) by (17). If the are all equal, then clearly . There￾fore, and when . B. Discussion In Section II, we show that a constant probing rate is optimal for stationary processes, and the optimal tradeoff points can be derived from (1). In this section, we show that the average missing probability can be further reduced when the contact arrival rate is time-varying. When the contact arrival rates are different in different time slots, we can use adaptive contact probing to redistribute the limited probing energy according to the contact arrival rate. For a time slot with high contact arrival rate, we can increase the probing rate and reduce the missing probability so that most contacts arriving in this time slot can be captured. When the contact arrival rate is low, the contact-probing rate can be reduced since the number of missed contacts will be small for a small , even if is quite high. In this way, the overall missing probability can be minimized. However, the missing probability for time slots with low arrival rates could be very high in this case. We now make two observations regarding the the optimiza￾tion in (14). First, when the contact arrival rates are equal for all time slots, it is not necessary to use different probing intervals in different time slots, and a constant probing rate is optimal. In this scenario, the solution to (14) reduces to the solution for