Reliable Data Storage in Heterogeneous Wireless Sensor Networks by Jointly Optimizing Routing and Storage Node Deployment

To resolve the JUST-Approx problem (and thus to address the JUST problem with approximation optimality), we design a CTMC ${\{F(t)\}}_{t⩾0}$ to drive the adaptive deployment of the storage nodes and the corresponding routing scheme, where $t$ denotes time and $F(t)\in ℱ$ denotes the storage node deployment adopted at time $t$ . In the CTMC, state transitions (i.e., storage node redeployments) continuously happen at any point in time and are characterized by transition rates. We assume that, any two of the states have a transition link if and only if the two states have only one storage node deployed at different sites. Note that this assumption does not compromise the reachability between the states and thus the irreducibility of the Markov chain.

The CTMC ${\{F(t)\}}_{t⩾0}$ has a unique stationary distribution, as it has finite states and is of irreducibility. In the Markov approximation framework, we design a time-reversible CTMC ${\{F(t)\}}_{t⩾0}$ , such that the following detailed balance equation holds for the stationary distribution, i.e.,

(18) $$p_f^{*}{q}_{f,f^{+}}=p_{f^{+}}^{*}{q}_{f^{+},f}$$

where $q_{f,f^{+}}$ and $q_{f^{+},f}$ denote the transition rates from $f$ to $f^{+}$ and the one from $f^{+}$ to $f$ , respectively. In this paper, we define the transition rates $q_{f,f^{+}}$ as

(19) $$q_{f,f^{+}}=\delta \frac{\exp (-\theta c_{f^{+}})}{\exp (-\theta c_f)+\exp (-\theta c_{f^{+}})}$$

where $\delta$ is a constant. Recalling the definition of $p_f^{*}$ (for $\forall f\in ℱ$ ) in Eq. ( 17 ), the above definition of $q_{f,f^{+}}$ apparently satisfies the balance in Eq. ( 18 ).

The CTMC ${\{F(t)\}}_{t⩾0}$ can be implemented based on the two propositions in Ref. [ 24 ], as shown in the following:

Proposition 1 For each state $f\in ℱ$ , the sojourn time is a random variable obeying an exponential distribution parameterized by

(20) $$v_f={\displaystyle \underset{f^{\prime }\in ℱ(f)}{\sum }}{q}_{f,f^{\prime }}=$$ $$\delta {\displaystyle \underset{f^{\prime }\in ℱ(f)}{\sum }}{\displaystyle \frac{\exp (-\theta c_{f^{\prime }})}{\exp (-\theta c_f)+\exp (-\theta c_{f^{\prime }})}}$$

where $ℱ(f)$ denotes the set of the states adjacent to $f$ .

Proposition 2 The transition probability from $f\in ℱ$ to $f^{+}\in ℱ(f)$ is defined as

(21) $$p_{f,f^{+}}=q_{f,f^{+}}/v_f$$

if considering the discrete-time counterpart of the CTMC.

According to the above propositions, the optimality of the CTMC-driven method can be explained from the following two folds: On one hand, we adopt the storage node deployments that have lower costs for a longer time; on the other hand, it is more likely to move to the lower-cost storage node deployment in each state transition.

Motivated by the two propositions, we can implement a CTMC to drive the adaptive deployment of the storage nodes by repeating the following steps: (1) Supposing $f$ denotes the current storage node deployment, we set up a countdown timer initialized by an exponential random value $\Delta t\sim \mathrm{Exponential}(v_f)$ ; (2) once the timer expires, we transit to a new storage node deployment $f^{+}\in ℱ(f)$ according to the transition probabilities defined in Eq. ( 19 ). Although we can achieve the optimal distribution ${\{p_f^{*}\}}_{f\in ℱ}$ by repeating the above two steps in a long run, this approach entails some central infrastructures.

We propose an algorithm (see Algorithm 2) to implement the CTMC in a distributed manner. By default, we initially deploy the storage nodes in a randomized fashion (as shown in Line 2). The lifetime of the sensor network can be divided into a sequence of epochs, and a new epoch begins when some storage nodes are redeployed. In each epoch, we first compute a routing strategy according to the current storage node deployment $f$ by the ${\mu }_i$ -NN policy (see Line 2). In every epoch, each storage node $s_j$ generates an exponential random variable $\Delta t_j\sim \mathrm{Exponential}(v_j)$ , where

$$v_j=\underset{f^{\prime }\in {ℱ}_j(f)}{\sum }{q}_{f,f^{\prime }},$$

with ${ℱ}_j(f)$ representing the subset of feasible storage node deployments where only $s_j$ is placed at different sites from the one in $f$ (see Line 2). Each storage node $s_j$ then sets up a countdown timer initialized by $\Delta t_j$ (see Line 2). We assume $j^{*}=\arg {\min }_j{\{\Delta t_j\}}_{j=1,\mathrm{\dots },|𝒮|}$ , and storage node $s_{j^{*}}$ is the one whose timer expires first. When the timer expires, $s_{j^{*}}$ broadcasts a notification message, and the other storage nodes that received the message (before their timers expire) stop counting down. As shown in Line 8, we redeploy $s_{j^{*}}$ according to the probability distribution:

(22) $$p_{f,f^{+}}=q_{f,f^{+}}/v_{j^{*}},\forall f^{+}\in {ℱ}_{j^{*}}(f)$$

The complexity of the above algorithm mainly stems from computing $c_{f^{+}}$ , i.e., calculating the routing strategy and corresponding cost. The shortest paths from the sensor nodes to the sites and the induced cost can be computed by state-of-the-art polynomial-time algorithms (e.g., Dijkstra’s method with a time complexity of $O({|𝒩|}^2)$ ). As the sensor nodes and the sites where we deploy the storage nodes are fixed, the data delivery paths and their costs can be preloaded in the storage nodes, especially as the storage nodes usually have sufficient memory space. When a storage node is redeployed, it notifies the other ones of its new position by broadcasting $O(\log |𝒰|)$ -length notification messages, such that all the other storage nodes can locally compute $c_{f^{+}}$ . Moreover, the storage nodes can forward the notifications to the sensor nodes by piggybacking the received new storage node deployment in the acknowledgments to the data deliveries. For each sensor node, once the notification is received from the storage nodes, the sensor node can quickly compute the cost of delivering a data unit in the redeployed storage node and then update the routing strategy according to the ${\mu }_i$ -NN policy.

In the above implementation, each of the storage nodes only needs to set up a local timer. One question is, does such a distributed implementation realize CTMC ${\{ℱ(t)\}}_{t⩾0}$ by respecting Propositions 1 and 21? To answer this question, we present the following theorem, which implies that relying on a set of local timers in a distributed manner instead of a centralized one does not compromise the optimality of ${\{ℱ(t)\}}_{t⩾0}$ in solving our JUST-Approx problem.

Theorem 2 In Algorithm 1, the sojourn time for each state $f$ is a random variable following an exponential distribution parameterized by rate $v_f$ in Eq. ( 20 ), and the transition probability from $f$ to $f^{+}$ ( $f^{+}\in ℱ(f)$ ) is $p_{f,f^{+}}=q_{f,f^{+}}/v_f$ (see Eq. ( 21 )).

Proof For any storage node deployment $f\in ℱ$ , the sojourn time $\Delta t(f)$ can be defined as

$$\Delta t(f)=\min {\{\Delta t_j\}}_{j=1,\mathrm{\dots },|𝒮|},$$

as shown in Algorithm 1. As $\Delta t_j\sim \mathrm{Exponential}(v_j)$ for $\forall j$ , we have $\Delta t(f)\sim \mathrm{Exponential}({\sum }_j{v}_j)$ for $\forall f\in ℱ$ . In another word, $\Delta t(f)$ is an exponentially distributed random variable with the rate defined by ${\sum }_j{v}_j={\sum }_j{\sum }_{f^{\prime }\in {ℱ}_j(f)}{q}_{f,f^{\prime }}$ . Also, since ${\bigcup }_j{ℱ}_j(f)=$ $ℱ/\{f\}$ and ${\bigcap }_j{ℱ}_j(f)=\mathrm{\varnothing }$ , we have ${\sum }_j{v}_j=$ ${\sum }_{f^{\prime }\ne f}{q}_{f,f^{\prime }}=v_f$ . Therefore, for $\forall f\in ℱ$ ,

$$\Delta t(f)\sim \mathrm{Exponential}(v_f).$$

For $\forall j^{*}\in \{1,\mathrm{\dots },|𝒮|\}$ , the probability that $s_{j^{*}}$ is the redeployed storage node with $\Delta t(f)=\Delta t_{j^{*}}$ can be calculated as $v_{j^{*}}/{\sum }_j{v}_j$ . Let ${ℱ}_{j^{*}}(f)$ denote the set of the storage node deployments with $s_{j^{*}}$ deployed at different sites from the one in $f$ . Then, for $\forall f^{+}\in$ ${ℱ}_{j^{*}}(f)$ , the probability that we have the transition $f\to f^{+}$ (given that $s_{j^{*}}$ has to be redeployed) can be defined by $q_{f,f^{+}}/v_{j^{*}}$ (see Eq. ( 22 )). Therefore, $p_{f,f^{+}}={\displaystyle \frac{v_{j^{*}}}{{\sum }_j{v}_j}}\cdot {\displaystyle \frac{q_{f,f^{+}}}{v_{j^{*}}}}={\displaystyle \frac{q_{f,f^{+}}}{v_f}}$ holds for $\forall f^{+}\in ℱ(f)$ .