Spatio-Temporally Adaptive Waiting Time for Cell Phone Sensor Networks

Abstract

In cell phone sensor networks (CpSN), sensor-embedded cell phones communicate sensor data using Near Field Communication outlets such as Wi-Fi or Bluetooth. This paper considers a query dissemination application of CpSN, where sensor data belonging to a certain time window [ $t_{s,\min }$ , $t_{s,\max }$ ] is needed from a region of interest. Existing approaches, such as ADAPT, use adaptive broadcast ranges at the Wireless Access Point (WAP) for query dissemination. This paper proposes the adaptation of waiting time at nodes for energy-efficient query dissemination. The design and analysis of the proposed Spatio-Temporally Adaptive Distributed Velocity Dependent (STA-DVD) waiting time is presented. The STA-DVD protocol is analytically compared with a Spatially Adaptive Distributed Velocity Dependent (SA-DVD) waiting time based protocol. Simulation results show that STA-DVD has a superior querying performance in terms of number of samples procured than SA-DVD, at a slightly higher energy cost. For the case of a Randomized Waiting (RW) time adopted by nodes in ADAPT, the ADAPT-RW protocol has the best querying performance, with significantly high energy costs. STA-DVD has a comparable querying performance with ADAPT-RW, for high residual times and a better performance for low residual times, with significantly low energy dissipation.

1. Introduction

Cell phone-based sensor networks are constituted by cell phones which are additionally empowered with sensing capabilities [1–6]. While the ubiquitous use of cell phones for regular voice applications resolves issues related to the deployment and provision of energy for the embedded sensors, the mobility of cell phone users provides improved coverage and energy efficiency [7, 8]. These networks can either use the cellular bandwidth (as in [9, 10]) or can use short-range communication outlets such as Wi-Fi or Bluetooth [11] to share sensor data. Cell phone-based sensor networks can cater to various urban sensing applications such as environmental monitoring, urban planning, natural resource management, civic hazard detection, and information sharing. Some of the on-going research in this relatively nascent area are discussed in Section 9. In this paper, we consider an architecture of cell phone-based sensor networks, where cell phones use short-range communications to transmit sensor data. Such networks (shown in Figure 1) are referred to as cell phone sensor networks (CpSNs). This paper specifically focusses on an application of CpSN which requires carbon monoxide (CO) levels, belonging to a particular time window $[t_{s,\min \hspace{0.17em}},t_{s,\max \hspace{0.17em}}]$ , from a region of interest. This involves the querying of nodes, by a wireless access point (WAP) in the specified region, to sense CO levels during the time window. Flooding of the query maximizes chances of querying more number of nodes, at the cost of increased interference which disrupts ongoing communications. Therefore, this work essentially develops an energy-efficient query dissemination scheme which maximizes the number of nodes (cell phones) queried to sense data within the time interval $[t_{s,\min \hspace{0.17em}},t_{s,\max \hspace{0.17em}}]$ , in the region of interest.

Figure 1

Schematic representaion of a cell phone sensor network (CpSN).

Figure 2 shows a schematic of the sensing platform on the cell phone, consisting of the query processing module, sensing module and data processing module. For the query dissemination application, the rate and duration of activation of the query processing module determines the energy dissipated by the sensing platform. In order to minimize this energy, this module can be scheduled to be activated only when the node needs to handle a query. The duration for which this module remains active, after it has been activated, is the parameter of interest in this paper. We refer to this duration as the waiting time, ${\tau }_w$ , of a node (Figure 2). During its ${\tau }_w$ , the node coordinates with the querying WAP and waits to receive the query from it. At the end of its ${\tau }_w$ , it activates the sensing module to collect samples until time $t_{s,\max \hspace{0.17em}}$ . The waiting time must be large enough for coordination to occur with the querying WAP and for the node to receive the query from the WAP. The waiting time must be small enough for the listening energy consumed during the coordination process to be minimized. In this work, we focus on the design and analysis of waiting time, specifically suitable for the dissemination of a query with temporal constraints, in a single-hop cell phone sensor network (CpSN).

Figure 2

Sensing platform on cell phone.

In [12], a randomized waiting (RW) time is proposed for supporting data aggregation in static wireless sensor networks. Adopting a randomized waiting time at nodes for the query dissemination application in CpSN would be an inefficient approach, as it is not tailored to address the following design challenges in CpSN.

• (i)

Nonuniform node distribution: in this work, we assume a random waypoint (RWP) [13, 14] distribution of cell phone users, where node density decays from the center of the cell, towards the boundaries. Therefore, the waiting time of nodes near boundaries must be large to ensure connectivity. On the other hand, waiting time of nodes closer to the center can be small, since nodes will have sufficient connectivity. Thus, the waiting time must vary spatially.

(ii)

Dynamic topology: the mobility of cell phone users causes a time-varying connectivity between users. We hence adopt a velocity-dependent waiting time for each node.

(iii)

Temporal constraints of the query: the sampled data needs to belong to the time window $(t_{s,\min \hspace{0.17em}}\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{t}_{s,\max \hspace{0.17em}})$ . If the query arrives at the WAP from the network, at t, where $t_{s,\min \hspace{0.17em}}\le t\le t_{s,\max \hspace{0.17em}}$ , the residual time of the application is defined as $(t_{s,\max \hspace{0.17em}}-t)$ . Existing approaches [11, 15], adapt the query broadcast range at the querying WAP, based on the application-dependent residual time, in order to maximize the number of nodes queried within $[t_{s,\min \hspace{0.17em}},t_{s,\max \hspace{0.17em}}]$ . ADAPT, proposed in [15], incorporates a temporally adaptive broadcast range at the querying WAP for query dissemination in the hybrid Metrosense architecture [16] comprising of static as well as hand-held sensing elements. ADAPT does not assume any underlying mobility model. A multihop CpSN (MCpSN), where spatio-temporal adaptation of broadcast range is done at the querying WAP and at intermediate nodes, was advocated in [11], for the RWP mobility model. While a high broadcast range in a single-hop CpSN (as in [15]) causes increased energy dissipation and interference; a MCpSN which uses multiple short-range broadcasts (as in [11]), is prone to path vulnerability and entails on-the-fly route discovery. In this paper, we propose a novel approach, where the waiting time of nodes is adapted, based on the application-dependent residual time of the query, in a single-hop CpSN.

The contributions of the paper can be summarized as follows:

• (i)

design and analysis of the proposed spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) waiting time for a Random Waypoint (RWP) [13] distribution of cell phone users,

(ii)

analytical comparison of the proposed spatio-temporally adaptive-distributed velocity dependent (STA-DVD) waiting time with the spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time which had been considered in [9–11],

(iii)

development of STA-DVD waiting time-based protocol for query dissemination,

(iv)

simulation-based perturbation analysis of the STA-DVD, SA-DVD, and ADAPT protocols.

The analytical and simulation results show that the proposed STA-DVD protocol has a querying performance, in terms of number of samples procured, superior to that of SA-DVD protocol at relatively higher energy costs. For small application-dependent residual times, the proposed STA-DVD protocol yields a comparable querying performance to that of ADAPT, however, with a significantly lower energy dissipation. It must be noted that, even though the STA-DVD protocol has been developed in this paper for single-hop CpSN, it can be extended to the case of multihop CpSN (MCpSN). Since the waiting time, (and not the broadcast power) is adapted in STA-DVD, the STA-DVD-based MCpSN would only differ from the single-hop CpSN in terms of the smaller range of broadcast powers available at the WAP or at an intermediate node and the additional requirement of an on-the-fly relay node discovery process (as in [11]).

The organization of the paper is as follows. The cell phone sensor network (CpSN) architecture and the system model are described in Sections 2 and 3, respectively. The waiting time in the spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) and spatially adaptive-distributed velocity-dependent (SA-DVD) protocols is proposed in Section 4, while the protocol for query dissemination is described in Section 5. Section 6 analytically derives the time stationary waiting time distribution in SA-DVD and STA-DVD. Section 7 discusses the choice of broadcast range at the WAP for these protocols. Section 8 presents the simulation results. Section 9 briefly describes on-going research in cell phone-based sensor networks and Section 10 presents the conclusions of the paper.

2. Architecture

In the cell phone sensor network (CpSN) architecture shown in Figure 1, the end-user application injects a query into the cell phone sensor cloud through a wired/wireless wide area network. The query is issued to a wireless access point (WAP) in the region of interest. The WAPs in this network, communicate with cell phones equipped with sensors, over a single-hop in half-duplex mode. Since sensor-based applications are in general low data-rate applications, we assume a multichannel, edium access control (MAC) scheme [17–19] for uplink communication in the CpSN framework. The multichannel MAC scheme assumed in this paper is similar to the hybrid-orthogonal frequency division multiple access (hybrid-OFDMA) scheme considered in [17]. For the CpSN, the channel bandwidth can be subdivided into orthogonal subchannels, with each subchannel constituted by a set of orthogonal subcarriers. The number of subcarriers within a subchannel, as well as the number of subchannels assigned to each user can be design parameters. If the number of subchannels is less than the number of users, contention can be implemented within each subchannel as in carrier sense multiple access (CSMA) schemes [17]. For low data rate sensing applications, such a scheme in the uplink results in fewer chances of collisions when nodes try to communicate independently and simultaneously with the WAP. The WAP in turn can use all the subchannels to communicate with nodes on the downlink.

3. System Model

Path Loss Model. Since we consider a single-hop cell phone sensor network (CpSN), we assume a log-normal path loss model [20]. If l is the known distance between source and destination, the transmission power $P(l)$ at the source is computed as

$\begin{array}{c}P\left(l\right)=P_d{\left(\frac{4\pi }{\lambda }\right)}^2{\left(\frac{l}{d_0}\right)}^n\end{array},$

(1)

$P_d$ is the minimum received power required for successful reception at the destination. For a known receiver sensitivity s in dBm, $P_d=10^{s/10}\hspace{0.17em}\text{mW}$ , λ is the wavelength of the Radio-Frequency (RF) signal, n is the path-loss exponent, and the reference distance $d_0=1\hspace{0.17em}\text{m}$ .

Energy Model of Mobile Phones

The sensing application is initiated by the mobile phone when it is activated by the querying application. At all other times, cell phone resources are used for regular (voice/text) applications. For any two time instants, $t_1$ and $t_2$ lying between two consecutive sensing application activation instants, we assume that the residual battery energy B decays linearly in the following manner:

$\begin{array}{c}B\left(t_2\right)=B\left(t_1\right)-\frac{(t_2-t_1)B_{\max }}{T_{\max }}\end{array}.$

(2)

In (2), $B_{\max \hspace{0.17em}}$ is the battery rating of the cell phone and $t_2>t_1$ . $T_{\max \hspace{0.17em}}$ is the corresponding talktime rating which determines the maximum duration for which the cell phone can be powered while performing regular applications. Therefore, assuming that a residual energy of $B_{\max \hspace{0.17em}}$ would decay within a time duration $T_{\max \hspace{0.17em}}$ , the energy drained within a duration $t_2-t_1$ would be $(t_2-t_1)B_{\max \hspace{0.17em}}/T_{\max \hspace{0.17em}}$ .

4. Waiting Time-Based Query Dissemination

In this section, the waiting time framework is developed for a single-hop half-duplex cell phone sensor network (CpSN).

4.1. Waiting Time Connectivity (WTC) in a Single-hop CpSN

The query processing module of each node is associated with a waiting time ${\tau }_w$ (Figure 2). During ${\tau }_w$ , the node waits to receive the query from the WAP and remains in a listening mode. Connectivity in a CpSN is defined based on the waiting time of nodes. We propose the following waiting time connectivity (WTC) rule.

Let ${\tau }_w(i)$ be the waiting time of node i and R the broadcast range of the querying WAP. For node i to be successfully queried by the WAP, the following condition must hold:

$\begin{array}{c}{\tau }_w\left(i\right)>\frac{2R}{c}\end{array},$

(3)

where c is the radiowave propagation velocity. If the relation (3) holds, the node i is connected to the WAP. Given that node i is connected to the WAP, relation (3) implies the following,

• Implication (a). If ${\tau }_w(i)$ is small, R must be small,

• Implication (b). If ${\tau }_w(i)$ is large, R can be large.

Conversely,

Implication (c). If R is small, ${\tau }_w(i)$ can be small,

Implication (d). If R is large, ${\tau }_w(i)$ must be large.

The factor $2R/c$ in relation (3) is considered due to the half-duplex assumption of the CpSN framework, as shall be explained in Section 5.

4.2. Waiting Time in a CpSN

Connectivity of nodes to the WAP is essential in order to maximize the number of nodes that get successfully queried by the WAP. Large waiting times ensure high connectivity in the CpSN, as more number of nodes satisfy the relation (3). At the same time, very large waiting times lead to an increased dissipation of listening energy during the waiting time and of communication energy due to more number of nodes satisfying WTC with the WAP. Thus, the design of waiting time is a tradeoff between overall energy dissipated in the network and the number of nodes tasked by the querying WAP.

4.2.1. Waiting Time in the Proposed STA-DVD Protocol

For a node, i, we propose the following definition of waiting time for the spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) waiting time-based protocol as ${\tau }_w(i)={\tau }_{ϵ}(i)$ , where

$\begin{array}{c}{\tau }_{ϵ}\left(i\right)=\left(1-\frac{v\left(i\right)}{v_{\max }}\right)\frac{d_s\left(i\right)}{cϵ},\end{array}$

(4)

$d_s(i)$ is the estimated distance of node i from base station (BS), which is assumed to be located at the center of the cell. $v(i)$ is the instantaneous node velocity, $v_{\max \hspace{0.17em}}$ is the maximum node velocity in the network, and ϵ is the fractional residual time of the application as defined in (5). The dependence of the STA-DVD waiting time, ${\tau }_{ϵ}$ , on each of these factors is described in the following paragraphs.

Distance from BS ( $d_s$ )

Owing to the RWP distribution, nodes occur sparsely at large distances from the center (BS location). A WAP located at this distance must, therefore, have a large broadcast radius, R, in order to communicate the query to as many nodes as possible. Consequently, nodes must have large waiting times (Implication (d)) to ensure that they are connected to the WAP. Since node density is higher near the BS, a WAP located near the BS can have a small broadcast range, R, in order to communicate the query to a sufficient number of nodes within its range circle. Nodes can, therefore, have small waiting times and yet be connected to the WAP (Implication (c)). Thus, in (4), waiting time of nodes is designed to progressively increase with distance from the centrally located BS.

Instantaneous Velocity $(v(i))$

Fast-moving nodes stay within the WAP range circle for short durations of time, during which they can successfully communicate with the WAP. Therefore, such nodes are assigned small waiting times in order to minimize packet losses in this communication. Slow moving nodes, however, stay within the WAP range circle for longer durations and can, therefore, be assigned larger waiting times, during which they can successfully communicate with the WAP.

Fractional Residual Time of the Application $(ϵ)$

The application considered, requires data to be sensed within the time interval $[t_{s,\min \hspace{0.17em}},t_{s,\max \hspace{0.17em}}]$ . Let the query arrive at the WAP located in the region of interest, at time t, where, $t_{s,\min \hspace{0.17em}}\le t\le t_{s,\max \hspace{0.17em}}$ . Then, the residual time of the application is given by $(t_{s,\max \hspace{0.17em}}-t)$ and the application-dependent fractional residual time, ϵ, is given by

$\begin{array}{c}ϵ=\frac{t_{s,\max }-t}{t_{s,\max }-t_{s,\min }}\end{array}.$

(5)

when the residual time $(t_{s,\max \hspace{0.17em}}-t)$ is low, the waiting time of nodes needs to be increased in order to increase the number of nodes that satisfy WTC in (3) (and are thus likely to be queried). In STA-DVD, the waiting time is made inversely proportional to the application-dependent fractional residual time, ϵ. Thus, in STA-DVD, the waiting time of nodes is made sensitive to the time specifications of the application.

4.2.2. Waiting Time in SA-DVD Protocol

The purely location and velocity-dependent waiting time which had been proposed earlier in [9–11] does not consider the temporal constraints of the query. We refer to the protocol for a single-hop CpSN based on this spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time (adopted in [9–11]), as the SA-DVD protocol. For a node, i, the definition of waiting time for the SA-DVD protocol is given by ${\tau }_w(i)=\tau (i)$ , where

$\begin{array}{c}\tau \left(i\right)=\left(1-\frac{v\left(i\right)}{v_{\max }}\right)\frac{d_s\left(i\right)}{c}\end{array},$

(6)

$d_s(i)$ is the estimated distance of node i from BS, $v(i)$ is the node velocity and $v_{\max \hspace{0.17em}}$ is the maximum node velocity in the network. The dependence of τ on $d_s$ and v is as described for STA-DVD in (4), and as explained in [9–11].

5. Query Dissemination Protocol

The proposed spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) protocol is based on the STA-DVD waiting time proposed in (4), while the spatially adaptive-distributed velocity-dependent (SA-DVD) protocol is based on the SA-DVD waiting time considered in [9–11] and discussed in (6). This being the primary distinction between the STA-DVD protocol and the SA-DVD protocol, the following steps and Figure 3 describe the steps in the query dissemination operation in STA-DVD and SA-DVD in a single-hop cell phone sensor network (CpSN).

Figure 3

Steps in Query dissemination.

The wireless access Point (WAP) which is injected with the query, broadcasts the request to send query, as shown in Figure 3(a). For STA-DVD, RTS: [WAP location, sensor type, ϵ, R]; and for SA-DVD, RTS: [WAP location, sensor type, R]. For both STA-DVD and SA-DVD, the broadcast power corresponding to a transmission range R, is computed as described in Section 7. After broadcasting the RTS, the WAP switches to the receive mode.

In the proposed spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) protocol, the query processing module of a node which receives the RTS, computes a spatio-temporally adaptive waiting time, ${\tau }_{ϵ}$ . In the spatially adaptive-distributed velocity -dependent (SA-DVD) protocol, the query processing module of a node which receives the RTS, computes a spatially adaptive waiting time, τ. In both cases, the node replies with a CTS: (node location, WAP location, sensor availability bit) if: (a) it is willing to participate in query dissemination, (b) it satisfies waiting time connectivity (WTC) with the WAP (3) and (c) the sensor availability bit = 1, indicating the presence of the desired sensor. Since we assume a multichannel MAC on the uplink [17–19], nodes can send CTS to the WAP simultaneously on different subchannels.

The query processing module of a node that has transmitted the CTS initiates a timer which has a value equal to the waiting time of the node (Figure 2). During this period, the node waits to receive the query from the WAP.

We assume half-duplex communication in the network. Hence, the WAP waits to receive CTS for the round-trip duration of $2R/c$ from the time at which it broadcasts the RTS, in order to receive CTS even from nodes lying in the boundary of its range circle. After this duration, it sends the query to the nodes that have replied with CTS (Figure 3(c)). The duration $2R/c$ also corresponds to the minimum duration for which a node must be in listening mode, from the time it replies with a CTS, in order to receive the query successfully from the WAP. Therefore, any node receiving $RTS$ compares its waiting time ${\tau }_w$ with $2R/c$ to determine its connectivity with WAP (WTC in (3)).

A node which receives the query within its waiting time activates the sensing module at the end of its waiting time. Samples are collected at the sampling rate $f_s$ of the particular sensor, till the end, $t_{s,\hspace{0.17em}\hspace{0.17em}\max \hspace{0.17em}}$ , of the sampling interval $[t_{s,\min \hspace{0.17em}},\hspace{0.17em}\hspace{0.17em}{t}_{s,\max \hspace{0.17em}}]$ specified in the query.

The RTS-CTS scheme specifically considered in this protocol does not involve internode communication typically observed in wireless LAN protocols. RTS, in particular, refers to a broadcast packet sent by the WAP, while CTS pertains to a unicast transmission from a node to the WAP. Note that the delays incurred in switching between channels or in switching between the transmit/receive modes, both at the WAP and at nodes, have not been considered in this work while computing waiting times.

5.1. Infimum of ϵ in a CpSN

In order to ensure that there is sufficient time available for the two-way signalling involved in the protocol, the application-dependent fractional residual time, ϵ, cannot be too small. Hence, we derive the greatest lower bound (infimum), ${ϵ}_{\min \hspace{0.17em}}$ , of ϵ, at any WAP which has a minimum broadcast range of $R=R_{\min \hspace{0.17em}}$ . In this work, we consider the following constraint imposed by the query dissemination protocol.

Statement 1.

For a given $R\ge R_{\min \hspace{0.17em}}$ , the minimum time available for the sensing application, at any node located at the boundary of the WAP range circle, must be greater than 0.

The time at which the query arrives at a node at the boundary of the WAP range circle is given by

$\begin{array}{c}t+\frac{3R}{c}\end{array},$

(7)

where t is the time at which the query arrives at the WAP. The time available for the sensing application at such a node is

$\begin{array}{c}{t}_{s,\max }-(t+\frac{3R}{c})\end{array}.$

(8)

According to Statement 1, this duration must be greater than 0. Therefore, for a given R, the application-dependent ϵ must satisfy the following condition:

$\begin{array}{c}ϵ>\frac{3R}{c{\delta }_0}\end{array},$

(9)

where ${\delta }_0=t_{s,\max \hspace{0.17em}}-t_{s,\min \hspace{0.17em}}$ , $ϵ=(t_{s,\max \hspace{0.17em}}-t)/{\delta }_0$ and c is the radiowave propagation velocity.

Substituting $R=R_{\min \hspace{0.17em}}$ in the relation (9), the greatest lower bound (infimum) of $ϵ={ϵ}_{\min \hspace{0.17em}}$ for the CpSN can be obtained as:

$\begin{array}{c}{ϵ}_{\min }=\frac{3R_{\min }}{c{\delta }_0}\end{array}.$

(10)

In general, if an application has ϵ such that ${ϵ}_{\min \hspace{0.17em}}<ϵ\le 1$ , it will be handled by the WAP in both STA-DVD and SA-DVD.

5.2. Supremum of Waiting Time of a Node in STA-DVD

In STA-DVD, for the case of $d_s=d$ , $v=0$ and $ϵ={ϵ}_{\min \hspace{0.17em}}$ , (4) gives the least upper bound (supremum) of ${\tau }_{ϵ}$ given by

$\begin{array}{c}{\tau }_{ϵ,\max }=\frac{d}{c{ϵ}_{\min }}=\frac{d{\delta }_0}{3R_{\min }}\end{array}.$

(11)

Therefore, taking into consideration the range of ϵ values that can belong to application queries arriving at the WAP, the waiting time, ${\tau }_{ϵ}$ , of any node in STA-DVD would lie in the range, $0\le {\tau }_{ϵ}<{\tau }_{ϵ,\max \hspace{0.17em}}$ .

5.3. Maximum Waiting Time of a Node in SA-DVD

In SA-DVD, the waiting time of a node is independent of the application-dependent ϵ. Therefore, even though Statement 1 must hold for SA-DVD protocol as well, the maximum waiting time of a node in an SA-DVD-based CpSN can be simply obtained when $d_s=d$ and $v=0$ in (6); that is,

$\begin{array}{c}{\tau }_{\max }=\frac{d}{c}.\end{array}$

(12)

6. Time-Stationary Waiting-Time Distribution

In order to study the effect of context-dependent adaptation of waiting time on the performance of the querying protocols, we derive the probability density function ( $pdf$ ) of the normalized spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) waiting time of nodes. To derive the $pdf$ of the STA-DVD waiting time, we first derive the $pdf$ corresponding to the existing purely spatially adaptive waiting time, considered in [9–11] and adopted in the spatially adaptive-distributed velocity-dependent (SA-DVD) protocol.

6.1. Normalized SA-DVD Waiting Time

For a node i, with spatially adaptive waiting time $\tau (i)$ , we define its normalized spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time, $\tilde{\tau }(i)$ as

$\begin{array}{c}\tilde{\tau }\left(i\right)=\frac{\tau \left(i\right)}{{\tau }_{\max }}\end{array},$

(13)

where ${\tau }_{\max \hspace{0.17em}}$ is the maximum value that can be assumed by the spatially adaptive waiting time in (6). Specifically, $\tau (i)={\tau }_{\max \hspace{0.17em}}$ when $v(i)=0$ and $d_s(i)=d$ , where d is the cell radius, in (6). Therefore, ${\tau }_{\max \hspace{0.17em}}=d/c$ , as obtained in (12). Note that the normalization in the normalized spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time in (13) has been done with respect to the cell radius. Equation (13) can be rewritten as

$\begin{array}{c}\tilde{\tau }\left(i\right)=(1-\frac{v\left(i\right)}{v_{\max }})r\left(i\right)\end{array},$

(14)

where $r(i)=d_s(i)/d$ . The $pdf$ of normalized waiting time for SA-DVD has to be derived for nodes within the range circle of the WAP, and not for nodes in the entire network. The $pdf$ for SA-DVD waiting time, is then used to obtain the $pdf$ of the proposed normalized spatio-temporally adaptive-distributed velocity-dependent STA-DVD waiting time as in Section 6.4.

6.2. Probability Density Function of Normalized SA-DVD Waiting Time Within the WAP Range Circle

Equation (14) can be written in its generic form as

$\begin{array}{c}\tilde{\tau }=\psi r\end{array},$

(15)

where the velocity-dependent factor, $\psi =1-v/v_{max}$ (the index i is dropped for brevity). Note that both $\psi \le 1$ and $|r|\le 1$ . Therefore, $\tilde{\tau }\le r$ and $\tilde{\tau }\le \psi$ . The probability density function $f_{\tilde{\tau }}(\tilde{\tau })$ is given by [21]

$\begin{array}{c}{f}_{\tilde{\tau }}\left(\tilde{\tau }\right)={{\displaystyle \int }}_{-\infty }^{\infty }\frac{1}{\left|\psi \right|}{f}_{\psi r}\left(\psi ,\frac{\tilde{\tau }}{\psi }\right)d\psi \end{array},$

(16)

where $f_{\psi r}$ is the joint $pdf$ of ψ and r. Since ψ and r are independent (velocity chosen by a node and location of a node are independent of each other), (16) can be re-written as [21]

$\begin{array}{c}{f}_{\tilde{\tau }}\left(\tilde{\tau }\right)={{\displaystyle \int }}_{-\infty }^{\infty }\frac{1}{\left|\psi \right|}{f}_{\psi }\left(\psi \right)f_r\left(\frac{\tilde{\tau }}{\psi }\right)d\psi \end{array},$

(17)

where $f_{\psi }(\psi )$ is the $pdf$ of ψ and $f_r(\tilde{\tau }/\psi )$ is the $pdf$ of node occurrence at a distance of $r=\tilde{\tau }/\psi$ from BS.

Probability Density Function of ψ

From $\psi =1-v/v_{\max \hspace{0.17em}}$ , it can be inferred that $f_{\psi }(\psi )=|v_{\max \hspace{0.17em}}|f_v(v)$ ([21]), where $f_v(v)$ is the $pdf$ of node velocity. From [13], $f_v(v)$ for a random-waypoint (RWP) model with pauses is given by

$\begin{array}{c}{f}_v\left(v\right)=\{\begin{array}{cc}\frac{P_{\text{mo}}}{v\ln \left(v_{\max }/v_{\min }\right)}\hfill & v_{\min }\le v\le v_{\max },\hfill \\ P_{\text{pa}}\delta \left(v\right)\hfill & v=0,\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}\end{array}$

(18)

where $P_{\text{mo}}$ is the probability of a node to be in motion state, while $P_{\text{pa}}$ is the probability of a node to be in pause state. If $\mathrm{\Delta }$ is the maximum diameter of the area from which a node can choose its position, and if $t\_\text{pause}(\min \hspace{0.17em})$ and $t\_\text{pause}(\max \hspace{0.17em})$ represent the minimum and maximum pause durations, respectively, then [13]

$\begin{array}{cc}\hfill & \begin{array}{c}{P}_{\text{pa}}=\frac{\beta }{\beta +\Delta }\end{array},\hfill \\ \hfill & \begin{array}{c}{P}_{\text{mo}}=1-P_{\text{pa}}\end{array},\hfill \end{array}$

(19)

where $\beta =0.5(t\_\text{pause}(\max \hspace{0.17em})+t\_\text{pause}(\min \hspace{0.17em}))$ and $\mathrm{\Delta }=2d$ for the cell of radius d. Therefore,

$\begin{array}{c}{f}_{\psi }\left(\psi \right)=\{\begin{array}{cc}\frac{P_{\text{mo}}}{\left(1-\psi \right)\ln \left(v_{\max }/v_{\min }\right)}\hfill & 0\le \psi \le \left(1-\frac{v_{\min }}{v_{\max }}\right),\hfill \\ P_{\text{pa}}\delta \left(1-\psi \right)\hfill & \psi =1,\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}\end{array}$

(20)

Probability Density of Node Location at a Distance r from BS, Within the WAP Range Circle

The probability of node occurrence at a distance r from the origin (0,0) in a cell of unit radius, is an angularly symmetric function for the RWP distribution [13]. Therefore, the probability of node occurrence would be the same within a circle centered at $(\alpha ,\rho )$ and within a circle centered at $(\alpha ,0)$ , where both these circles lie within the circle of unit radius over which the angularly symmetric function is defined. Without loss of generality, any circle centered at $(\alpha ,\rho )$ , where $\rho \ne 0$ , can be rotated to the location $(\alpha ,0)$ for analytical simplicity. Let $d_w$ be the distance of the WAP from the BS and R be the broadcast range of the WAP. Then, as shown in Figure 4, we define $\alpha =d_w/d$ as the normalized distance of the WAP from the BS, and $\tilde{R}=R/d$ as the normalized broadcast range of the WAP (Figure 4). Here, we define the probability density function, $f_r(r)$ , to be the probability of node occurrence at a normalized radial distance r from the center (0,0) (corresponding to the BS location), within the broadcast range circle of normalized radius, $\tilde{R}$ . For a circular disk of unit radius, from [13, 14]

$\begin{array}{c}{f}_r\left(r\right)=\frac{45}{32\pi }\left(1-r^2\right)E\left(r^2\right)\varphi \left(r\right)\end{array},$

(21)

where $r=\sqrt{x^2+y^2}$ , $\alpha -\tilde{R}\le r\le \alpha +\tilde{R}$ and $E(r^2)={\int }_0^{\pi /2}\sqrt{(1-r^2\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}si{n}^2(\theta ))}d\theta$ . The instantaneous angle $\varphi (r)$ is the angle inscribed at the center (BS location) by an arc within the range circle, which is located at a distance of r from the center (as shown in Figure 4). The computation of this angle has been derived in the Appendix of this paper.

Figure 4

Broadcast circle of radius $\tilde{R}$ within a cell of normalized radius.

Therefore, using (20) and (21) in (17), the $pdf$ of normalized spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time $\tilde{\tau }$ , is given by (22). The analytical plot of $f_{\tilde{\tau }}(\tilde{\tau })$ is shown in Figure 5, while the corresponding histogram plot obtained from simulations is shown in Figure 6. Figure 7 shows the analytical plot of the corresponding cumulative distribution function (CDF), $F_{\tilde{\tau }}(\zeta )$ .

$\begin{array}{c}{f}_{\tilde{\tau }}\left(\tilde{\tau }\right)=\{\begin{array}{c}\begin{array}{c}\frac{45}{32\pi }\frac{P_{\text{mo}}}{\ln \left(v_{\max }/v_{\min }\right)}{{\displaystyle \int }}_{\tilde{\tau }/\alpha +\tilde{R}}^{\tilde{\tau }/\alpha -\tilde{R}}\frac{1}{\left|\psi \right|}\frac{\tilde{\tau }\varphi \left(\tilde{\tau }/\psi \right)}{\psi \left(1-\psi \right)}\left(1-{\left(\frac{\tilde{\tau }}{\psi }\right)}^2\right)E\left({\left(\frac{\tilde{\tau }}{\psi }\right)}^2\right)d\psi \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\\ \hspace{1em}\begin{array}{cc}+\frac{45\tilde{\tau }\varphi \left(\tilde{\tau }\right)}{32\pi }{P}_{\text{pa}}\left(1-{\left(\tilde{\tau }\right)}^2\right)\hspace{0.17em}\hspace{0.17em}E\left({\left(\tilde{\tau }\right)}^2\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}0<\tilde{\tau }\le \left(1-\frac{v_{\min }}{v_{\max }}\right)\left(\alpha +\tilde{R}\right),\end{array}\hspace{1em}\hspace{1em}\hspace{1em}\\ \begin{array}{cc}\frac{45\tilde{\tau }}{32\pi }{P}_{\text{pa}}\varphi \left(\tilde{\tau }\right)\left(1-{\left(\tilde{\tau }\right)}^2\right)\hspace{0.17em}\hspace{0.17em}E\left({\left(\tilde{\tau }\right)}^2\right)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left(1-\frac{v_{\min }}{v_{\max }}\right)\left(\alpha +\tilde{R}\right)<\tilde{\tau }\le \left(\alpha +\tilde{R}\right),\end{array}\\ \begin{array}{cc}0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{otherwise}.\end{array}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\end{array}\hfill \end{array}\end{array}$

(22)

Figure 5

Analytical plot of $f_{\tilde{\tau }}(\tilde{\tau })$ for normalized SA-DVD waiting time $\tilde{\tau }$ , for $\tilde{R}=0.15,\alpha =0.4$ .

Figure 6

Histogram plot of $f_{\tilde{\tau }}(\tilde{\tau })$ for normalized SA-DVD waiting time $\tilde{\tau }$ for $\tilde{R}=0.15,\alpha =0.4$ .

Figure 7

Cumulative distribution function (CDF) $F_{\tilde{\tau }}(\zeta )$ for normalized SA-DVD waiting time $\tilde{\tau }$ for $\tilde{R}=0.15,\alpha =0.4$ .

6.3. Proposed Normalized STA-DVD Waiting Time ${\tilde{\tau }}_{ϵ}$

In addition to spatial adaptation of waiting time to suit the RWP distribution, temporal adaptation of waiting time needs to be further incorporated in the spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time, in order to meet the temporal constraints of the query. Specifically, if the query arrives at the WAP at t, where $t_{s,\min \hspace{0.17em}}\le t\le t_{s,\max \hspace{0.17em}}$ , the application-dependent fractional residual time, $ϵ=\delta (t)/{\delta }_0$ (5), where $\delta (t)=t_{s,\max \hspace{0.17em}}-t$ and ${\delta }_0=t_{s,\max \hspace{0.17em}}-t_{s,\min \hspace{0.17em}}$ , can be used to tune the normalized SA-DVD waiting time, $\tilde{\tau }$ , in order to obtain the proposed normalized spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) waiting time. We propose the following relation between the normalized SA-DVD waiting time, $\tilde{\tau }$ and normalized STA-DVD waiting time ${\tilde{\tau }}_{ϵ}$

$\begin{array}{c}{\tilde{\tau }}_{ϵ}=\frac{\tilde{\tau }}{ϵ}\end{array}.$

(23)

This relationship is carried over to the actual values of the proposed STA-DVD and SA-DVD waiting times defined, in Sections 4.2.1 and 4.2.2 respectively.

Note that the normalization in ${\tilde{\tau }}_{ϵ}$ has been done only with respect to the cell radius d, as in the case of spatially adaptive waiting time. The waiting time in SA-DVD can be considered as a special case of waiting time in STA-DVD if ϵ is assumed to be 1, irrespective of the actual value of application-dependent $ϵ=\delta (t)/{\delta }_0$ , calculated at the WAP. In other words, the value of application-dependent ϵ calculated at the WAP, is not used by nodes while computing waiting time in SA-DVD. This also implies that the waiting time of nodes in STA-DVD reduces to the waiting time of nodes in SA-DVD, that is, ${\tilde{\tau }}_{ϵ}=\tilde{\tau }$ , when the value of application-dependent ϵ calculated at the WAP is 1.

6.4. Probability Density Function of Proposed Normalized STA-DVD Waiting Time Within the WAP Range Circle

The $pdf$ , $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ of the proposed normalized spatio-temporally adaptive-distributed velocity-dependent STA-DVD waiting time, ${\tilde{\tau }}_{ϵ}$ in the STA-DVD protocol, can be obtained from [21]

$\begin{array}{c}{f}_{{\tilde{\tau }}_{ϵ}}\left({\tilde{\tau }}_{ϵ}\right)=ϵf_{\tilde{\tau }}\left(\tilde{\tau }\right)\end{array},$

(24)

where $0\le {\tilde{\tau }}_{ϵ}\le (\alpha +\tilde{R})/ϵ$ and $f_{\tilde{\tau }}(\tilde{\tau })$ is as defined in (22).

In Figures 8 and 10, $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ is evaluated for application-dependent $ϵ=0.7778$ and $ϵ=0.3737$ , respectively. The corresponding histogram plots, obtained by simulation are given in Figures 9 and 11, respectively. As can be seen, the waiting time range increases as ϵ decreases. Also shown in Figures 8 and 10 is $f_{\tilde{\tau }}(\tilde{\tau })$ corresponding to the $pdf$ of normalized waiting time in SA-DVD which is equivalent to the specific case of $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ for $ϵ=1$ .

Figure 8

Analytical plot of $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ for $ϵ=0.7778$ .

Figure 9

Histogram plot of ${\tilde{\tau }}_{ϵ}$ for $ϵ=0.7778$ .

Figure 10

Analytical plot of $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ for $ϵ=0.3737$ .

Figure 11

Histogram plot of ${\tilde{\tau }}_{ϵ}$ for $ϵ=0.3737$ .

6.5. Mean and Variance of Waiting Time in STA-DVD and SA-DVD

Table 1 gives the mean and variance of normalized waiting time (through analysis and simulations) in STA-DVD for different ϵ. It also shows these values for application-dependent $ϵ=1$ . This corresponds to the case when the waiting time in STA-DVD and SA-DVD are the same. As can be seen, the mean and variance of waiting time is minimum when $ϵ=1$ and increases as ϵ decreases. Note that different values of $\tilde{R}$ are chosen for each of the ϵ values. For a particular ϵ value, there is a corresponding $\tilde{R}$ value which yields the best protocol performance in terms of number of samples procured. This choice of a suitable $\tilde{R}$ value at the WAP, as a function of the application-dependent ϵ, is explained in Section 7.

Table 1

Analytic and simulation results for mean and variance for different $ϵ,\tilde{R}$ .

$ϵ,\tilde{R}$	Mean (analytic)	Mean (simulation)	Variance (analytic)	Variance (simulation)
1, 0.15	0.3383	0.3346	0.0127	0.0124
0.7778, 0.2	0.4353	0.4210	0.0263	0.0254
0.3737, 0.25	0.9072	0.8653	0.1417	0.1306

6.6. Waiting Time Connectivity (WTC) Computation

As explained in Section 5, since we consider half-duplex operation, the nodes which can receive and process the query are those which have a waiting time greater than $2R/c$ , which corresponds to a normalized waiting time $2\tilde{R}$ .

The probability,   $P_{\text{WTC}}$ (STA-DVD) in STA-DVD, that a node satisfies WTC, given that it lies within the range circle, is therefore given by

$\begin{array}{c}{P}_{\text{WTC}}\left(\text{STA-DVD}\right)={{\displaystyle \int }}_{2\tilde{R}}^{\alpha +\tilde{R}/ϵ}{f}_{{\tilde{\tau }}_{ϵ}}\left({\tilde{\tau }}_{ϵ}\right)d{\tilde{\tau }}_{ϵ}\end{array}.$

(25)

The corresponding probability in SA-DVD is given by

$\begin{array}{c}{P}_{\text{WTC}}\left(\text{SA-DVD}\right)={{\displaystyle \int }}_{2\tilde{R}}^{\alpha +\tilde{R}}{f}_{\tilde{\tau }}\left(\tilde{\tau }\right)d\tilde{\tau }\end{array}.$

(26)

The probability that a node lies within the WAP range circle of normalized radius $\tilde{R}$ , with the WAP located at a normalized radial distance of α from the center of the unit circle is given by

$\begin{array}{c}{P}_R={{\displaystyle \int }}_{\alpha -\tilde{R}}^{\alpha +\tilde{R}}{f}_r\left(r\right)dr,\end{array}$

(27)

where $f_r(r)$ is as defined in (21). The integral in (27) can be evaluated using the method described in the Appendix.

The joint probability, $P_q$ , of a node satisfying WTC (generically written as $P_{\text{WTC}}$ for STA-DVD and SA-DVD), and occurring within the range circle, is therefore given by

$\begin{array}{c}{P}_S=P_{\text{WTC}}\times P_R.\end{array}$

(28)

In (28), we make use of the fact that, the occurrence of a node within the WAP range circle is independent of its satisfying the relation (3).

The probability that a node in the network (unit circle in Figure 4) gets queried can be analytically obtained as

$\begin{array}{c}{P}_q=p\times P_{\text{WTC}}\times P_R,\end{array}$

(29)

where p is the probability of a node having the desired sensor.

The values of $P_{\text{WTC}}$ and $P_q$ obtained by analysis and simulation when $p=1$ and $\tilde{R}=0.15$ for the proposed STA-DVD waiting time, are given in Table 2. It also shows these values for application-dependent $ϵ=1$ . This corresponds to the case when the waiting time in STA-DVD and SA-DVD are the same. It can be seen that both $P_q$ and $P_{\text{WTC}}$ increase as ϵ decreases. However, note that the increase in value of $P_q$ is not significant as compared to theincrease in $P_{\text{WTC}}$ , for a given $\tilde{R}$ . This is because of the small value of $P_R$ corresponding to $\tilde{R}=0.15$ . Therefore, in this work, the $\tilde{R}$ chosen at the WAP for a specific ϵ aims to maximize $P_q$ corresponding to the particular ϵ. The relation between the choice of $\tilde{R}$ at the WAP and the ϵ value calculated at the WAP, is explained in Section 7.

Table 2

Analytic and simulation results for $P_{WTC}$ and $P_q$ for different ϵ when $\tilde{R}=0.15$ .

ϵ	$P_{\text{WTC}}$ (analytic)	$P_{\text{WTC}}$ (simulation)	$P_q$ (analytic)	$P_q$ (simulation)
1	0.6770	0.6769	0.0220	0.0308
0.7778	0.8460	0.8505	0.0333	0.0387
0.3737	0.9470	0.9473	0.0373	0.0431

6.7. Cumulative Distribution Function (CDF) $F_{{\tilde{\tau }}_{ϵ}}(\zeta )$

The Cumulative Distribution Function (CDF), $F_{{\tilde{\tau }}_{ϵ}}(\zeta )=\text{Prob}({\tilde{\tau }}_{ϵ}\le \zeta )$ , is evaluated as

$\begin{array}{c}{F}_{{\tilde{\tau }}_{ϵ}}\left(\zeta \right)={{\displaystyle \int }}_0^{\zeta }{f}_{{\tilde{\tau }}_{ϵ}}\left({\tilde{\tau }}_{ϵ}\right)d{\tilde{\tau }}_{ϵ}\end{array}.$

(30)

Suppose that $ϵ1>ϵ2$ and

$\begin{array}{c}{F}_{{\tilde{\tau }}_{ϵ1}}\left(\zeta \right)>F_{{\tilde{\tau }}_{ϵ2}}\left(\zeta \right)\end{array},$

(31)

It follows that

$\begin{array}{c}1-F_{{\tilde{\tau }}_{ϵ1}}\left(\zeta \right)<1-F_{{\tilde{\tau }}_{ϵ2}}\left(\zeta \right)\end{array}.$

(32)

which implies that

$\begin{array}{c}\text{Prob}\left({\tilde{\tau }}_{ϵ1}>\zeta \right)<\text{Prob}\left({\tilde{\tau }}_{ϵ2}>\zeta \right).\end{array}$

(33)

Therefore, the probability of nodes having normalized waiting times greater than ζ for $ϵ=ϵ1$ , is less than the probability of nodes having normalized waiting times greater than ζ for $ϵ=ϵ2$ , where $ϵ1>ϵ2$ .

Such a case is observed in Figures 12 and 13, which evaluate the CDF for $ϵ=0.7778,\hspace{0.17em}\hspace{0.17em}0.3737$ , respectively. As can be seen, for $\zeta =0.4$ , $F_{{\tilde{\tau }}_{ϵ}}(0.4)\approx \mathrm{0.429,0.156}$ for $ϵ=0.7778,\hspace{0.17em}\hspace{0.17em}0.3737$ , respectively. Figures 12 and 13 also show the CDF corresponding to SA-DVD (equivalently, $F_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ in STA-DVD when application-dependent $ϵ=1$ ). For the case of $ϵ=1$ , $F_{{\tilde{\tau }}_{ϵ}}(0.4)=F_{\tilde{\tau }}(0.4)=0.63$ . Thus, $F_{{\tilde{\tau }}_{ϵ}}(0.4)$ decreases as ϵ decreases. In other words, the probability of nodes having normalized waiting times greater than 0.4 increases as the residual time of the application decreases. Since this observation can be made for every value of ζ; and for low values of ζ in particular, it can be inferred that nodes tend to have higher waiting times as the residual time decreases. Hence, we state the following.

Figure 12

CDF of ${\tilde{\tau }}_{ϵ}$ , $F_{{\tilde{\tau }}_{ϵ}}(\zeta )$ in STA-DVD for $ϵ=0.7778$ .

Figure 13

CDF of ${\tilde{\tau }}_{ϵ}$ , $F_{{\tilde{\tau }}_{ϵ}}(\zeta )$ in STA-DVD for $ϵ=0.3737$ .

Statement 2.

In spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) protocol, nodes tend to have higher waiting times for low fractional residual times and lower waiting times for high fractional residual times.

7. Choice of Broadcast Range R at the WAP in SA-DVD and STA-DVD

In this section, we formulate a probabilistic estimate of the number of samples, $N_s$ , that can be procured for a particular ϵ, as a function of the broadcast range, R at the WAP. The computed value of $N_s$ is used to determine the broadcast range chosen by the WAP to transmit the RTS.

7.1. Dependence of $N_s(R)$ on $P_q$ for a Particular ϵ

Statement 3.

For a particular application-dependent ϵ, the number of samples, $N_s(R)$ is maximum for the R value corresponding to maximum $P_q$ .

The range R must be chosen to maximize $P_q$ (29), so that a maximum number of nodes get queried for the particular ϵ. From (27), choosing a large R increases $P_R$ , and hence, the number of nodes within the WAP range circle. The increased $P_R$ increases the probability $P_q$ in (29), equivalently increasing the chances of querying more number of nodes. At the same time, the number of nodes that will satisfy WTC with the WAP as per (3) may decrease if R is very large, since nodes may not have large waiting times, as was required by Implication (d) in Section 4.1. This may happen if nodes tend to have low waiting times with a greater probability (as in SA-DVD, or if the particular ϵ is high in STA-DVD, Statement 2). Thus, a large R can lead to low $P_{\text{WTC}}$ (in both (25) and (26)) and consequently, low $P_q$ values (29). A comparison of Table 2 and Table 3 further illustrates this point. Table 3 gives the values of $P_{\text{WTC}}$ and $P_q$ for varying $ϵ,\tilde{R}$ , while Table 2 provides the corresponding values for varying ϵ with $\tilde{R}=0.15$ . As can be seen, for $ϵ=0.7778$ , $P_{\text{WTC}}(\text{analytic})$ decreases from 0.8460 in Table 2 to 0.5958 in Table 3 when $\tilde{R}$ increases from 0.15 to 0.2. However, $P_q(\text{analytic})$ increases from $.0333$ in Table 2 to $.0441$ in Table 3, when $\tilde{R}$ increases from 0.15 to 0.2. A similar trend in $P_{\text{WTC}}$ and $P_q$ is also observed in the analytic and simulation values for $ϵ=0.3737$ . It can be inferred that although $P_{\text{WTC}}$ decreases when $\tilde{R}$ increases, $P_q$ increases due to the increase in $P_R$ , for a given ϵ value. Therefore, for a particular ϵ, R must be large enough to ensure that $P_R$ is high and must be small enough so that $P_{\text{WTC}}$ does not deteriorate significantly. Thus, R must be chosen such that it maximizes $P_q$ , for a given ϵ computed at the WAP.

Table 3

Analytic and simulation results for $P_{WTC}$ and $P_q$ for different $ϵ,\tilde{R}$ .

$ϵ,\tilde{R}$	$P_{\text{WTC}}$ (analytic)	$P_{\text{WTC}}$ (simulation)	$P_q$ (analytic)	$P_q$ (simulation)
1, 0.15	0.6770	0.6769	0.0220	0.0308
0.7778, 0.2	0.5958	0.5589	0.0412	0.0441
0.3737, 0.25	0.8519	0.8465	0.0907	0.0993

7.2. Dependence of $N_s(R)$ on $ϵ{\delta }_0$

In STA-DVD, $P_{\text{WTC}}$ , and consequently $P_q$ , depend on the application-dependent ϵ. Specifically, $P_q$ increases when ϵ decreases. For ${ϵ}_1>{ϵ}_2$ , this implies that $P_q({ϵ}_1)<P_q({ϵ}_2)$ . Even though more number of nodes get queried for $ϵ={ϵ}_2$ , it cannot be concluded that $N_s({ϵ}_1)<N_s({ϵ}_2)$ . This is because for $ϵ={ϵ}_2$ , the actual residual time available at each node to procure samples is low, even though the number of queried nodes is high. Therefore, we have the following.

Statement 4.

$N_s(R)$ must be a function of actual residual time $ϵ{\delta }_0$ .

Based on Statements 3 and 4, it can be concluded that $N_s(R)$ must be a function of $P_q$ and $ϵ{\delta }_0$ . We consider the following probabilistic estimate of the number of samples, $N_s(R)$ , that can be procured for a particular range R. Assuming that the WAP can have processing capabilities, this estimate is computed at the WAP to determine R

$\begin{array}{c}{N}_s\left(R\right)=P_q\times N\times \left(ϵ{\delta }_0-\frac{3R}{c}\right)\times f_s\end{array},$

(34)

where, $P_q$ is the probability that a node is queried (29), N is the number of nodes in the network, and $f_s$ is the sensor sampling rate. $N,f_s$ are assumed to be parameters provided to the WAP by the application. The factor

$\begin{array}{c}(ϵ{\delta }_0-\frac{3R}{c})=t_{s,\max }-(t+\frac{3R}{c})\end{array}$

(35)

corresponds to the time that would be available for the sensing application at a node located at the boundary of the range circle, where $(t+3R/c)$ is the time at which the node at the boundary of the range circle receives the query from the WAP. Thus, this factor represents the minimum time available at a node within the broadcast circle for sampling sensor data.

Statement 5.

For a given application-dependent ϵ value computed at the WAP, the R which maximizes $N_s(R)$ is chosen as the broadcast range by the querying WAP.

In this work, we assume a discrete set of broadcast ranges for the WAP to choose from. Figures 14 and 15 plot $N_s(R)$ with respect to $\tilde{R}$ (equivalently, $R=\tilde{R}d$ , where d is the cell radius) for SA-DVD and STA-DVD, respectively. The following inferences can be drawn from these figures.

Figure 14

$N_s(R)$ in SA-DVD with varying $\tilde{R}$ and ϵ.

Figure 15

$N_s(R)$ in STA-DVD with varying $\tilde{R}$ and ϵ.

• (i)

  In both SA-DVD and STA-DVD, it is observed that $N_s(R)$ increases as ϵ increases for a given $\tilde{R}$ . This is evident from the fact that, for a given R, the minimum time available for sensing, $(ϵ{\delta }_0-3R/c)$ , increases as ϵ increases. Thus, as ϵ increases, nodes can procure samples over a larger time window.

• (ii)

  In SA-DVD (Figure 14), even though the application-dependent $ϵ=0.7778,\hspace{0.17em}\hspace{0.17em}0.3737$ , the waiting time computation at nodes does not make use of these values. Figure 14 shows that in SA-DVD, the value of $\tilde{R}$ which yields the maximum $N_s(R)$ remains the same for different ϵ. This is because, for any R, $P_{\text{WTC}}$ (SA-DVD) (26) and consequently $P_q$ , are independent of ϵ in SA-DVD, and remain constant for varying ϵ. Therefore, for a given R, only a proportionate increase in $N_s(R)$ is observed when ϵ increases. In other words, the maximum $N_s(R)$ increases as ϵ increases, but the R which yields the maxima for different ϵ remains the same in SA-DVD.

• (iii)

  In STA-DVD (Figure 15), it is observed that the $\tilde{R}$ which yields the maximum $N_s(R)$ increases as ϵ decreases. This is because nodes tend to have higher ${\tilde{\tau }}_{ϵ}$ for low ϵ (Statement 2). Nodes can, therefore, satisfy WTC with the WAP for larger values of R (Implication (b) in Section 4.1). The high values of $P_{\text{WTC}}$ (STA-DVD) and $P_q$ observed for low ϵ, start deteriorating only when $\tilde{R}$ becomes very high in (25). However, when ϵ is high, nodes tend to have lower waiting times (Statement 2). Therefore, R must be small to ensure that $P_{\text{WTC}}$ does not deteriorate (Implication (a) in Section 4.1).

The R value chosen based on the maximization of $N_s(R)$ in (34) for different ϵ in STA-DVD and SA-DVD are given in Table 4 in Section 8. Here, the R value in meters belongs to the discrete set: $R:\{\mathrm{150,200,250,300,350}\}$ .

Table 4

Broadcast range R in meters for different schemes with varying ϵ.

ϵ	SA-DVD	STA-DVD	ADAPT-RW
0.7778	150 m	200 m	200 m
0.5758	150 m	250 m	250 m
0.3737	150 m	250 m	300 m

7.3. Variation of $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ With $\tilde{R}$

The variation of probability density function, $f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ with $\tilde{R}$ , in SA-DVD (where ϵ is assumed to be 1), and in STA-DVD for $ϵ=0.7778$ and $ϵ=0.3737$ , has been shown in Figures 16, 17 and 18, respectively. It can be inferred that in STA-DVD, for a given $\tilde{R}$ , the waiting time range increases as ϵ decreases, and consequently, the probability of nodes having higher waiting times also increases. As expected, it is observed that for a particular ϵ, the waiting time range also increases slightly with $\tilde{R}$ in both SA-DVD and STA-DVD.

Figure 16

$f_{\tilde{\tau }}(\tilde{\tau })$ in SA-DVD with varying $\tilde{R}$ .

Figure 17

$f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ in STA-DVD for $ϵ=0.7778$ and varying $\tilde{R}$ .

Figure 18

$f_{{\tilde{\tau }}_{ϵ}}({\tilde{\tau }}_{ϵ})$ in STA-DVD for $ϵ=0.3737$ and varying $\tilde{R}$ .

8. Simulation Results and Discussion

MATLAB has been used as the simulation tool in this work. We consider a circular area of radius $d=1000\hspace{0.17em}\text{m}$ with 1000 nodes whose locations, and velocities in the range 0.01–9.99 m/s, are drawn from the RWP steady state distribution [13] at sampling intervals of $T_s=5\hspace{0.17em}\text{s}$ . The pause time of nodes is uniformly distributed between 0–100 s. The battery rating is $3.3\hspace{0.17em}V\times 1100\hspace{0.17em}\text{mAh}$ , talktime is six hours and users recharge their batteries if the residual energy falls below 0.2  ×  battery rating. Initial residual energy of each cell phone is assumed to be different. Cell phone receiver sensitivity is chosen as $-80\hspace{0.17em}\text{dBm}$ , and duration of the application is $T_a=100\hspace{0.17em}\text{s}$ . The minimum broadcast range of the WAP, $R_{\min \hspace{0.17em}}=150\hspace{0.17em}\text{m}$ , and power consumed in listening is assumed to be $3.3\hspace{0.17em}V\times 15\hspace{0.17em}\text{mA}$ . A path-loss exponent of $n=2.7$ is considered for the log-normal fading model. 1000 different seeds were chosen to evaluate average performances. Confidence intervals of $95\text{\%}$ are further evaluated to study the robustness of the average performances. A cell-phone is considered to have the desired sensor with probability p.

ADAPT [15] is considered for the case of a single query over a single hop. In ADAPT, the WAP chooses the kth power level from a set of K power levels, where $k=\mathrm{mod}\hspace{0.17em}(K(1-ϵ),K+1)$ . In our simulations, we consider $K=5$ . Table 4 gives the R value determined by the WAP in ADAPT for different ϵ values. For fairness of comparison, we modify ADAPT by considering a uniformly distributed random waiting (RW) time [12] drawn from $[0,{\tau }_{ϵ,\max \hspace{0.17em}})$ , where ${\tau }_{ϵ,\max \hspace{0.17em}}$ is given by (11). For the current simulation setup, ${\tau }_{ϵ,\max \hspace{0.17em}}\approx 6.6$ . The proposed spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) protocol is compared with ADAPT-RW and spatially adaptive-distributed velocity-dependent (SA-DVD) protocol.

Simulations have been carried out by varying ϵ at the WAP, and p of nodes. The R value is chosen at the WAP for each ϵ, in both STA-DVD and SA-DVD, based on the discussion in Section 7 and is tabulated in Table 4. The performances of the protocols can be explained based on the effects of ϵ, which depicts the time constraints of the query, and the probability, p, of a node having the desired sensor. Note that in all the simulation plots, the $95\text{\%}$ confidence intervals obtained were very small (of the order of the marker size), hence demonstrating the robustness in the average performances obtained.

8.1. Effect of ϵ

As ϵ decreases, the waiting time of nodes in STA-DVD increases. Therefore, more number of nodes satisfies WTC with the WAP. Thus, as seen in Figure 19, the number of queried nodes $N_q$ increases with decrease in ϵ. Since waiting time in SA-DVD is independent of ϵ, $N_q$ remains the same for all ϵ. As seen in Figure 19, $N_q$ is lesser for SA-DVD than in STA-DVD, as the waiting time range of nodes is also correspondingly lesser. In ADAPT-RW, the broadcast range chosen by the WAP is time adaptive. A small ϵ corresponds to a higher broadcast range, and therefore to a high value of $P_R$ (27). The number of nodes satisfying WTC is also higher in ADAPT-RW, as the average normalized waiting time in RW ( $0.5{\tau }_{ϵ,\max \hspace{0.17em}}\approx 3.3$ ) is more than that in STA-DVD and SA-DVD (Table 1). Thus, due to high $P_R$ , and a large number of nodes satisfying WTC in ADAPT-RW, $P_q$ , and therefore $N_q$ , is maximum in ADAPT-RW, as seen in Figure 20. Note that the waiting time RW is not adaptive and is chosen from a uniform distribution.

Figure 19

Number of queried nodes ( $N_q$ ) with varying p and ϵ in STA-DVD and SA-DVD.

Figure 20

Number of queried nodes ( $N_q$ ) with varying p and ϵ in ADAPT-RW.

Since $N_q$ is larger in STA-DVD compared to SA-DVD, the energy dissipated in communication by nodes is also larger in STA-DVD, as seen in Figure 21. The communication energy dissipated is highest (Figure 22) in ADAPT-RW as its $N_q$ highest. The waiting time range in STA-DVD is greater than in SA-DVD. This manifests in the listening energy consumed by nodes which is greater in STA-DVD compared to SA-DVD, for all ϵ, as seen in Figure 23. Further, in STA-DVD, the listening energy consumed increases with decrease in ϵ, as the waiting time also increases. The listening energy remains a constant with varying ϵ in SA-DVD, as it adopts a waiting time independent of ϵ in SA-DVD. As seen in Figure 24, the listening energy is highest in ADAPT-RW as the average normalized waiting time of nodes ( $\approx 3.3$ ) is maximum in ADAPT-RW when compared to that of STA-DVD and SA-DVD.

Figure 21

Energy dissipated with varying p and ϵ in STA-DVD and SA-DVD.

Figure 22

Energy dissipated with varying p and ϵ in ADAPT-RW.

Figure 23

Listening Energy consumed with varying p and ϵ in STA-DVD and SA-DVD.

Figure 24

Listening Energy consumed with varying p and ϵ in ADAPT-RW.

As observed from Figures 26 and 25, respectively, the number of samples procured is maximum in ADAPT-RW, and is greater in STA-DVD, than in SA-DVD. This is because $N_q$ is maximum for ADAPT-RW, and $N_q$ is greater in STA-DVD than in SA-DVD. Further, in STA-DVD, SA-DVD and ADAPT-RW, the number of samples procured is higher for large ϵ values. This is because, for a constant sensor sampling rate, $f_s$ , the sensing time window available at nodes in all protocols, is largest for the largest application-dependent ϵ value. This is despite the fact that $N_q$ is smallest when ϵ is largest.

Figure 25

Number of samples ( $N_s$ ) with varying p and ϵ in STA-DVD and SA-DVD.

Figure 26

Number of samples ( $N_s$ ) with varying p and ϵ in ADAPT-RW.

8.2. Effect of p

The number of nodes queried and the number of samples procured increase linearly with p for all schemes as seen in Figures 19, 20, 25, and 26. The energy dissipated and the listening energy consumed by nodes also correspondingly increase with p, as the number of queried nodes increase with p. This is observed in Figures 21, 22, 23, and 24.

8.3. Effect of σ

We assume that cell phones are equipped with GPS and velocities are computed from consecutive location measurements. Since location and velocity measurements are prone to error, we consider the following Gaussian perturbation model. If γ in general represents either location or velocity, then the measured γ for node i is ${\gamma }_m(i)={\gamma }_a(i)+\sigma \kappa (i){\gamma }_a(i)$ , where ${\gamma }_a(i)$ is the actual value of γ, σ is the perturbation fraction and $\kappa (i)~N(\mathrm{0,1})$ . For simplicity, we assume the same value of σ for location and velocity perturbations, while κ is node and parameter-specific.

The number of nodes queried and hence the number of samples procured in all schemes decreases for $\sigma >0$ , as seen in Figures 27, 28, 33, and 34, respectively. This is because of RTS-CTS packet losses due to erroneous location and velocity estimates. Therefore, the total energy dissipated and the listening energy consumed by the fewer number of nodes involved in the application also correspondingly decrease. This can be inferred from Figures 29, 30, 31, and 32.

Figure 27

Number of queried nodes ( $N_q$ ) with varying p and σ for $ϵ=0.7778$ in STA-DVD and SA-DVD.

Figure 28

Number of queried nodes ( $N_q$ ) with varying p and σ for $ϵ=0.7778$ in ADAPT-RW.

Figure 29

Energy dissipated with varying p and σ for $ϵ=0.7778$ in STA-DVD and SA-DVD.

Figure 30

Energy dissipated with varying p and σ for $ϵ=0.7778$ in ADAPT-RW.

Figure 31

Listening energy consumed with varying p and σ for $ϵ=0.7778$ in STA-DVD and SA-DVD.

Figure 32

Listening energy consumed with varying p and σ for $ϵ=0.7778$ in ADAPT-RW.

Figure 33

Number of samples ( $N_s$ ) with varying p and σ for $ϵ=0.7778$ in STA-DVD and $SA-DVD$ .

Figure 34

Number of samples ( $N_s$ ) with varying p and σ for $ϵ=0.7778$ in ADAPT-RW.

Based on the effect of ϵ, p, and σ, it can be concluded that, incorporating time adaptiveness to the waiting time of nodes enhances the performance for applications that involve time constraints. Although the cost in terms of energy dissipated and listening energy increases, the proposed STA-DVD scheme has a significant performance improvement especially when the residual time is high and more nodes have the desired sensor. Further, for critical applications with very low residual time (small ϵ), or which involve sensors that users generally do not possess (small p), the proposed STA-DVD scheme still exhibits a better performance than SA-DVD at comparable energy costs. The ADAPT-RW scheme has the best performance in terms of number of samples obtained. However, the communication energy and listening energy consumed by resource-constrained cell phones in ADAPT-RW are significantly higher than in STA-DVD and SA-DVD.

Table 4 shows a comparison of the broadcast ranges in SA-DVD and STA-DVD at which $N_s(R)$ (34) is maximum as well as the ranges corresponding to the temporally adaptive broadcast power levels chosen in ADAPT-RW. It is observed that the range remains the same for all ϵ values in SA-DVD, where no temporal waiting time adaptation is performed. Further, for $ϵ=0.3737$ ; that is, when residual time is small, ADAPT-RW chooses a range of 300 m compared to 250 m chosen in STA-DVD. Moreover, for $ϵ=0.3737$ , Figures 25 and 26 show that SA-DVD procures more number of samples compared to ADAPT-RW at much lower energy costs (Figures 21, 23, 22, 24). The results clearly demonstrate that the proposed STA-DVD protocol is suitable for the query dissemination application at a higher energy efficiency compared to ADAPT-RW, especially for applications with low residual times.

9. Some Recent Works in Cell Phone Based Sensor Networks

Research and development, academic, industrial, and governmental partnerships have recently recognized the enormous potential of cell phone-based sensor networks in urban, mobile, participatory, or people-centric sensing applications [1, 3, 4, 16, 22–25]. In addition to protocol design, various challenges involved in the design and development of these networks have been identified in [1, 26–30]. Here, we have attempted to include as many references as we can on these networks. In Accra, Ghana, pollution data was captured, throughout the day by GPS-supported carbon monoxide sensor kits carried by taxi drivers and students [31–33]. Ten other cases where cell phones contribute to assistance in the areas of public health, security and environmental conservation have been presented in [31]. The urban sensing group at UCLA, [34], works on a large number of areas like public health, community cultural expression and well-being, environmental monitoring and urban planning. The Mobile Millennium project uses positioning data from GPS-enabled cell phones mounted on vehicles, to get real-time traffic information [6]. In [35], a system, UbiFit garden, has been developed for people to monitor lifestyle and to encourage physical activity. In [5], projects ranging from personal sensing systems to sensing terrain are under research, while [36] studies the realtime movement patterns in Rome. The Campaignr framework, [37], was proposed to enable users to upload sensor data, yet concealing the complexities of the underlying embedded mobile phone environment. Tackling security-related issues is considered in [38], while [39] proposes a continuous queryprocessing system for intermittently connected mobile sensor networks. Handling of spatio-temporal queries efficiently from the sensors is described in [40]. Data inferencing using cooperative techniques to overcome device heterogeneity is considered in [41].

10. Conclusions

In this paper, a short-range communications based Cell phone Sensor Network (CpSN) had been considered for a query dissemination application. The main contribution of this paper was the development of an energy-efficient, waiting time-based scheme, where the waiting time is adapted based on the temporal specifications of the query for a random waypoint distribution of cell phone users. The proposed spatio-temporally adaptive-distributed velocity-dependent (STA-DVD) waiting time based scheme outperforms a spatially adaptive-distributed velocity-dependent (SA-DVD) waiting time-based scheme in terms of number of samples procured from the network at a cost of slightly higher energy dissipation. However, the proposed STA-DVD protocol is especially suitable for applications where the residual time is very low and the procurement of samples becomes a priority. The existing temporally adaptive scheme, ADAPT-RW, caters to the temporal specifications by varying the range of the querying WAP. Our results show that the proposed STA-DVD scheme has a significantly higher energy efficiency than ADAPT-RW. STA-DVD has a slightly poorer performance (in terms of number of samples procured) than ADAPT-RW for high residual times, and a better performance (in terms of number of samples procured) than ADAPT-RW, for low residual times. Hence, the proposed STA-DVD scheme is an energy-efficient viable solution for time-constrained query dissemination in CpSN.