# On-Demand Mobile Data Collection in Cyber-Physical Systems

Authors: Liang He; Linghe Kong; Jun Tao; Jingdong Xu; Jianping Pan
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

The collection of sensory data is crucial for cyber-physical systems. Employing mobile agents (MAs) to collect data from sensors offers a new dimension to reduce and balance their energy consumption but leads to large data collection latency due to MAs’ limited velocity. Most existing research effort focuses on the offlinemobile data collection (MDC), where the MAs collect data from sensors based on preoptimized tours. However, the efficiency of these offline MDC solutions degrades when the data generation of sensors varies. In this paper, we investigate the on-demand MDC; that is, MAs collect data based on the real-time data collection requests from sensors. Specifically, we construct queuing models to describe theFirst-Come-First-Serve-based MDC with a single MA and multiple MAs, respectively, laying a theoretical foundation. We also use three examples to show how such analysis guides online MDC in practice.


---

## Body

## 1. Introduction

Collecting data from sensors is a core function of large cyber-physical systems such as wind farm and smart grid [1–4]. Traditional data collection approaches rely on the wireless communications between sensor nodes and the sink, excessively consuming nodes’ limited energy supply and leading to their unbalanced energy consumption. Adopting mobile agents (MAs) for data collection, that is,mobility-assisted data collection (MDC), reduces and balances the communication loads of nodes (and thus their energy consumption) [5–7]. Also, with MAs’ controllable mobility, the communications and networking become possible even in sparse networks via thestore-carry-forward approach. A real-life MDC example is the NEPTUNE project—a seabed crawler is deployed to collect sensory data from other underwater experiment nodes [8]. However, MDC leads to large data collection latency due to MAs’ limited velocity, degrading the realtimeness of the collected data, and may cause data loss due to the buffer overflow at sensor nodes.Much research effort onoffline MDC exists in the literature, where the MAsperiodically collect data from nodes with a preoptimized path [9]. On the other end of the spectrum,on-demand MDC—sensor nodes send data collection requests to the MAs when they have data to report and the MAs only visit (and collect data from) such requesting nodes—is a more efficient approach to exploit MAs’ limited mobility resource, especially for event-driven systems with diverse data generation among sensors [10, 11]. The challenge in the on-demand MDC, however, is to determine how the MAs should collect data from nodes without a priori information on future data collection demands.On-demand MDC shows clear queuing behavior. In this paper, we formulate two queuing models to capture the on-demand MDC with theFirst-Come-First-Serve (FCFS) discipline (FCFS is a simple and natural choice to maintain request fairness and is preferred in certain node-centric scenarios.), on the cases where a single MA and multiple MAs are deployed for data collection, respectively, and corresponding analytical results on the data collection performance are derived. Furthermore, we use three examples to show how the analysis guides the on-demand MDC in practice: (i) how to use multiple MAs? (ii) When to request data collection? (iii) How likely the requests combination—that is, collect data from multiple sensor nodes at the same location—would happen via the wireless communication between the MAs and nodes? The contributions of this paper include the following:(i)
Formulation of anM/G/1 queuing model to capture and analytically evaluate the on-demand MDC when a single MA is deployed for data collection (Section 4)(ii)
AnM/G/c queuing model for the case when multiple MAs are deployed, based on which the data collection performance is explored via approximation (Section 5)(iii)
Three examples to show how the analysis guides the on-demand MDC in practice (Section7)The rest of this paper is organized as follows. The literature on MDC is briefed in Section2. We formulate the problem in Section 3. The on-demand MDC with a single MA and multiple MAs is investigated in Sections 4 and 5 and evaluated in Section 6. The practical guidance is presented in Section 7, followed by further discussions in Section 8. The paper concludes in Section 9.


## 2. Related Work

Observing the advantages of MDC over traditional data collection approaches (e.g., via direct communication or multihop forwarding), much effort has been made to explore theMDC with a single MA [7, 11, 12]. For example, Sugihara and Gupta investigated the MDC with the objective of minimizing MA’s travel distance in [9]. Zhao et al. proposed a three-layer framework for the offline MDC, including the sensor layer, cluster head layer, and MA layer. The MA collects data according to a preoptimized tour with dual antennas [13]. A unified framework for analyzing the MA’s mobility and data collection latency was presented and solutions to the involved subproblems were proposed in [14]. An MA-tracking protocol was proposed in [15], in which the routing structure of data collection requests was additively updated with MA’s movement. The joint energy replenishment and data collection was investigated in [16], with the consideration of various sources of energy consumption and time-varying nature of energy replenishment. The colocation of MA and wireless charger has been investigated in [17], with the objective of ensuring sustainable and lossless system operation.Scalability is a critical bottleneck when only a single MA is used and a potential mitigation is to employ multiple MAs for data collection. An early investigation on the scenario of multiple MAs is [18], where the MAs travel along fixed tracks to collect data from nodes with the consideration of load balancing. A motion planning algorithm for the MAs was proposed in [19], which minimizes the number of MAs according to the constraints in distance and time. This work was extended for applications with strict distance/time constraints, and a data-gathering algorithm with multiple MAs was proposed in [20]. More detailed information on MDC is found in [21] and the references therein.Most of these existing efforts focus on the offline MDC, while we tackle the on-demand MDC in this paper. Although similar scenarios have been investigated in [12, 22, 23], our queue-based analytical framework provides detailed insights into the data collection process such as system size, queuing time, and response time, and these analytical insights guide the MDC in practice.


## 3. Preliminaries

### 3.1. On-Demand MDC

In many offline MDC solutions, the MAs periodically collect data from sensor nodes based on preoptimized tours [9]. These solutions perform well when nodes generate data at similar paces but degrade dramatically when the data generation at nodes varies—MAs may visit nodes with little or no data to report. Unfortunately, many event-driven systems demonstrate such diverse data generations [10]. For example, Figure 1 plots the number of packets received from 54 sensor nodes in a trace provided by Intel Berkeley Research Lab [24], showing clear diversity among nodes. Targeting on these scenarios with diverse data generations, we investigate theon-demand MDC, where the MAs collect data based on real-time demands from sensor nodes in this paper.Figure 1
Diverse data generation among sensor nodes (original data from [24]).


### 3.2. Network Model

We consider the scenario where controllable MAs collect data from stationary sensor nodes randomly deployed in a square sensing field [9] (our model formulation and analysis are also applicable to sensing fields of other shapes, as will be explained in Section 4). Sensor nodes monitor their surrounding environments, store the gathered data in their buffers, and send out data collection requests to MAs when their buffers are to be full [10]. The data collection requests can be delivered to the MAs via existing MA-tracking protocols [15]. Because the typical data relay speed is much faster than the MAs’ travel, we assume that the time since a request is sent by a sensor node till it is received by MAs is short and negligible [12]. Note that, instead of using these MA-tracking protocols to upload the sensory data directly, which are normally of much larger volume, only data collection requests are forwarded to MAs to reduce nodes’ communication loads.MAs maintain a service pool to store the received data collection requests and serve them according to theFirst-Come-First-Serve (FCFS) discipline. Byserving the request, we mean one of the MAs moves to the corresponding requesting node to collect its data via short-range wireless communications. FCFS, albeit not the optimal solution for on-demand MDC, is a classic scheduling discipline known to be fair for clients [25]. Moreover, the theoretically established data collection performance with FCFS serves as a good baseline for the evaluation of more sophisticated MDC solutions.Also, it is not necessary for the MA to travel to the exact location of nodes to collect data because of the wireless communications between the MA and the nodes [12, 26]. This way, the MA can potentially collect data from all nodes within its communication range at a single site. The impact of the communication range on MDC relies on both the field size and node density. To establish a theoretic foundation, we do not directly incorporate the communication range into our modeling; however, we investigate and evaluate its impact in Section 7.3.


### 3.3. Problem Statement

The on-demand MDC is dynamic both temporally and spatially, that is, when a data collection request will be received and where (which sensor node) the request is from. This dynamic property not only shifts our objective from MAs’ optimal path planning (as in theoffline MDC) to the design of efficient real-time service disciplines to select the next request (i.e., the requesting node) to serve (i.e., collect data from) but also makes the MDC hard to capture and thus its performance challenging to evaluate. In this paper, we evaluate the on-demand MDC via a queue-based analytical approach.


## 3.1. On-Demand MDC

In many offline MDC solutions, the MAs periodically collect data from sensor nodes based on preoptimized tours [9]. These solutions perform well when nodes generate data at similar paces but degrade dramatically when the data generation at nodes varies—MAs may visit nodes with little or no data to report. Unfortunately, many event-driven systems demonstrate such diverse data generations [10]. For example, Figure 1 plots the number of packets received from 54 sensor nodes in a trace provided by Intel Berkeley Research Lab [24], showing clear diversity among nodes. Targeting on these scenarios with diverse data generations, we investigate theon-demand MDC, where the MAs collect data based on real-time demands from sensor nodes in this paper.Figure 1
Diverse data generation among sensor nodes (original data from [24]).


## 3.2. Network Model

We consider the scenario where controllable MAs collect data from stationary sensor nodes randomly deployed in a square sensing field [9] (our model formulation and analysis are also applicable to sensing fields of other shapes, as will be explained in Section 4). Sensor nodes monitor their surrounding environments, store the gathered data in their buffers, and send out data collection requests to MAs when their buffers are to be full [10]. The data collection requests can be delivered to the MAs via existing MA-tracking protocols [15]. Because the typical data relay speed is much faster than the MAs’ travel, we assume that the time since a request is sent by a sensor node till it is received by MAs is short and negligible [12]. Note that, instead of using these MA-tracking protocols to upload the sensory data directly, which are normally of much larger volume, only data collection requests are forwarded to MAs to reduce nodes’ communication loads.MAs maintain a service pool to store the received data collection requests and serve them according to theFirst-Come-First-Serve (FCFS) discipline. Byserving the request, we mean one of the MAs moves to the corresponding requesting node to collect its data via short-range wireless communications. FCFS, albeit not the optimal solution for on-demand MDC, is a classic scheduling discipline known to be fair for clients [25]. Moreover, the theoretically established data collection performance with FCFS serves as a good baseline for the evaluation of more sophisticated MDC solutions.Also, it is not necessary for the MA to travel to the exact location of nodes to collect data because of the wireless communications between the MA and the nodes [12, 26]. This way, the MA can potentially collect data from all nodes within its communication range at a single site. The impact of the communication range on MDC relies on both the field size and node density. To establish a theoretic foundation, we do not directly incorporate the communication range into our modeling; however, we investigate and evaluate its impact in Section 7.3.


## 3.3. Problem Statement

The on-demand MDC is dynamic both temporally and spatially, that is, when a data collection request will be received and where (which sensor node) the request is from. This dynamic property not only shifts our objective from MAs’ optimal path planning (as in theoffline MDC) to the design of efficient real-time service disciplines to select the next request (i.e., the requesting node) to serve (i.e., collect data from) but also makes the MDC hard to capture and thus its performance challenging to evaluate. In this paper, we evaluate the on-demand MDC via a queue-based analytical approach.


## 4. MDC with a Single MA

We investigate the on-demand MDC in this section and the following ones. Specifically, in this section, anM/G/1 queuing model is constructed to capture the MDC when a single MA is deployed.


### 4.1. Construction of theM/G/1 Model

The on-demand MDC shows clear queuing behavior, inspiring us to capture it with a queuing model—the MA serves as the server and the data collection requests from sensors are treated as the clients (Figure2). For any queuing system, two fundamental components to be characterized are the client arrival and departure.Figure 2
Queuing model when a single MA is deployed for data collection.


#### 4.1.1. Request Arrival

The aggregated request arrival process at the MA is the superposition ofn requesting processes of individual sensors, where n is the number of sensors in the system. This way, the request arrival at the MA can be captured by a Poisson process according toPalm-Khintchine theorem [27]. This is because (i) for a stable data collection process the number of sensors in the system is large when compared with the number of to-be-served requests at any given time instance, indicating low dependency in their requesting of data collections; (ii) the probability for a sensor to initiate a data collection request at a specific time instance is small. Theoretically, if the client population of a queuing system is large and the probability by which clients arrive at the queue is low at a specific time, the arrival process can be adequately modeled as Poisson [28]. We will further statistically verify this Poisson arrival of requests in Section 6.Assume that a memory buffer of sizeB is equipped for each sensor and its asymptotic data generation rates are fi(i=1,2,…,n). The request arrival rate λ can be approximated as(1)λ≈1B∑i=1nfi.Essentially, (1) is a lower bound on the aggregated requests arrival rate because the requesting node would not request again before its data has been collected. Denoting λ∗ as the true request arrival rate, we have(2)λ∗-λ⟶0+asn⟶∞.


#### 4.1.2. Request Departure

The MA travels to the requesting node to collect the data therein. Because the data propagation speed is much faster than the MA’s travel speed, we simplify our investigation by assuming a negligible data transmission latency. This way, the departure process, or the service time of clients, can be characterized by the time from the service completion of the current request to the time when the MA moves to the next requesting node.As the previous data collection site is also the starting location when the MA serves the next request, the service time of consecutively served requests seems not to be independent. However, denoting the sequence of service times as{t1,t2,t3,…}, if we examine only at every second element of the original process, it is clear that {t1,t3,…} are independent of each other, and the distribution-ergodic property of this subprocess can be observed [29]. The same is true for subprocess {t2,t4,…}. The distribution-ergodic property still holds if we combine these two subprocesses because their asymptotic behaviors do not change after the combination. A demonstration on this distribution-ergodic property is shown in Figure 3. This means that if we identify the time distribution when the MA travels between consecutively served nodes, we can use it as the service time distribution for the queuing model over a long time period.Figure 3
Distribution-ergodic property of the service time.From existing results in geometrical probability [11], the distance distribution between two random locations in a unit square is(3)fDx=2xπ-4x+x20≤x≤12x2sin-11x-2sin-11-1x2+4x2-1-x2-21≤x≤20otherwise.Thus, with MA travel speedv, the service time distribution can be derived as(4)FSt=Pservice time<t=Ptravel distance<vt=∫0vt2xπ-4x+x2dxt≤1v∫012xπ-4x+x2dx+∫1vt2x2sin-11x-2sin-11-1x2-x2-2dx1v<t≤2v1t>2v.Its expectation, variance, and coefficient of variation are(5)ES=EDv=1vED,VS=VDv=1v2VD,CovS=VSES=VDED=CovD.After characterizing the request arrival and departure, we can model the on-demand MDC with a single MA as anM/G/1 queuing system. Note that the distance distributions between the random locations in other field shapes are also available in the literature [30, 31], which can be used in our model accordingly (e.g., by substituting (3)).


### 4.2. Analysis Based on theM/G/1 Queuing Model

With theM/G/1 queuing model, the data collection latency is equivalently the client response time in the queuing model. We next derive analytical results on the latter to shed light on the former.


#### 4.2.1. System Size Distribution

DenoteXn as the number of requests in the service pool immediately after the departure of a request at time tn; then(6)Xn+1=Xn-1+An+1Xn≥1An+1Xn=0,where An+1 is the number of new arrivals when serving the (n+1)th request. It is clear that An+1 depends only on the service time of the (n+1)th request rather than any events that occurred earlier (i.e., the system size at earlier departure points, Xn-1,Xn-2,…). Thus, the embedded discrete-time process {X1,X2,…} observed at departure times is aDiscrete-Time Markov Chain (Figure 4) with transition probabilities.(7)pij=PXn+1=j∣Xn=i.Figure 4
Transition diagram of the Markov Chain.Define the probability thati new requests are received when serving a request as(8)ki=PA=i=∫0∞PA=i∣S=t×fStdt=∫0∞e-λtλtii!fStdt.With ki, we have the following state transition matrix:(9)P=pij=k0k1k2k3⋯k0k1k2k3⋯0k0k1k2⋯00k0k1⋯000k0⋯⋮⋮⋮⋮.Denoteπ as the steady-state system size probabilities at the departure times.(10)πP=π,from which we know that(11)πi=π0ki+∑j=1i+1πjki-j+1,fori=0,1,2,….Define the following generating functions:(12)Πz=∑i=0∞πizi,z≤1Kz=∑i=0∞kizi,z≤1.Because π0=1-ρ, we have(13)Πz=1-ρ1-zKzKz-z,from which π can be derived. Note that π are not the same as the steady-state system size probabilities pn in general. However, for the M/G/1 queue, it has been proven that these two quantities are asymptotically identical [25].


#### 4.2.2. Response Time Distribution

Next we derive the response time distribution based onπ, which consists of two parts: (i) the queuing time since its arrival at the system to its service start and (ii) its service time. With FCFS, for a new request arriving at the queue with n′ existing requests, its queuing time is the sum of the service times of these n′ requests. Byconvolution theorem, we have(14)qt,n′=0n′=0stn′=1qt,n′-1∗stn′>1,where ∗ is the convolution operator. This way, the probability distribution of the queuing time can be derived as(15)Qt=∑i=0∞Pr⁡iexisting requests·Prqueuing time≤t∣iexisting requests=∑i=0∞πi∫0tqx,idx,and its density function is q(t)=∂Q(t)/∂t.Similarly, the response time distribution for a request being received by the MA with a system sizen′ is(16)rt,n′=stn′=0qt,n′∗stn′>1.Its probability distribution can be calculated as(17)Rt=∑i=0∞Priexisting requests·Prresponse time≤t∣iexisting requests=∑i=0∞πi∫0trx,idx,and r(t)=∂R(t)/∂t.


## 4.1. Construction of theM/G/1 Model

The on-demand MDC shows clear queuing behavior, inspiring us to capture it with a queuing model—the MA serves as the server and the data collection requests from sensors are treated as the clients (Figure2). For any queuing system, two fundamental components to be characterized are the client arrival and departure.Figure 2
Queuing model when a single MA is deployed for data collection.


### 4.1.1. Request Arrival

The aggregated request arrival process at the MA is the superposition ofn requesting processes of individual sensors, where n is the number of sensors in the system. This way, the request arrival at the MA can be captured by a Poisson process according toPalm-Khintchine theorem [27]. This is because (i) for a stable data collection process the number of sensors in the system is large when compared with the number of to-be-served requests at any given time instance, indicating low dependency in their requesting of data collections; (ii) the probability for a sensor to initiate a data collection request at a specific time instance is small. Theoretically, if the client population of a queuing system is large and the probability by which clients arrive at the queue is low at a specific time, the arrival process can be adequately modeled as Poisson [28]. We will further statistically verify this Poisson arrival of requests in Section 6.Assume that a memory buffer of sizeB is equipped for each sensor and its asymptotic data generation rates are fi(i=1,2,…,n). The request arrival rate λ can be approximated as(1)λ≈1B∑i=1nfi.Essentially, (1) is a lower bound on the aggregated requests arrival rate because the requesting node would not request again before its data has been collected. Denoting λ∗ as the true request arrival rate, we have(2)λ∗-λ⟶0+asn⟶∞.


### 4.1.2. Request Departure

The MA travels to the requesting node to collect the data therein. Because the data propagation speed is much faster than the MA’s travel speed, we simplify our investigation by assuming a negligible data transmission latency. This way, the departure process, or the service time of clients, can be characterized by the time from the service completion of the current request to the time when the MA moves to the next requesting node.As the previous data collection site is also the starting location when the MA serves the next request, the service time of consecutively served requests seems not to be independent. However, denoting the sequence of service times as{t1,t2,t3,…}, if we examine only at every second element of the original process, it is clear that {t1,t3,…} are independent of each other, and the distribution-ergodic property of this subprocess can be observed [29]. The same is true for subprocess {t2,t4,…}. The distribution-ergodic property still holds if we combine these two subprocesses because their asymptotic behaviors do not change after the combination. A demonstration on this distribution-ergodic property is shown in Figure 3. This means that if we identify the time distribution when the MA travels between consecutively served nodes, we can use it as the service time distribution for the queuing model over a long time period.Figure 3
Distribution-ergodic property of the service time.From existing results in geometrical probability [11], the distance distribution between two random locations in a unit square is(3)fDx=2xπ-4x+x20≤x≤12x2sin-11x-2sin-11-1x2+4x2-1-x2-21≤x≤20otherwise.Thus, with MA travel speedv, the service time distribution can be derived as(4)FSt=Pservice time<t=Ptravel distance<vt=∫0vt2xπ-4x+x2dxt≤1v∫012xπ-4x+x2dx+∫1vt2x2sin-11x-2sin-11-1x2-x2-2dx1v<t≤2v1t>2v.Its expectation, variance, and coefficient of variation are(5)ES=EDv=1vED,VS=VDv=1v2VD,CovS=VSES=VDED=CovD.After characterizing the request arrival and departure, we can model the on-demand MDC with a single MA as anM/G/1 queuing system. Note that the distance distributions between the random locations in other field shapes are also available in the literature [30, 31], which can be used in our model accordingly (e.g., by substituting (3)).


## 4.1.1. Request Arrival

The aggregated request arrival process at the MA is the superposition ofn requesting processes of individual sensors, where n is the number of sensors in the system. This way, the request arrival at the MA can be captured by a Poisson process according toPalm-Khintchine theorem [27]. This is because (i) for a stable data collection process the number of sensors in the system is large when compared with the number of to-be-served requests at any given time instance, indicating low dependency in their requesting of data collections; (ii) the probability for a sensor to initiate a data collection request at a specific time instance is small. Theoretically, if the client population of a queuing system is large and the probability by which clients arrive at the queue is low at a specific time, the arrival process can be adequately modeled as Poisson [28]. We will further statistically verify this Poisson arrival of requests in Section 6.Assume that a memory buffer of sizeB is equipped for each sensor and its asymptotic data generation rates are fi(i=1,2,…,n). The request arrival rate λ can be approximated as(1)λ≈1B∑i=1nfi.Essentially, (1) is a lower bound on the aggregated requests arrival rate because the requesting node would not request again before its data has been collected. Denoting λ∗ as the true request arrival rate, we have(2)λ∗-λ⟶0+asn⟶∞.


## 4.1.2. Request Departure

The MA travels to the requesting node to collect the data therein. Because the data propagation speed is much faster than the MA’s travel speed, we simplify our investigation by assuming a negligible data transmission latency. This way, the departure process, or the service time of clients, can be characterized by the time from the service completion of the current request to the time when the MA moves to the next requesting node.As the previous data collection site is also the starting location when the MA serves the next request, the service time of consecutively served requests seems not to be independent. However, denoting the sequence of service times as{t1,t2,t3,…}, if we examine only at every second element of the original process, it is clear that {t1,t3,…} are independent of each other, and the distribution-ergodic property of this subprocess can be observed [29]. The same is true for subprocess {t2,t4,…}. The distribution-ergodic property still holds if we combine these two subprocesses because their asymptotic behaviors do not change after the combination. A demonstration on this distribution-ergodic property is shown in Figure 3. This means that if we identify the time distribution when the MA travels between consecutively served nodes, we can use it as the service time distribution for the queuing model over a long time period.Figure 3
Distribution-ergodic property of the service time.From existing results in geometrical probability [11], the distance distribution between two random locations in a unit square is(3)fDx=2xπ-4x+x20≤x≤12x2sin-11x-2sin-11-1x2+4x2-1-x2-21≤x≤20otherwise.Thus, with MA travel speedv, the service time distribution can be derived as(4)FSt=Pservice time<t=Ptravel distance<vt=∫0vt2xπ-4x+x2dxt≤1v∫012xπ-4x+x2dx+∫1vt2x2sin-11x-2sin-11-1x2-x2-2dx1v<t≤2v1t>2v.Its expectation, variance, and coefficient of variation are(5)ES=EDv=1vED,VS=VDv=1v2VD,CovS=VSES=VDED=CovD.After characterizing the request arrival and departure, we can model the on-demand MDC with a single MA as anM/G/1 queuing system. Note that the distance distributions between the random locations in other field shapes are also available in the literature [30, 31], which can be used in our model accordingly (e.g., by substituting (3)).


## 4.2. Analysis Based on theM/G/1 Queuing Model

With theM/G/1 queuing model, the data collection latency is equivalently the client response time in the queuing model. We next derive analytical results on the latter to shed light on the former.


### 4.2.1. System Size Distribution

DenoteXn as the number of requests in the service pool immediately after the departure of a request at time tn; then(6)Xn+1=Xn-1+An+1Xn≥1An+1Xn=0,where An+1 is the number of new arrivals when serving the (n+1)th request. It is clear that An+1 depends only on the service time of the (n+1)th request rather than any events that occurred earlier (i.e., the system size at earlier departure points, Xn-1,Xn-2,…). Thus, the embedded discrete-time process {X1,X2,…} observed at departure times is aDiscrete-Time Markov Chain (Figure 4) with transition probabilities.(7)pij=PXn+1=j∣Xn=i.Figure 4
Transition diagram of the Markov Chain.Define the probability thati new requests are received when serving a request as(8)ki=PA=i=∫0∞PA=i∣S=t×fStdt=∫0∞e-λtλtii!fStdt.With ki, we have the following state transition matrix:(9)P=pij=k0k1k2k3⋯k0k1k2k3⋯0k0k1k2⋯00k0k1⋯000k0⋯⋮⋮⋮⋮.Denoteπ as the steady-state system size probabilities at the departure times.(10)πP=π,from which we know that(11)πi=π0ki+∑j=1i+1πjki-j+1,fori=0,1,2,….Define the following generating functions:(12)Πz=∑i=0∞πizi,z≤1Kz=∑i=0∞kizi,z≤1.Because π0=1-ρ, we have(13)Πz=1-ρ1-zKzKz-z,from which π can be derived. Note that π are not the same as the steady-state system size probabilities pn in general. However, for the M/G/1 queue, it has been proven that these two quantities are asymptotically identical [25].


### 4.2.2. Response Time Distribution

Next we derive the response time distribution based onπ, which consists of two parts: (i) the queuing time since its arrival at the system to its service start and (ii) its service time. With FCFS, for a new request arriving at the queue with n′ existing requests, its queuing time is the sum of the service times of these n′ requests. Byconvolution theorem, we have(14)qt,n′=0n′=0stn′=1qt,n′-1∗stn′>1,where ∗ is the convolution operator. This way, the probability distribution of the queuing time can be derived as(15)Qt=∑i=0∞Pr⁡iexisting requests·Prqueuing time≤t∣iexisting requests=∑i=0∞πi∫0tqx,idx,and its density function is q(t)=∂Q(t)/∂t.Similarly, the response time distribution for a request being received by the MA with a system sizen′ is(16)rt,n′=stn′=0qt,n′∗stn′>1.Its probability distribution can be calculated as(17)Rt=∑i=0∞Priexisting requests·Prresponse time≤t∣iexisting requests=∑i=0∞πi∫0trx,idx,and r(t)=∂R(t)/∂t.


## 4.2.1. System Size Distribution

DenoteXn as the number of requests in the service pool immediately after the departure of a request at time tn; then(6)Xn+1=Xn-1+An+1Xn≥1An+1Xn=0,where An+1 is the number of new arrivals when serving the (n+1)th request. It is clear that An+1 depends only on the service time of the (n+1)th request rather than any events that occurred earlier (i.e., the system size at earlier departure points, Xn-1,Xn-2,…). Thus, the embedded discrete-time process {X1,X2,…} observed at departure times is aDiscrete-Time Markov Chain (Figure 4) with transition probabilities.(7)pij=PXn+1=j∣Xn=i.Figure 4
Transition diagram of the Markov Chain.Define the probability thati new requests are received when serving a request as(8)ki=PA=i=∫0∞PA=i∣S=t×fStdt=∫0∞e-λtλtii!fStdt.With ki, we have the following state transition matrix:(9)P=pij=k0k1k2k3⋯k0k1k2k3⋯0k0k1k2⋯00k0k1⋯000k0⋯⋮⋮⋮⋮.Denoteπ as the steady-state system size probabilities at the departure times.(10)πP=π,from which we know that(11)πi=π0ki+∑j=1i+1πjki-j+1,fori=0,1,2,….Define the following generating functions:(12)Πz=∑i=0∞πizi,z≤1Kz=∑i=0∞kizi,z≤1.Because π0=1-ρ, we have(13)Πz=1-ρ1-zKzKz-z,from which π can be derived. Note that π are not the same as the steady-state system size probabilities pn in general. However, for the M/G/1 queue, it has been proven that these two quantities are asymptotically identical [25].


## 4.2.2. Response Time Distribution

Next we derive the response time distribution based onπ, which consists of two parts: (i) the queuing time since its arrival at the system to its service start and (ii) its service time. With FCFS, for a new request arriving at the queue with n′ existing requests, its queuing time is the sum of the service times of these n′ requests. Byconvolution theorem, we have(14)qt,n′=0n′=0stn′=1qt,n′-1∗stn′>1,where ∗ is the convolution operator. This way, the probability distribution of the queuing time can be derived as(15)Qt=∑i=0∞Pr⁡iexisting requests·Prqueuing time≤t∣iexisting requests=∑i=0∞πi∫0tqx,idx,and its density function is q(t)=∂Q(t)/∂t.Similarly, the response time distribution for a request being received by the MA with a system sizen′ is(16)rt,n′=stn′=0qt,n′∗stn′>1.Its probability distribution can be calculated as(17)Rt=∑i=0∞Priexisting requests·Prresponse time≤t∣iexisting requests=∑i=0∞πi∫0trx,idx,and r(t)=∂R(t)/∂t.


## 5. MDC with Multiple MAs

Scalability is a critical bottleneck when only a single MA is deployed for data collection, especially with a large sensing field or with a high node density. Employing multiple MAs to collect data collaboratively is a straightforward mitigation, which we investigate next. Specifically, we consider the scenario where each MA has the full knowledge on the received data collection requests, which can be achieved by the communications among the MAs and the sink, for example, via satellite or cellular communications. Whenever an MA accomplishes its current data collection task, it selects the next-to-be-served request with FCFS.


### 5.1. Construction of theM/G/c Model

Our approach is to extend the previously constructedM/G/1 queuing model to M/G/c, where c is the number of MAs (Figure 5). The employment of multiple MAs does not affect sensors’ data generation, and thus the request arrival process is the same as in the single MA case. For the request departure, the service time for individual data collection requests is still the same as that with a single MA (i.e., as in (4)), but the aggregated system departure rate will be c/E[S].Figure 5
Queuing model when multiple MAs are deployed for data collection.


### 5.2. Analysis Based on theM/G/c Queuing Model

Although extending the queuing model to the multiple MAs case is straightforward, evaluating anM/G/c queue is analytically intractable. Even when closed-form solutions can be obtained, often they are complicated and require particular probability distributions [32, 33]. Thus, instead of pursuing the exact analytical results on system measures, we use an approximation approach. The basic idea is to combine the analytical results on simple queuing systems such as M/M/c and M/D/c to approximate the measures of the M/G/c queue [34].


#### 5.2.1. Expected Response Time

We first explore the expected data collection latency or, equivalently, the expected response time of theM/G/c queue. A simple two-moment approximation formula with verified accuracy for the mean queuing time in an M/G/c queue can be derived from [35](18)⁡EQM/G/c≈1+γ2γ/EQM/M/c+1-γ/EQM/D/c,where γ=Cov[S]2.The above approximation is essentially a weighted combination ofE[QM/M/c] and E[QM/D/c]. The former can be calculated by(19)EQM/M/c=cρcc!cμ1-ρ2·∑i=0c-1cρii!+cρcc!1-ρ-1,and the latter can be obtained byCrommelin’s formula [36].(20)EQM/D/c=1μ∑i=1∞∑j=ic+1∞icρj-1j-1!-icρjρj!e-icρ.However, the series in (20) converges slowly especially with high traffic intensity [37]. Again, approximations are adopted to speed up its convergence. An approximation on E[QM/D/c] with simple computation complexity and promising accuracy is presented in [34].(21)EQM/D/c≈1+hθgρ1-e-θ/hθgρ·EQM/M/c,where(22)θ=1-2c+1,c≥1,hθ=θ9+θ1-θ1/2-281+θ,gρ=1ρ-1.Substituting (19) and (21) into (18), we can calculate E[QM/G/c], with which the requests’ expected response time in the M/G/c queue can be derived as(23)ERM/G/c=EQM/G/c+ES.The expected response time is crucial because it not only offers us insights into the asymptotic data collection latency but also helps to obtain the measures on the size of theM/G/c queue, based on which more insights into the MDC can be obtained. Again, denote X as the number of requests either waiting or being served at arbitrary time in the M/G/c queue. Let Pi=P{X=i}(i≥0), and define(24)α=EQM/G/cEQM/M/c.A geometric-form approximation for the system size probability is proposed in [38].(25)Pi,M/G/c=cρii!P0,M/M/ci=0,…,c-11-ζζi-cUM/M/ci≥c,where(26)ζ=ρα1-ρ+ρα,P0,M/M/c=∑i=0c-1cρci!+cρcc!1-ρ-1,UM/M/c=cρccP0,M/M/cc!1-ρcis the probability that a newly arriving request has to wait before being served in an M/M/c queue. Note that ζ<1 if ρ<1 and ζ=ρ if the service time is exponentially distributed.We calculate the expected system size based on its approximated distribution as(27)EL=∑i=0∞i·Pi,M/G/c,and the probability that a newly arrived request has to wait before being served, that is, the equivalent of UM/M/c in M/G/c queue, can be calculated as(28)UM/G/c=1-∑i=0c-1Pi,M/G/c.Bydistributional Little’s law [39], the number of customers in the queue has the same distribution as the number of arrivals during the waiting time. Based on this and the above approximation results on the system size distribution, an approximation for the queuing time distribution in the M/G/c queue is proposed in [40].(29)QM/G/ct≈1-e-cμ1-ρt/αUM/M/c,qM/G/ct=∂QM/G/ct∂t.Furthermore, because the response time of a request is the sum of its queuing time and service time, which are independent of each other, byconvolution theorem, we have(30)rM/G/ct=qM/G/ct∗st.⁡


## 5.1. Construction of theM/G/c Model

Our approach is to extend the previously constructedM/G/1 queuing model to M/G/c, where c is the number of MAs (Figure 5). The employment of multiple MAs does not affect sensors’ data generation, and thus the request arrival process is the same as in the single MA case. For the request departure, the service time for individual data collection requests is still the same as that with a single MA (i.e., as in (4)), but the aggregated system departure rate will be c/E[S].Figure 5
Queuing model when multiple MAs are deployed for data collection.


## 5.2. Analysis Based on theM/G/c Queuing Model

Although extending the queuing model to the multiple MAs case is straightforward, evaluating anM/G/c queue is analytically intractable. Even when closed-form solutions can be obtained, often they are complicated and require particular probability distributions [32, 33]. Thus, instead of pursuing the exact analytical results on system measures, we use an approximation approach. The basic idea is to combine the analytical results on simple queuing systems such as M/M/c and M/D/c to approximate the measures of the M/G/c queue [34].


### 5.2.1. Expected Response Time

We first explore the expected data collection latency or, equivalently, the expected response time of theM/G/c queue. A simple two-moment approximation formula with verified accuracy for the mean queuing time in an M/G/c queue can be derived from [35](18)⁡EQM/G/c≈1+γ2γ/EQM/M/c+1-γ/EQM/D/c,where γ=Cov[S]2.The above approximation is essentially a weighted combination ofE[QM/M/c] and E[QM/D/c]. The former can be calculated by(19)EQM/M/c=cρcc!cμ1-ρ2·∑i=0c-1cρii!+cρcc!1-ρ-1,and the latter can be obtained byCrommelin’s formula [36].(20)EQM/D/c=1μ∑i=1∞∑j=ic+1∞icρj-1j-1!-icρjρj!e-icρ.However, the series in (20) converges slowly especially with high traffic intensity [37]. Again, approximations are adopted to speed up its convergence. An approximation on E[QM/D/c] with simple computation complexity and promising accuracy is presented in [34].(21)EQM/D/c≈1+hθgρ1-e-θ/hθgρ·EQM/M/c,where(22)θ=1-2c+1,c≥1,hθ=θ9+θ1-θ1/2-281+θ,gρ=1ρ-1.Substituting (19) and (21) into (18), we can calculate E[QM/G/c], with which the requests’ expected response time in the M/G/c queue can be derived as(23)ERM/G/c=EQM/G/c+ES.The expected response time is crucial because it not only offers us insights into the asymptotic data collection latency but also helps to obtain the measures on the size of theM/G/c queue, based on which more insights into the MDC can be obtained. Again, denote X as the number of requests either waiting or being served at arbitrary time in the M/G/c queue. Let Pi=P{X=i}(i≥0), and define(24)α=EQM/G/cEQM/M/c.A geometric-form approximation for the system size probability is proposed in [38].(25)Pi,M/G/c=cρii!P0,M/M/ci=0,…,c-11-ζζi-cUM/M/ci≥c,where(26)ζ=ρα1-ρ+ρα,P0,M/M/c=∑i=0c-1cρci!+cρcc!1-ρ-1,UM/M/c=cρccP0,M/M/cc!1-ρcis the probability that a newly arriving request has to wait before being served in an M/M/c queue. Note that ζ<1 if ρ<1 and ζ=ρ if the service time is exponentially distributed.We calculate the expected system size based on its approximated distribution as(27)EL=∑i=0∞i·Pi,M/G/c,and the probability that a newly arrived request has to wait before being served, that is, the equivalent of UM/M/c in M/G/c queue, can be calculated as(28)UM/G/c=1-∑i=0c-1Pi,M/G/c.Bydistributional Little’s law [39], the number of customers in the queue has the same distribution as the number of arrivals during the waiting time. Based on this and the above approximation results on the system size distribution, an approximation for the queuing time distribution in the M/G/c queue is proposed in [40].(29)QM/G/ct≈1-e-cμ1-ρt/αUM/M/c,qM/G/ct=∂QM/G/ct∂t.Furthermore, because the response time of a request is the sum of its queuing time and service time, which are independent of each other, byconvolution theorem, we have(30)rM/G/ct=qM/G/ct∗st.⁡


## 5.2.1. Expected Response Time

We first explore the expected data collection latency or, equivalently, the expected response time of theM/G/c queue. A simple two-moment approximation formula with verified accuracy for the mean queuing time in an M/G/c queue can be derived from [35](18)⁡EQM/G/c≈1+γ2γ/EQM/M/c+1-γ/EQM/D/c,where γ=Cov[S]2.The above approximation is essentially a weighted combination ofE[QM/M/c] and E[QM/D/c]. The former can be calculated by(19)EQM/M/c=cρcc!cμ1-ρ2·∑i=0c-1cρii!+cρcc!1-ρ-1,and the latter can be obtained byCrommelin’s formula [36].(20)EQM/D/c=1μ∑i=1∞∑j=ic+1∞icρj-1j-1!-icρjρj!e-icρ.However, the series in (20) converges slowly especially with high traffic intensity [37]. Again, approximations are adopted to speed up its convergence. An approximation on E[QM/D/c] with simple computation complexity and promising accuracy is presented in [34].(21)EQM/D/c≈1+hθgρ1-e-θ/hθgρ·EQM/M/c,where(22)θ=1-2c+1,c≥1,hθ=θ9+θ1-θ1/2-281+θ,gρ=1ρ-1.Substituting (19) and (21) into (18), we can calculate E[QM/G/c], with which the requests’ expected response time in the M/G/c queue can be derived as(23)ERM/G/c=EQM/G/c+ES.The expected response time is crucial because it not only offers us insights into the asymptotic data collection latency but also helps to obtain the measures on the size of theM/G/c queue, based on which more insights into the MDC can be obtained. Again, denote X as the number of requests either waiting or being served at arbitrary time in the M/G/c queue. Let Pi=P{X=i}(i≥0), and define(24)α=EQM/G/cEQM/M/c.A geometric-form approximation for the system size probability is proposed in [38].(25)Pi,M/G/c=cρii!P0,M/M/ci=0,…,c-11-ζζi-cUM/M/ci≥c,where(26)ζ=ρα1-ρ+ρα,P0,M/M/c=∑i=0c-1cρci!+cρcc!1-ρ-1,UM/M/c=cρccP0,M/M/cc!1-ρcis the probability that a newly arriving request has to wait before being served in an M/M/c queue. Note that ζ<1 if ρ<1 and ζ=ρ if the service time is exponentially distributed.We calculate the expected system size based on its approximated distribution as(27)EL=∑i=0∞i·Pi,M/G/c,and the probability that a newly arrived request has to wait before being served, that is, the equivalent of UM/M/c in M/G/c queue, can be calculated as(28)UM/G/c=1-∑i=0c-1Pi,M/G/c.Bydistributional Little’s law [39], the number of customers in the queue has the same distribution as the number of arrivals during the waiting time. Based on this and the above approximation results on the system size distribution, an approximation for the queuing time distribution in the M/G/c queue is proposed in [40].(29)QM/G/ct≈1-e-cμ1-ρt/αUM/M/c,qM/G/ct=∂QM/G/ct∂t.Furthermore, because the response time of a request is the sum of its queuing time and service time, which are independent of each other, byconvolution theorem, we have(30)rM/G/ct=qM/G/ct∗st.⁡


## 6. Performance Evaluations

We verify the model soundness and the analysis accuracy in this section. We consider a system deployed in a square field of size100×100m2. A total number of 100 sensors are randomly deployed unless otherwise specified. The MA velocity is set to 1 m/s based on Power Bot [41]. The simulation is implemented with Matlab. A total number of 10,000 requests are generated and served during each run of the simulation, which is repeated for 50 times.To deal with the inconvenience of the piecewise distance probability density function in (3), we approximate it by a 10-order polynomial with least squares fitting.(31)f~d=0.2802d10-2.0964d9+2.2349d8+24.3629d7-106.8231d6+194.4928d5-182.8093d4+91.8223d3-29.3663d2+8.2843d-0.0402.


### 6.1. Verifying the Queuing Models

To verify the soundness of the queue-based modeling, we examine the request arrival with an event-driven simulator, where stochastic events occur randomly in the sensing field (note that when events happen in a clustered manner, this actually improves the MDC performance as the MAs’ travel distance is reduced. This way, our models capture the worst cases of on-demand MDC, which are important to provide performance guarantees). Sensors within a certain distance (i.e., the sensing range) can detect the event, and corresponding sensory data are generated. The data size for recording each event varies from 10 to 100 B. Events happen independently in both the spatial and temporal domains, and sensor nodes initiate the data collection requests when their buffers become full. We explore the cases where the sensor node buffer size is 4 KB and 8 KB, respectively, and record the interarrival time of data collection requests for comparison with an exponential distribution with the same mean value (the Poisson arrival process indicates an exponentially distributed request interarrival time). Figure6 indicates that the simulation results match the exponential distribution well, verifying the assumption on Poisson arrival. Furthermore, a larger node buffer results in a smaller request arrival rate, because the sensor nodes can hold the on-board data longer.Figure 6
Verify the request arrival.We further statistically verify the queuing models by validating the Poisson arrival of requests, the independence of request arrivals, and the service time independence. Kolmogorov-Smirnov (K-S) test with a significance level of5% is used to verify the Poisson arrival. We perform the tests with a different number of sensor nodes (20–100), each with 50 trials. We record the number of trials that reject the Poisson arrival hypothesis. The verification results are listed in the first row of Table 1. The low rejection ratio indicates that the Poisson arrival in our modeling is sound. To evaluate the independence of the request arrival and service time, we record the request interarrival time and service time and calculate their 1-lag autocorrelations. Again, the simulation is repeated for 50 times with 20 to 100 sensor nodes, respectively, and the average absolute values of the autocorrelations are shown in the second and third rows of Table 1. The small correlations of both the request arrival and their service time support our queue-based modeling.Table 1
Verify the queuing model (with50 trials).
# of nodes 20 40 60 80 100 # of rejections 0 1 1 3 3 Arrival corr. 0.0463 0.0371 0.0236 0.0183 0.0167 Service corr. 0.0942 0.1023 0.0985 0.0967 0.1000


### 6.2. Single MA

Next, we evaluate our analytical results on the single MA case. Service time distribution is the core component in the queue-based analysis, which is obtained based on results from geometrical probability. We evaluate our analysis on the service time distribution with an MA velocity of1m/s and 2 m/s, respectively, and the results are shown in Figure 7. We can see that the analytical results and the simulation match greatly. The service time is significantly reduced after increasing the MA velocity from 1m/s to 2m/s, agreeing with (4).Figure 7
Service time distribution.The response time distributions with request arrival rates of0.012 and 0.018 are shown in Figure 8. Besides the accuracy of the analysis, we can see that the response time of requests, or the data collection latency in our focus, is significantly increased when increasing the request arrival rate. This verifies the potential scalability issue when only one MA is used for data collection.Figure 8
Response time distribution.


### 6.3. Multiple MAs

We evaluate our modeling and analysis results on the multiple MAs case in the following. We explore the cases withc=2 and c=3, respectively, and also present the results with c=1 for comparison.The approximation results on the expected queuing time are verified in Figure9. The effect of deploying more MAs is obvious, especially when the request arrival rate is high. Note that no results for c=1 or c=2 are shown when λ is larger than 0.018 or 0.036, because the further increase of λ will result in a ρ greater than 1, and no steady-state measures can be obtained.Figure 9
The average queuing time.Figure10 shows the evaluation results of the approximation on the system size distribution with λ of 0.018. Besides the accuracy of the approximation, we can see that increasing c from 1 to 2 can greatly shorten the system size, which in turn reduces the data collection latency. However, the benefit of increasing c further from 2 to 3 is quite limited. This is because the system utilization factor is already small when c=2, and thus further increasing c cannot significantly improve the data collection performance anymore.Figure 10
The system size distribution.The results on the probability for requests to wait before being served are shown in Figure11. Intuitively, the wait probability increases when the system becomes more heavily occupied, which results when (1) fewer MAs are adopted (c decreases) and (2) the data intensity in the network is higher (λ increases). The verification of this reasoning can be clearly observed from Figure 11.Figure 11
Waiting probability.The queuing time and response time distributions withλ of 0.018 are shown in Figures 12 and 13, respectively. Besides the analysis accuracy, again we observe that further increasing c from 2 to 3 when λ=0.018 cannot significantly reduce the queuing time (response time), agreeing with Figure 10.Figure 12
Queuing time distribution.Figure 13
Response time distribution.


## 6.1. Verifying the Queuing Models

To verify the soundness of the queue-based modeling, we examine the request arrival with an event-driven simulator, where stochastic events occur randomly in the sensing field (note that when events happen in a clustered manner, this actually improves the MDC performance as the MAs’ travel distance is reduced. This way, our models capture the worst cases of on-demand MDC, which are important to provide performance guarantees). Sensors within a certain distance (i.e., the sensing range) can detect the event, and corresponding sensory data are generated. The data size for recording each event varies from 10 to 100 B. Events happen independently in both the spatial and temporal domains, and sensor nodes initiate the data collection requests when their buffers become full. We explore the cases where the sensor node buffer size is 4 KB and 8 KB, respectively, and record the interarrival time of data collection requests for comparison with an exponential distribution with the same mean value (the Poisson arrival process indicates an exponentially distributed request interarrival time). Figure6 indicates that the simulation results match the exponential distribution well, verifying the assumption on Poisson arrival. Furthermore, a larger node buffer results in a smaller request arrival rate, because the sensor nodes can hold the on-board data longer.Figure 6
Verify the request arrival.We further statistically verify the queuing models by validating the Poisson arrival of requests, the independence of request arrivals, and the service time independence. Kolmogorov-Smirnov (K-S) test with a significance level of5% is used to verify the Poisson arrival. We perform the tests with a different number of sensor nodes (20–100), each with 50 trials. We record the number of trials that reject the Poisson arrival hypothesis. The verification results are listed in the first row of Table 1. The low rejection ratio indicates that the Poisson arrival in our modeling is sound. To evaluate the independence of the request arrival and service time, we record the request interarrival time and service time and calculate their 1-lag autocorrelations. Again, the simulation is repeated for 50 times with 20 to 100 sensor nodes, respectively, and the average absolute values of the autocorrelations are shown in the second and third rows of Table 1. The small correlations of both the request arrival and their service time support our queue-based modeling.Table 1
Verify the queuing model (with50 trials).
# of nodes 20 40 60 80 100 # of rejections 0 1 1 3 3 Arrival corr. 0.0463 0.0371 0.0236 0.0183 0.0167 Service corr. 0.0942 0.1023 0.0985 0.0967 0.1000


## 6.2. Single MA

Next, we evaluate our analytical results on the single MA case. Service time distribution is the core component in the queue-based analysis, which is obtained based on results from geometrical probability. We evaluate our analysis on the service time distribution with an MA velocity of1m/s and 2 m/s, respectively, and the results are shown in Figure 7. We can see that the analytical results and the simulation match greatly. The service time is significantly reduced after increasing the MA velocity from 1m/s to 2m/s, agreeing with (4).Figure 7
Service time distribution.The response time distributions with request arrival rates of0.012 and 0.018 are shown in Figure 8. Besides the accuracy of the analysis, we can see that the response time of requests, or the data collection latency in our focus, is significantly increased when increasing the request arrival rate. This verifies the potential scalability issue when only one MA is used for data collection.Figure 8
Response time distribution.


## 6.3. Multiple MAs

We evaluate our modeling and analysis results on the multiple MAs case in the following. We explore the cases withc=2 and c=3, respectively, and also present the results with c=1 for comparison.The approximation results on the expected queuing time are verified in Figure9. The effect of deploying more MAs is obvious, especially when the request arrival rate is high. Note that no results for c=1 or c=2 are shown when λ is larger than 0.018 or 0.036, because the further increase of λ will result in a ρ greater than 1, and no steady-state measures can be obtained.Figure 9
The average queuing time.Figure10 shows the evaluation results of the approximation on the system size distribution with λ of 0.018. Besides the accuracy of the approximation, we can see that increasing c from 1 to 2 can greatly shorten the system size, which in turn reduces the data collection latency. However, the benefit of increasing c further from 2 to 3 is quite limited. This is because the system utilization factor is already small when c=2, and thus further increasing c cannot significantly improve the data collection performance anymore.Figure 10
The system size distribution.The results on the probability for requests to wait before being served are shown in Figure11. Intuitively, the wait probability increases when the system becomes more heavily occupied, which results when (1) fewer MAs are adopted (c decreases) and (2) the data intensity in the network is higher (λ increases). The verification of this reasoning can be clearly observed from Figure 11.Figure 11
Waiting probability.The queuing time and response time distributions withλ of 0.018 are shown in Figures 12 and 13, respectively. Besides the analysis accuracy, again we observe that further increasing c from 2 to 3 when λ=0.018 cannot significantly reduce the queuing time (response time), agreeing with Figure 10.Figure 12
Queuing time distribution.Figure 13
Response time distribution.


## 7. Practical Guidance

The constructed queuing models not only reveal insights into the on-demand MDC but also guide its practical implementation. We use three examples to show how these models can assist the system implementation in this section.


### 7.1. How to Adopt Multiple MAs?

In the first example, we explore the problem of how to employ multiple MAs for collaborative data collection. In general, two strategies can be used—the MAs can collaboratively collect data from the entire system, referred to as Strategy-I, or the system can be divided into subareas, and each MA is responsible to collect data from one subarea, which is referred to as Strategy-II. These two strategies can be captured by multiserver systems with shared (i.e., all MAs share the knowledge of data collection requests as with Strategy-I) and separate (i.e., each MA is only responsible for a subset of requests that fall in its service queue as with Strategy-II) queues, respectively.Conventional wisdom says that, all things being equal, a shared queue outperforms separate queues most times [25]. To the best of our knowledge, however, no results on the comparison of the two strategies have been reported yet. Here, we close this gap based on the constructed M/G/1 and M/G/c queuing models. Our results reveal that Strategy-II outperforms Strategy-I in both MAs’ workloads and requests’ response time, contradicting with the conventional wisdom.Let us consider the case wherec MAs are deployed in an L×L sensing field. For the ease of description, we assume that c=i2(i=1,2,…), which can be relaxed as will be explained later. When Strategy-I is adopted, the data collection performance can be evaluated based on the results in Section 5. Specifically, the utilization factor of individual MAs is(32)ρ1=λcESand the expected data collection latency and its distribution can be obtained according to (23) and (30), respectively.When Strategy-II is adopted, that is, the field is divided intoc subareas of size L/c×L/c each, the data collection performance can be evaluated based on the results in Section 4 but in a smaller sensing field. Denoting the requests arrival rate at individual MA and the service time in this case as λ′ and S′, the utilization factor of individual MAs is(33)ρ2=λ′ES′.With randomly distributed sensor nodes, it is clear that(34)λ′=λc,ES′=ESc.Thus, from (32) and (33), we have(35)ρ1ρ2=ESES′=c>1.This indicates that Strategy-II achieves a lower workload for the MAs with reduced MA travel distance, which dominates the service time in MDC.Because the comparison on the response time achieved with the two strategies is not so obvious, numerical comparison is performed with a network scale of 100 sensor nodes andc=4. The results are shown in Figure 14, where the aggregated request arrival rate at the MAs varies from 0.02 to 0.05. Again, Strategy-II reduces the response time by 50% when compared with Strategy-I, due to the fact that the service time is dominated by the MAs’ travel time.Figure 14
Average response time obtained with the two strategies.Although we simplify the above description by assuming thatc=i2(i=1,2,…), the conclusion on the advantage of Strategy-II holds in more general cases. However, dividing the field into c identical subareas of square shape may not be always feasible, in which cases the distance distributions between random locations in other field shapes can be used [42].


### 7.2. When to Request Data Collection?

The time for sensors to request data collection plays a critical role in the on-demand MDC. Sending the request too early unnecessarily increases the workload of the MAs, which also increases the data collection latency of other requests. On the other hand, a belated request leaves little time for the MAs to complete the data collection before the buffer of the requesting node overflows.The response time distribution, derived based on the constructed queuing models, helps identify the proper time instant to send out the data collection requests. With a memory bufferB for each sensor node and its respective data generation rate fi, denote θ  (0≤θ≤1) as the remaining memory buffer ratio when node sends the data collection request. This way, the aggregated request arrival rate is(36)λ≈11-θB∑i=1nfi.Buffer overflow would occur if the response time is larger than θB/fi. With the derived response time distribution (i.e., (17) and (30)), the probability for buffer overflow to occur can be calculated with given θ, which in turn allows us to identify the smallest θ (and thus the smallest workloads on MAs) that guarantees a small enough buffer overflow probability (e.g., poverflow<0.01), as illustrated in Algorithm 1.Algorithm 1:Find the optimal remaining buffer ratio θ.
( 1 )   θ = 0,  Δ=0.01; ( 2 ) while p o v e r f l o w > 0.01 and θ<1do ( 3 )  θ=θ+Δ;λ11-θB∑i=1nfi ( 4 )  calculate R(t) with λ; ( 5 )  poverflow=1-∫0θB/fi‍r(t)dt; ( 6 ) end while


### 7.3. Requests Combination and Preemption

The MAs can potentially collect data from multiple sensor nodes at the same location because of the wireless communication capabilities of both the MAs and sensor nodes, which corresponds to the scenario of batch service in queuing theory and is referred to asrequests combination here.Clearly, the probability for requests combination to occur is jointly determined by (i) the communication rangeR between the MAs and sensors (normalized to the field size) and (ii) the number of requests in the service pool when the new request arrives, that is, the queue length. Specifically, for a new request arriving when L requests are in the queue, it can be combined with at least one of these existing requests with probability(37)PcombineR,L=1-1-∫0RfDxdxL,where fD(x) is the distance distribution between two random locations as in (3). This indicates that the effect of requests combination on improving the on-demand MDC will be profound when the communication range is large or when the service queue is long.Figure15 shows the effect of requests combination with varying communication ranges. As expected, a larger communication range has a greater effect in reducing the data collection latency, when compared with the noncombination cases. Also, the advantage of requests combination is less significant when the number of MAs increases. This is because the service pool size is reduced when more MAs are adopted for the data collection tasks, and thus the probability for combination to happen is reduced as well.Figure 15
Effect of requests combination with communication range.Requests preemption is another potential way to improve the on-demand MDC—a new request arrival may preempt the service of existing requests if its requesting node is close to the current locations of the MAs. We have analytically explored the possibility and advantage of requests preemption in another work [43].


## 7.1. How to Adopt Multiple MAs?

In the first example, we explore the problem of how to employ multiple MAs for collaborative data collection. In general, two strategies can be used—the MAs can collaboratively collect data from the entire system, referred to as Strategy-I, or the system can be divided into subareas, and each MA is responsible to collect data from one subarea, which is referred to as Strategy-II. These two strategies can be captured by multiserver systems with shared (i.e., all MAs share the knowledge of data collection requests as with Strategy-I) and separate (i.e., each MA is only responsible for a subset of requests that fall in its service queue as with Strategy-II) queues, respectively.Conventional wisdom says that, all things being equal, a shared queue outperforms separate queues most times [25]. To the best of our knowledge, however, no results on the comparison of the two strategies have been reported yet. Here, we close this gap based on the constructed M/G/1 and M/G/c queuing models. Our results reveal that Strategy-II outperforms Strategy-I in both MAs’ workloads and requests’ response time, contradicting with the conventional wisdom.Let us consider the case wherec MAs are deployed in an L×L sensing field. For the ease of description, we assume that c=i2(i=1,2,…), which can be relaxed as will be explained later. When Strategy-I is adopted, the data collection performance can be evaluated based on the results in Section 5. Specifically, the utilization factor of individual MAs is(32)ρ1=λcESand the expected data collection latency and its distribution can be obtained according to (23) and (30), respectively.When Strategy-II is adopted, that is, the field is divided intoc subareas of size L/c×L/c each, the data collection performance can be evaluated based on the results in Section 4 but in a smaller sensing field. Denoting the requests arrival rate at individual MA and the service time in this case as λ′ and S′, the utilization factor of individual MAs is(33)ρ2=λ′ES′.With randomly distributed sensor nodes, it is clear that(34)λ′=λc,ES′=ESc.Thus, from (32) and (33), we have(35)ρ1ρ2=ESES′=c>1.This indicates that Strategy-II achieves a lower workload for the MAs with reduced MA travel distance, which dominates the service time in MDC.Because the comparison on the response time achieved with the two strategies is not so obvious, numerical comparison is performed with a network scale of 100 sensor nodes andc=4. The results are shown in Figure 14, where the aggregated request arrival rate at the MAs varies from 0.02 to 0.05. Again, Strategy-II reduces the response time by 50% when compared with Strategy-I, due to the fact that the service time is dominated by the MAs’ travel time.Figure 14
Average response time obtained with the two strategies.Although we simplify the above description by assuming thatc=i2(i=1,2,…), the conclusion on the advantage of Strategy-II holds in more general cases. However, dividing the field into c identical subareas of square shape may not be always feasible, in which cases the distance distributions between random locations in other field shapes can be used [42].


## 7.2. When to Request Data Collection?

The time for sensors to request data collection plays a critical role in the on-demand MDC. Sending the request too early unnecessarily increases the workload of the MAs, which also increases the data collection latency of other requests. On the other hand, a belated request leaves little time for the MAs to complete the data collection before the buffer of the requesting node overflows.The response time distribution, derived based on the constructed queuing models, helps identify the proper time instant to send out the data collection requests. With a memory bufferB for each sensor node and its respective data generation rate fi, denote θ  (0≤θ≤1) as the remaining memory buffer ratio when node sends the data collection request. This way, the aggregated request arrival rate is(36)λ≈11-θB∑i=1nfi.Buffer overflow would occur if the response time is larger than θB/fi. With the derived response time distribution (i.e., (17) and (30)), the probability for buffer overflow to occur can be calculated with given θ, which in turn allows us to identify the smallest θ (and thus the smallest workloads on MAs) that guarantees a small enough buffer overflow probability (e.g., poverflow<0.01), as illustrated in Algorithm 1.Algorithm 1:Find the optimal remaining buffer ratio θ.
( 1 )   θ = 0,  Δ=0.01; ( 2 ) while p o v e r f l o w > 0.01 and θ<1do ( 3 )  θ=θ+Δ;λ11-θB∑i=1nfi ( 4 )  calculate R(t) with λ; ( 5 )  poverflow=1-∫0θB/fi‍r(t)dt; ( 6 ) end while


## 7.3. Requests Combination and Preemption

The MAs can potentially collect data from multiple sensor nodes at the same location because of the wireless communication capabilities of both the MAs and sensor nodes, which corresponds to the scenario of batch service in queuing theory and is referred to asrequests combination here.Clearly, the probability for requests combination to occur is jointly determined by (i) the communication rangeR between the MAs and sensors (normalized to the field size) and (ii) the number of requests in the service pool when the new request arrives, that is, the queue length. Specifically, for a new request arriving when L requests are in the queue, it can be combined with at least one of these existing requests with probability(37)PcombineR,L=1-1-∫0RfDxdxL,where fD(x) is the distance distribution between two random locations as in (3). This indicates that the effect of requests combination on improving the on-demand MDC will be profound when the communication range is large or when the service queue is long.Figure15 shows the effect of requests combination with varying communication ranges. As expected, a larger communication range has a greater effect in reducing the data collection latency, when compared with the noncombination cases. Also, the advantage of requests combination is less significant when the number of MAs increases. This is because the service pool size is reduced when more MAs are adopted for the data collection tasks, and thus the probability for combination to happen is reduced as well.Figure 15
Effect of requests combination with communication range.Requests preemption is another potential way to improve the on-demand MDC—a new request arrival may preempt the service of existing requests if its requesting node is close to the current locations of the MAs. We have analytically explored the possibility and advantage of requests preemption in another work [43].


## 8. Further Discussions

### 8.1. System Stability Condition

A necessary and sufficient condition for the data collection process to be stable isρ/c<1 [12, 22]. This way, from (1), we know that(38)ρc=λESc<EDvcB∑i=1nfi<1,which implies that the minimum requirement on the travel speed of the MAs is (39)v>EDcB∑i=1nfi.From (39), we can see that, to provide a stable data collection performance, there is a clear trade-off between the number of required MAs and their capabilities such as travel speed v and memory size B, assisting us in determining the number of needed MAs in practice.


### 8.2. Insights for Sophisticated Discipline Design

We establish a theoretical foundation on the on-demand MDC when FCFS is adopted, which reveals insights into the design of more sophisticated service disciplines. Through the queue-based analysis, it is clear that the MAs’ travel distance between two consecutively served requests is the dominant factor that determines the data collection latency, which should be minimized to achieve a better performance. Inspired by this, in our recent work [11], we have extended these queuing models to investigate the MDC with a greedy service discipline that minimizes the travel distance between two consecutively served requests, and significant asymptotic improvement can be observed. However, the greedy discipline may cause some unfairness among sensor nodes, which has to be addressed to guarantee the worst-case performance for every node. Also note that Petri nets could be another analytical tool to capture such data collection process [44], which we will explore more in the future.


## 8.1. System Stability Condition

A necessary and sufficient condition for the data collection process to be stable isρ/c<1 [12, 22]. This way, from (1), we know that(38)ρc=λESc<EDvcB∑i=1nfi<1,which implies that the minimum requirement on the travel speed of the MAs is (39)v>EDcB∑i=1nfi.From (39), we can see that, to provide a stable data collection performance, there is a clear trade-off between the number of required MAs and their capabilities such as travel speed v and memory size B, assisting us in determining the number of needed MAs in practice.


## 8.2. Insights for Sophisticated Discipline Design

We establish a theoretical foundation on the on-demand MDC when FCFS is adopted, which reveals insights into the design of more sophisticated service disciplines. Through the queue-based analysis, it is clear that the MAs’ travel distance between two consecutively served requests is the dominant factor that determines the data collection latency, which should be minimized to achieve a better performance. Inspired by this, in our recent work [11], we have extended these queuing models to investigate the MDC with a greedy service discipline that minimizes the travel distance between two consecutively served requests, and significant asymptotic improvement can be observed. However, the greedy discipline may cause some unfairness among sensor nodes, which has to be addressed to guarantee the worst-case performance for every node. Also note that Petri nets could be another analytical tool to capture such data collection process [44], which we will explore more in the future.


## 9. Conclusions

In this paper, we have analytically investigated the on-demand MDC in cyber-physical systems. Two queuing models, namely, anM/G/1 and an M/G/c model, have been constructed to capture the MDC with a single MA and multiple MAs, respectively. System measures of the queues, for example, the expected values and distributions of queue length, queuing time, and response time have been explored. These queuing models shed light on the impact of different parameters on MDC, and the corresponding analytical results serve as guidelines in the design of more sophisticated data collection solutions. The soundness of the models and the accuracy of the analysis have been verified via extensive simulations.Through the queue-based analysis, it is clear that the MAs’ travel distance between two consecutively served requests is the dominant factor that determines the data collection latency, which should be minimized to achieve a better performance. Inspired by this, in our recent work [11], we have extended these queuing models to investigate the MDC with a greedy service discipline that minimizes the travel distance between two consecutively served requests, and a significant improvement can be observed asymptotically.



---

*Source: 5913981-2018-04-30.xml*