Sage Journals: Discover world-class research

Abstract

We propose to develop Wireless Sensor Networks with Mobile Sinks (MSSN), under high sensor node density, where multiple sensor nodes need to share one single communication channel in the node-to-sink transmission. By exploiting the tradeoff between the successful information retrieval probability and the nodes energy consumption, a number of multiple nodes transmission scheduling algorithms are proposed. Both optimal and suboptimal algorithms, which exhibit exponential and linear complexity respectively, are discussed under the desired application. Computer simulations show that suboptimal algorithms perform nearly as good as the optimal one. The study leads to the cross-layer Wireless Link layer design for MSSN.

Keywords

Wireless Sensor Networks Transmission Scheduling Multiple Access Wireless Link Layer Energy Consumption

1. Introduction

The unique nature of wireless sensor networks, which are resource-limited and application-specific, requires new approaches in the system design. Recently [1], we proposed to develop Sensor Networks with Mobile Sinks (MSSN) for two application areas, environment monitoring systems with high latency tolerance [19], and intelligent-space [17]. This new architecture features very high energy-efficiency, because multi-hop transmissions of high volume data over the network is converted to single-hop transmissions. Additional advantages of MSSN include: infrastructure free, high security, and ease of implementation. In [1], we discussed the transmission scheduling algorithm TSA-MSSN in a sparsely deploying network setup, where it is assumed that only one sensor node is communicating with the mobile sink on a given channel.

However, when the density of sensor networks increases, multiple nodes can be within the transmission range to the sink, and the assumption of a sparsely deploying setup no longer holds. Consider for example the application of micro spies [5]. A micro spy is a micro aircraft with the size of less than six inches. For the purpose of battlefield observation and strategic reconnaissance, sensor networks can be deployed in a remote place with limited wireless infrastructures. A micro spy can, on the other hand, act as a mobile sink, which flies over the sensor deployed region and delivers the collected information back to the commander. In the communication setup, a number of sensor nodes need to send packets to the micro spy simultaneously, because of the importance of the desired information. Also, it may be risky to have the micro spies stay in the air for too long a time, hence, the communication time slots available are limited.

The wireless architecture in this scenario is centralized, which is analogous to cellular networks, star network setup in IEEE 802.15.4 [6], and Point Coordination Function (PCF) in IEEE 802.11 [7]. Although there is a large number of classical multiple access schemes [15] available, such as TDMA, FDMA, CDMA, etc., all of them assume that multiple wireless channels are available for node-to-sink communication. In our case, the sink can assign one such distinctive channels to any individual node. The TSA-MSSN, proposed in [1], can then operate on different channels respectively. However, when the number of nodes exceeds the number of channels, multiple nodes will need to share one channel. Thus, multiple nodes scheduling algorithms are needed to ensure the Quality of Service (QoS) of the wireless network.

Under different types of wireless networks, there are numerous works investigating the desired scheduling problem. Under cellular networks, from an information theoretic approach, [8] showed that, to maximize the total uplink capacity, it is sufficient to have only the user with the strongest channel to the base station transmit at any given time. Such a power control scheme is known as multiuser diversity, which is also extended to downlink channels in [9], and other forms of channel capacity such as delay-limited capacity [10] and outage capacity [11]. Although strategies in [8] are optimal in the sense of capacity, in the service layer implementations, more QoS factors should be considered, such as fairness, delay, and connection admission control (CAC). Recent references on this topic can be found in CDMA cellular networks [12] and IEEE 802.11 enabled home networking [13]. In the area of sensor networks, SENMA [20] (Sensor Networks with Mobile Agents) studied the sensor network topology similar to MSSN, and proposed distributed random access scheduling. However, SENMA assumes a simple reachback sensor network, which differentiates it from the proposed MSSN.

Compared to the existing works, the MSSN is distinctive for the following reasons: In MSSN, the objective of scheduling algorithms is to retrieve integrated/compressed information [14] stored on sensor nodes with the minimum energy consumption. Combined with the mobility of the sink, this guideline, [1], makes the system design different from the conventional wireless networks. More specifically, in the MSSN transmission scheduling, we exploit the tradeoff between the successful information retrieval credit and the nodes energy consumption cost, under the latency limitations imposed by the sink mobility. Instead, in conventional wireless networks, “throughput” is usually emphasized, which is the number of retrived packets per second.

Next, we discuss the scenario where multiple sensor nodes are sharing one communication channel in sending information to the mobile sink which is travelling through the deployed sensor networks. The system description is provided in Section II. The proposed optimal multiple nodes transmission scheduling algorithm (MTSA-MSSN) is described in Section III. The optimal MTSA-MSSN has the complexity which grows up exponentially with the number of nodes N. Thus, in Section IV, we propose suboptimal algorithms with the complexity as low as O(N). A comparison and validation of the suboptimal algorithms performance are given in Section V, by means of computer simulations. Discussions and concluding remarks are given in Section VI and VII, respectively.

2. System Description

2.1. Concepts and Assumptions

The concept of the scheduling design is to reduce the sensor nodes energy consumption, in the process of information retrieval, by exploiting the sink mobility. Utilizing the higher energy, computing, and storage resources at the sink, the proposed scheduling algorithms are centralized, and executed solely at the sink. The problem of finding the optimal scheduling policy is formulated as a Markov Decision Process (MDP), and solved in the framework of dynamic programming [22]. Essentially, the tradeoff between the successful information retrieval credit and the sensor nodes energy consumption cost is explored.

Let N denote the number of nodes sharing one specific communication channel. Assume that the location and the number of residual packets of every node are known at the sink, by a registration procedure. More specifically, the registration can be conducted on a separate control channel, where the nodes send the registration, i.e, the location and the packet number, upon the detection of the sink arrival, by means of carrier sensing multiple access (CSMA). The sink acknowledges the registration by assigning the node a generated identification number.

At the current time slot i₀, the problem to formulate is how the sink decides the transmission strategy, i.e., which one of the N nodes is going to transmit and what is the transmission power. The scheduling algorithm is executed at the beginning of every communication time slot. One time slot is composed of the transmission of two different packets in sequence, which are the acknowledgement (ACK) packet from the sink, and the data packet from one of the sensor nodes, respectively. The obtained scheduling strategy can be piggybacked on the ACK packet broadcasted by the sink to the N associated sensor nodes. The ACK packet, on the other hand, also serves to acknowledge successful or failed data transmission in the previous time slot. It is assumed that the lost data packets will be retransmitted.

Assume that the sink has an estimation of its current mobility, which can be obtained from the Global Positioning System (GPS). We do not assume that the future mobility pattern is available at the sink. Instead, we make two approximations:

No new node is admitted to the channel until all N nodes have finished the transmission;

The mobility of the sink is maintained constant in future time slots.

Both assumptions are realistic, because the scheduling algorithm is run at the beginning of every time slot, where both the nodes and the sink mobility information are updated.

In the scheduling design, we do not consider the possibility of new data arrival at sensor nodes, in the procedure of information retrieval. The sensor nodes is dissociated with the sink, whenever all the data packets have been retrieved.

2.2. System State Vector Ě(i₀)

Let Range denote the communication range of the sensor node. It is assumed that Range is the same for all nodes. Let {L₁,….L_N} denote the location of the N sensor nodes respectively, which are fixed throughout the transmission. At the current time slot i₀, let ${K_{n} (i_{0}) | n = 1 \dots N}$ denote the number of residual packets awaiting for transmission at node n. The location, direction, and the speed of the sink are denoted by L_s(i₀), θ_s(i₀), ν_s(i₀), respectively. Then, the current system state is composed of these 2N + 3 elements,

E (i_{0}) = {L_{s} (i_{0}), θ_{s} (i_{0}), v_{s} (i_{0}), L_{1}, \dots, L_{N}, K_{1} (i_{0}), \dots, K_{N} (i_{0})} .

(1)

Let D_n(i₀) denote the distance between the sink and the sensor node n, n = 1…N,

D_{n} (i_{0}) = ∥ L_{s} (i_{0}) - L_{n} ∥ .

(2)

The communication channel gain for the node n can be modeled as [16].

G_{n} (i_{0}) = 10 \cdot log (A) - 10 \cdot log (D_{n} (i_{0})) + (d B),

(3)

where A is a constant decided by the antenna gain; β is the path loss exponent decided by the propagation environment, e.g. β = 2 for free space; and ξ is a random variable under normal distribution $N (0, σ_{ξ}^{2})$ , indicating the shadowing effect. $σ_{ξ}^{2}$ denotes the variance of ξ.

Let T_n(i₀) denote the estimated transmission time slots available for node n, n = 1…N. Since the sink is assumed to have constant mobility when passing through all the N circular regions, centered at {L_n|n = 1…N} with the radius Range, there is,

T_{n} (i_{0}) = ⌊ \frac{∥ L_{s} (i_{0}) - L_{s_o u t, n} ∥}{v_{s} (i_{0}) \cdot Δ t} ⌋,

(4)

where $Δ t = \frac{F_{d} + F_{b}}{R}$ is the time duration of one slot. F_d and F_b are the size of the data and ACK packets respectively. R is the transmission data rate. L_{s_out,n} is illustrated in Fig. 1, and is defined as the point at which the sink goes out of the communication range of sensor node n. (See Appendix I for a mathematical definition.)

Let,

T (i_{0}) = max_{n = 1 \dots N} {T_{n} (i_{0})} .

(5)

Then, the vector of estimated states can be defined as,

\hat{E} (i_{0}) = {\hat{E} (i_{0}), \hat{E} (i_{0} + 1), \dots, \hat{E} (i_{0} + T (i_{0}) + 1)},

(6)

where Ě(i₀) is known as,

E (i_{0}) = E (i_{0}),

(7)

and,

{\begin{cases} \hat{L_{s}} (i_{0} + j) = L_{s} (i_{0}) + j \cdot v_{s} \cdot Δ t \cdot [cos (θ_{s}), sin (θ_{s})]; \\ {\hat{θ}}_{s} (i_{0} + j) = θ_{s} (i_{0}) = θ_{s}; \\ {\hat{v}}_{s} (i_{0} + j) = v_{s} (i_{0}) = v_{s}; \\ j = 1 \dots T (i_{0}) + 1. \end{cases}

(8)

Figure 1

The mobile sink passes through the circular region centered on L_n.

Thus, the only variable parameters of each estimated state {Ě(i), i₀ < i  i₀ + T(i₀) + 1} are ${{\hat{K}}_{n} (i)}$ , which ranges from 0 to K_n(i₀). The vector Ě(i) (i₀ < i  i₀ + T(i₀) + 1) can then take $\prod_{n = 1}^{N} (K_{n} (i_{0}) + 1)$ discrete values.

2.3. Markov Chain Model of Ě(i₀)

The transmission strategy S(i) at time slot i, where i₀  i  i₀ + T(i₀), is decided by two parameters,

S (i) = {η (i) \cdot P_{t} (i)},

(9)

where η(i) ∊ {1…N} denotes the ID of the transmitting node in time slot i. P_t(i) is, on the other hand, the transmission power at the sensor node η(i). Note that P_t(i) can be 0 if all N nodes are forced to sleep. We assume the discrete levels transmission power, and that the number of optional levels is Sizeof {P_t}. Given Ě(i) and S(i), Ě(i + 1) is not related to any previous states before i. Thus, {Ě(i)} can be modelled as a Markov chain in time domain, that is,

\begin{aligned} P r o b & (\hat{E} (i + 1) ∣ \hat{E} (i_{0}), \dots, \hat{E} (i), S (i_{0}) \dots, S (i)) \\ = P r o b (\hat{E} (i + 1) ∣ \hat{E} (i), P_{t} (i), η (i)) . \end{aligned}

(10)

The state transferring probability function can be written as,

\begin{aligned} P r o b (\hat{E} (i + 1) ∣ \hat{E} (i), P_{t} (i), η (i)) = \\ {\begin{cases} P \hat{E} R (i), & {\hat{K}}_{n} (i + 1) = {\hat{K}}_{n} (i), \forall n = 1 \dots N; \\ 1 - P \hat{E} R (i), & {\hat{K}}_{η (i)} (i + 1) = {\hat{K}}_{η (i)} (i) - 1, \\ {\hat{K}}_{n} (i + 1) = {\hat{K}}_{n} (i), \forall n \neq η (i); \\ 0, & o t h e r s; \end{cases} \end{aligned}

(11)

where PĚR(i) is the packet error rate of transmission in time slot i. Consider a BPSK modulated uncoded data packet. And assume that the sink is unaware of the shadowing effect ξ, i.e. in the channel model Eq. (3). Then, the PĚR(i) can be written as, [15],

P E R (i) = 1 - {(1 - Q (\sqrt{\frac{2 P_{i} (i) \cdot Λ}{σ_{n}^{2} \cdot {\hat{D}}_{η (i)} (i)^{β}}}))}^{F_{d}},

(12)

where $σ_{n}^{2}$ is the noise power. And $Q (x) = \frac{1}{\sqrt{π}} \cdot \int_{\frac{x}{\sqrt{2}}}^{\infty} e^{- t^{2}} d t$ .

In the definition of the transmission strategy S(i), Eq. (9), we preclude the possibility of multiple nodes transmitting simultaneously in one time slot. Although the scenario is not physically infeasible, it will require highly sophisticated coding schemes on sensor nodes, which is generally impractical due to the limited hardware resource on one single sensor node. Instead, by adopting the definition in Eq. (9), we reduce the size of strategy space from $S i z e o f {P_{t}}^{N}$ to $S i z e o f {P_{t}} \cdot N$ Furthermore, from an energy conservation perspective, it is also preferable to not allow multiple nodes transmitting simultaneously on one channel. The proof is provided in Appendix II.

3. Optimal MTSA-MSSN Strategy

At current time i₀, the objective of the MTSA-MSSN is to decide the optimal strategy S(i₀) so as to maximize the probability of successful transmission while minimizing the energy consumption. However, these two goals can not be achieved simultaneously. The optimal strategy, $S^{*} (E (i_{0})) = {η^{*} (E (i_{0})), P_{t}^{*} (E (i_{0}))$ , is searched by maximizing a utility function, $J (S (i_{0}), \hat{E} (i_{0}))$ ,

S^{*} (E (i_{0})) = \underset{S (i_{0})}{arg max} {J (S (i_{0}), \hat{E} (i_{0}))} .

(13)

For i₀  i  i₀ + T(i₀), we define,

J (S (i), \hat{E} (i)) = J_{m} (S (i), \hat{E} (i)) - λ \cdot J_{c} (S (i)) .

(14)

In Eq. (14), J_m (S(i), Ě(i)) denotes the figure of credit, which is the expected achievable utility by adopting S(i) at Ě(i). J_c (S(i)), on the other hand, is the figure of cost, which is decided by the energy consumption. λ is a coefficient deciding the tradeoff between the two.

Since {Ě(i)} is modeled as a Markov chain, there is:

\begin{aligned} J_{m} (S (i), \hat{E} (i)) = \\ Σ_{\hat{E} (i + 1)} {max}_{S (i + 1)} {J (S (i + 1), \hat{E} (i + 1))} . \\ P r o b (\hat{E} (i + 1) ∣ \hat{E} (i), P_{t} (i), η (i)), \end{aligned}

(15)

and,

J_{c} (S (i)) = \frac{1}{max {P_{t}}} \cdot P_{t} (i) .

(16)

where max{P_t} is the maximum available RF (Radio Frequency) transmission power and acts as a normalization factor in J_c.

Thus, by combining Eq.(14,15,16), the function J can be written recursively as,

\begin{aligned} J (S (i), \hat{E} (i)) = J (η (i), P_{t} (i), \hat{E} (i)) = \\ Σ_{\hat{E} (i + 1)} {max}_{S (i + 1)} {J (S (i + 1), \hat{E} (i + 1))}, \\ P r o b (\hat{E} (i + 1) ∣ \hat{E} (i), P_{t} (i), η (i)) - \frac{λ}{max {P_{t}}} \cdot P_{t} (i) . \end{aligned}

(17)

At the final state of the algorithm, i = i₀ + T(i₀) + 1, the utility function is decided only by Ě(i₀ + T(i₀) + 1), that is,

J (S (i_{0} + T (i_{0} + 1), \hat{E} (i_{0} + T (i_{0}) + 1)) = J (\hat{E} (i_{0} + T (i_{0}) + 1)) .

(18)

The definition of J (Ě(i₀ + T(i₀) + 1)) is, however, application dependent. For example, assuming that each packet is equally credited, say “1”, then it can be defined as,

J (\hat{E} (i_{0} + T (i_{0}) + 1)) = \sum_{n = 1}^{N} {K_{n} (i_{0}) - {\hat{K}}_{n} (i_{0} + T (i_{0}) + 1)} .

(19)

If we set λ = 1 in Eq. (14), Eq. (19) suggests that the cost of a maximal power transmission time slot equal to the credit of successfully transmitting one packet.

As such, the optimal MTSA-MSSN can be solved by means of dynamic programming, and is summarized in Table 1. Compared with the TSA-MSSN [1], the size of strategy space in MTSA-MSSN has increased N times, from $S i z e o f {P_{t}} to N \cdot S i z e o f {P_{t}}$ .

Table 1

Optimal MTSA-MSSN Algorithm

Moreover, the size of the state space $\hat{E} (i) is \prod_{n = 1}^{N} (K_{n} (i_{0}) + 1)$ . Hence, Eq. (17) is executed $O {N \cdot S i z e o f {P_{t}} \cdot \prod_{n = 1}^{N} (K_{n} (i_{0}) + 1)}$ times in any one iteration of i. The TSA-MSSN, in this framework, becomes a special case of MTSA-MSSN, where N = 1. Since there are T(i₀) iterations, the complexity of optimal algorithm is,

\begin{aligned} C (O p t i m a l) & = O {N \cdot S i z e o f {P_{t}} \cdot T (i_{0}) \cdot \prod_{n = 1}^{N} (K_{n} (i_{0}) + 1)} \\ = O (e^{N}) . \end{aligned}

(20)

Due to the fact that $\prod_{n = 1}^{N} (K_{n} (i_{0}) + 1)$ (the number of discrete states) increases exponentially with the number of nodes N, the complexity of the optimal algorithm also increases at least exponentially with N.

Moreover, if a continuous power level control is implemented, the concavity of the utility function is only proved under the condition N = 1, [1]. It is unclear whether a computational simple way can be found for the optimization in Eq. (17), when N > 1.

4. Suboptimal Algorithms

Since the optimal algorithm has the complexity, C(Optimal) given by Eq. (20), which increases exponentially with the number of nodes N, it is infeasible for implementation on a mobile sink, such as a “micro spy.” In developing suboptimal algorithms, the idea is to run the TSA-MSSN (i.e. N = 1) algorithm individually for each node n, and combine the N individual strategies. We denote this suboptimal multiple-access transmission strategy as S^s(i). As presented in [1], the complexity of TSA-MSSN can be reduced to O(1), when a feasible storage capability is available on the sink. Then, the complexity of the proposed suboptimal algorithms, requiring the same sized storage capability, equals N times the complexity of TSA-MSSN. Thus,

C (S u b o p t i m a l) = O (N) .

(21)

4.1. Preprocessing: TSA-MSSN Runs

We outline the preprocessing procedure of TSA-MSSN for the integrity of this paper. Assume the current time slot is i₀. Let P_t,n(i) denote the strategy (transmission power) of TSA-MSSN run on node n, and let Ě_n(i) denote the estimated system state on node n, which is,

\begin{aligned} {\hat{E}}_{n} (i) = {{\hat{L}}_{s} (i), {\hat{θ}}_{s} (i), {\hat{v}}_{s} (i), L_{n}, {\hat{K}}_{n} (i)}, \\ i = i_{0}, \dots, i_{0} + T_{n} (i_{0}) + 1. \end{aligned}

(22)

The definition of ${\hat{L}}_{s} (i), {\hat{θ}}_{s} (i)$ , and ${\hat{v}}_{s} (i)$ follows from Eq. (8).

The TSA-MSSN searches the maximum of a utility function $J (P_{t, n} (i_{0}), {\hat{E}}_{n} (i_{0}))$ in obtaining the optimal transmission power decision, $P_{t, n}^{*} (E_{n} (i_{0}))$ ,

P_{t, n}^{*} (E_{n} (i_{0})) = \underset{P_{t, n} (i_{0})}{arg max} {J (P_{t, n} (i_{0}), {\hat{E}}_{n} (i_{0}))} .

(23)

The utility function for each node n, J_n, is recursively defined as,

\begin{aligned} J_{n} (P_{t, n} (i), {\hat{E}}_{n} (i)) = \\ Σ_{{\hat{E}}_{n} (i + 1)} {max}_{P_{t, n} (i + 1)} {J (P_{t, n} (i + 1), {\hat{E}}_{n} (i + 1))}, \\ P r o b ({\hat{E}}_{n} (i + 1) ∣ {\hat{E}}_{n} (i), P_{t, n} (i)) - \frac{λ}{max {P_{t}}} \cdot P_{t, n} (i), \\ i = i_{0}, \dots, i_{0} + T_{n} (i_{0}) . \end{aligned}

(24)

where,

\begin{aligned} P r o b ({\hat{E}}_{n} (i + 1) ∣ {\hat{E}}_{n} (i), P_{t, n} (i)) = \\ {\begin{cases} P \hat{E} R_{n} (i), {\hat{K}}_{n} (i + 1) = {\hat{K}}_{n} (i); \\ 1 - P \hat{E} R_{n} (i), {\hat{K}}_{n} (i + 1) = {\hat{K}}_{n} (i) - 1; \\ 0, o t h e r s; \end{cases} \end{aligned}

(25)

And,

P \hat{E} R_{n} (i) = 1 - {(1 - Q (\sqrt{\frac{2 P_{t, n} (i) \cdot A}{{\hat{D}}_{n} (i) \cdot σ_{n}^{2}}}))}^{F_{d}},

(26)

assuming that BPSK modulated uncoded signal is transmitted.

The final state configuration function is J_n (Ě_n(i₀ + T_n(i₀) + 1)). In compliance with Eq. (19), it is defined as,

J_{n} ({\hat{E}}_{n} (i_{0} + T_{n} (i_{0}) + 1)) = K_{n} (i_{0}) - {\hat{K}}_{n} (i_{0} + T_{n} (i_{0}) + 1) .

(27)

Table 2

Suboptimal MTSA-MSSN Algorithm Preprocessing

Table 2 summarizes the TSA-MSSN preprocessing in suboptimal algorithms. After the preprocessing we obtain the TSA-MSSN power decision on each node, {P∗_t,n (E_n (i₀))|n = 1… N. Due to the constraint on Eq. (9), only one node has a transmitting power greater than zero at any time slot. Different suboptimal algorithms will operate in different ways in deciding η^s (E(i₀)) ∊ {1…N}, and then,

P_{t}^{s} (E (i_{0})) = P_{t, η^{s} (E (i_{0}))}^{*} (E_{η^{s} (E (i_{0}))} (i_{0})) .

(28)

4.2. Suboptimal Algorithm I: Maximal Sensor Power Strategy (MSPS-MSSN)

The strategy here is to choose the node with maximum P∗_t,n (E_n (i₀)) as the transmitting node, that is,

η^{s} (E (i_{0})) = \underset{n}{arg max} {P_{t, n}^{*} (E_{n} (i_{0}))},

(29)

and then by Eq. (28),

P_{t}^{s} (E (i_{0})) = max_{n} {P_{t, n}^{*} (E_{n} (i_{0}))} .

(30)

Thus, in general, the MSPS-MSSN assumes that the sensor node with higher TSA-MSSN power level has higher “urgency” in transmission.

4.3. Suboptimal Algorithm II: Maximal Sensor Utility Strategy (MSUS-MSSN)

Based on the TSA-MSSN preprocessing results, MSUS-MSSN chooses the node with the maximal achievable TSA-MSSN utility summation, which is conceptually interpreted as the associated utility functions summation by selecting one node n for transmitting. The specific summation is mathematically defined as, for n = 1…N,

U_{n} (E (i_{0})) = \sum_{p = 1 : p \neq n}^{N} {J_{p} (0, {\hat{E}}_{p} (i_{0}))} + J_{n} (P_{t, n}^{*} (E_{n} (i_{0})), {\hat{E}}_{n} (i_{0})) .

(31)

We have,

η^{s} (E (i_{0})) = \underset{n}{arg max} {U_{n} (E (i_{0}))},

(32)

and $P_{t}^{s} (E (i_{0}))$ is obtained through Eq. (28).

4.4. Comparisons of Optimal and Suboptimal Algorithms

To provide an analytical performance comparison between optimal and suboptimal algorithms is difficult. However, we discuss two case studies.

Case 1: TSA-MSSN Active Case: The definition of “active” is that at least one of the N TSA-MSSN power decisions {P∗_t,n(E_n (i₀)) | n = 1…N} is nonzero. Consider a simplified scenario where “ideal coding” is utilized on every sensor node, and the power control level P_t,n(i₀) on the sensor node is continuous. Furthermore, we assume that there is no shadowing uncertainty about the channel, that is $σ_{ξ}^{2} = 0$ . These imply that,

P E R_{n} (i_{0}) = {\begin{cases} 0, & P_{t, n} (i_{0}) \geq B \cdot G_{n} (i_{0}); \\ 1, & P_{t, n} (i_{0}) < B \cdot G_{n} (i_{0}); \end{cases}

(33)

holds, instead of Eq. (26) where an uncoded binary information sequence has been assumed. B in Eq. (33) is a constant that depends on the noise power $σ_{n}^{2}$ and the transmission rate R. Under this scenario, in both optimal and suboptimal algorithms, we have the following equations,

{\begin{cases} P_{t}^{*} (E (i_{0})) = B \cdot G_{η^{*} (E (i_{0}))} (i_{0}); \\ P_{t}^{s} (E (i_{0})) = B \cdot G_{η^{s} (E (i_{0}))} (i_{0}); \end{cases}

(34)

Eq. (34) can be interpreted as follows: For the selected transmitting node n, since $P_{t, n} (i_{0}) = B \cdot G_{n} (i_{0})$ is the minimum power which guarantees the successful packet transmission with probability one, it must be the optimal power decision for both suboptimal and optimal algorithms.

According to the simplified model of Eq. (34), the optimal and suboptimal algorithms differ only in the way of choosing the transmission node, η∗ (E(i₀)) or η^s (E(i₀)), respectively. Note that under more realistic settings, this claim holds only approximately. When comparing MSPS-MSSN and MSUS-MSSN, we note that the latter takes into considerations both the energy consumption and the number of residual packets on every node, while the former takes into considerations only the transmitting power. A simulation comparison of the optimal and suboptimal algorithms is given in Section V.

Case II: TSA-MSSN Sleeping Case: The definition of TSA-MSSN “sleeping” case is that the TSA-MSSN power decision by Eq. (23) is zero for all nodes, that is,

P_{t, n}^{*} (E (i_{0})) = 0, n = 1 \dots N .

(35)

Under this condition, all suboptimal algorithms will keep all nodes sleeping in the current time slot i₀. The optimal MTSA-MSSM performs strictly better, since it avoids this restriction by jointly deciding the transmission strategy over all N nodes.

Consider the following illustrative example. We set N = 2, and L₁ = L₂ = [0,5]. Let θ_s = 0, L_s = [−10,0], and K₁(i₀) = K₂(i₀) = 11. The ν_s is set in such a way that ν_s. Δt = 1. The TSA-MSSN run on each node will provide the result that P∗ _t,n (E(i₀)) = 0, n = 1,2, since there are enough “better” time slots available for transmission when the sink is moving along the x-axis. However, when jointly considering two nodes, the scheduling algorithm will force one node to transmit, which is equivalent to running TSA-MSSN on one node with K = 20.

Since virtually all the configurations in nodes/sink fall under the two described cases, one should avoid Case II when employing suboptimal scheduling algorithms. This, however, can be achieved by the special design in the Media Access Control (MAC) layer channel selecting algorithm.

4.5. Implementation of Suboptimal Algorithms

As it has already been mentioned, to avoid the performance degradation in suboptimal algorithms, one should avoid “Case II.” This can be accomplished by running the channel selection algorithm for one specific node n only when it is active, i.e. P∗_t,n (E_n (i₀)) > C. This criterion, on the other hand, also enhances the spectrum efficiency by keeping all the occupied channels busy.

At the current time i₀, assume that there are N_all(i₀) nodes associated to the mobile sink. And there are M(i₀) occupied channels, where obviously M(i₀) < N_all(i₀). Define a sensor nodes subset A(i₀) of {n| n = 1…N_all(i₀)} to be,

A (i_{0}) = {n ∣ P_{t, n}^{*} (E_{n} (i_{0})) > 0, n = 1 \dots N_{a l l} (i_{0})} .

(36)

Then, at time i₀, the channel selection algorithm only runs on the newly activated nodes n ∊ A_new(i₀), where

A_{n e w} (i_{0}) = A (i_{0}) - A (i_{0}) \cap A (i_{0} - 1) .

(37)

Suppose that the maximum number of available channels is M_max. If M(i₀) < M_max, the channel selecting algorithm can always randomly pick one vacant channel for the new active node, n ∊ A_new(i₀). However, if M(i₀) = M_max, the channel selection algorithm selects one of the M_max occupied channels for the new node, according to some criterion. Although a further discussion on channel selection algorithms is outside the scope of this paper, we give an illustrative example. When M(i₀) = M_max, assume that the system states associated with M_max channels are E^m(i₀) (m = 1…M_max), respectively. Let A^m(i₀) denote the set of nodes sharing the channel m. We define the overall packets number of channel m, K^m(i₀), as,

K^{m} (i_{0}) = \sum_{n ε A^{m} (i_{0})} K_{n} (i_{0}) .

(38)

Table 3

Channel Selecting Algorithm

A simple criterion on deciding the selected channel m∗ for the new node is that K^m∗(i₀) be minimal. This criterion, however, expresses a rule of thumb, which simply prevents overcrowding any one particular channel. Table 3 describes this algorithm.

5. Simulations

The following simulations scenario is considered. The sink is passing through the sensor network region. Some parameters generally comply with IEEE 802.15.4 [6], and are listed in Table 4. The number of transmission power levels is set to 10, and the set of discrete levels is,

\begin{aligned} P_{t} (i) ε {- \infty, - 32, - 28, - 24, - 20, \\ - 16, - 12, - 8, - 4, 0} (d B m) . \end{aligned}

(39)

λ, which is the parameter to decide the tradeoff between successful transmission and energy consumption, is set to be ‘1’ throughout all the simulations. The setups of the stimulations in Section V-A and V-B, i.e. the nodes/sink locations and the packet numbers, are randomly chosen, satisfying the “active” and ‘sleeping” conditions, respectively. All the results in the figures are the average of 500 Monte-Carlo runs.

5.1. Case 1: TSA-MSSN Active Case

We compare the optimal and suboptimal algorithms under “Case I” specified in Section IV-D.1. We assume that two sensor nodes are sharing one specific communication channel, that is N = 2. Without loss of generality, let L₁ = [−5, 5], L₂ = [0, −4], and K₁(i₀) = K₂(i₀) = 10. Set θ_s(i) = 0. With L_s(i₀) = [22, 0], the sink passes through the circular communication region of the nodes in a straight line. That is, the sink is moving away from the nodes.

Table 4
Communication Parameters Setup

Parameter Unit Value

F_d bit 128 × 8

F_b bit 20 × 8

R bits/sec 20000

β 3

A dB −31

Range m 50

$σ_{n}^{2}$ dBm −92

ν_s m/sec 20

Parameter	Unit	Value
F_d	bit	128 × 8
F_b	bit	20 × 8
R	bits/sec	20000
β		3
A	dB	−31
Range	m	50
$σ_{n}^{2}$	dBm	−92
ν_s	m/sec	20

Simulations are performed to measure the energy consumption E_all and successful transmission rate P_all of MTSA-MSSN, MSPS-MSSN, and MSUS-MSSN, respectively. In calculating the energy consumption, we omit the RF circuits energy consumption, since it is the same for all algorithms. Then, the definitions of E_all and P_all will be,

E_{a l l} = \sum_{i - i_{0}}^{i_{0} + T (i_{0})} P_{t}^{r} (i) \cdot \frac{F_{d}}{R},

(40)

P_{a l l} = \sum_{n - 1}^{N} {K_{n} (i_{0}) - K_{n} (i_{0} + T (i_{0}) + 1)},

(41)

respectively, where,

P_{t}^{r} (i) = {\begin{cases} P_{t}^{*} (E (i)), & f o r o p t i m a l; \\ P_{t}^{s} (E (i)), & f o r s u b o p t i m a l; \end{cases}

(42)

Figures 2 and 3 plot E_all and P_all, respectively, when $σ_{ξ}^{2}$ changes.

The following observations are made: The energy consumption E_all of MSPS-MSSN is much higher than the other two algorithms everywhere; however, it also has a higher P_all than others when $σ_{ξ}^{2}$ is relatively small. Compared with MSPS-MSSN, the MTSA-MSSN and MSUS-MSSN offer a better tradeoff between energy consumption and a successful transmission rate. Although MTSA-MSSN is theoretically optimal and has a much higher complexity, the suboptimal MSUS-MSSN surprisingly performs at least as good as MTSA-MSSN in the simulation. When $σ_{ξ}^{2}$ is small, MTSA-MSSN outperforms MSUS-MSSN slightly, as shown in Figs. 2 and 3. However, when $σ_{ξ}^{2}$ becomes large, the suboptimal MSUS-MSSN becomes better than the optimal algorithm in both energy consumption and the successful transmission rate. The result may seem to be strange at first glance. This is, however, due to the fact that scheduling algorithms are unaware of the shadowing effect of the channel in Eq. (3) (see Eq. (12)). Suboptimal MTSA-MSSN chooses a higher transmission power level, which consumes more energy on one hand, and enhances the probability of successful transmission on the other. Generally, in “Case I,” suboptimal algorithms are efficient alternatives to the optimal one. Especially for the MSUS-MSSN, it performs as good as the optimal algorithm in terms of total energy consumption E_all and successful transmission rate P_all.

Figure 2

Case I: total energy consumption E_all vs. $σ_{n}^{2}$ .

5.2. Case II: TSA-MSSN Sleeping Case

We compare E_all and P_all of MTSA-MSSN, MSPS-MSSN, and MSUS-MSSN under “Case II” specified in Section IV-D.2. Again, we assume two sensor nodes are associated with one specific communication channel, which is N = 2. let L₁ = [15, 5], L₂ = [15, −8], and K₁(i₀) = K₂(i₀) = 8. Set θ_s(i) = 0. With L_s(i₀) = [0, 0], the sink passes through the circular communication region of the nodes in a straight line. That is, the sink is moving toward the nodes.

Since the number of available time slots are much higher than the number of packets in this simulation, P_all for all the algorithms is 16, which implies that no packet is lost in the transmission. Figure 4 shows the variation of E_all when $σ_{ξ}^{2}$ changes. We observe that the suboptimal algorithms consume much higher energy than the optimal one for all $σ_{ξ}^{2}$ . The result agrees with our analysis in Section IV-D.2.

Figure 3

Case I: successfully transmitted packets P_all vs. $σ_{ξ}^{2}$ .

6. Discussions

6.1. Centralized vs. Distributed Scheduling

We hereby compare the multiple access MSSN with the SENMA [20], [21]. Although the two have similar network topology, they are nevertheless different types of networks.

In MSSN, we assume certain signal processing capability on individual sensor nodes, which can be viewed as the high level event acquisition [4], instead of raw data acquisition. The sink is dominant in MSSN, since the deterministic scheduling is decided on the sink. SENMA, on the other hand, assumes a simple reachback sensor network, where the sensor nodes transmit raw data to the sink (mobile agent), with no inter-node signal processing. The sink in SENMA, on the other hand, consecutively retrieves the packets from the node with the best channel state. SENMA is a sensor nodes dominant network, because the random access is implemented. SENMA claims low complexity of the sensor nodes. MSSN, however, achieves a higher efficiency and a higher application specific flexibility [1], because of the high level event acquisition. The proposed scheduling algorithms better utilize the higher processing/power capability of the sink, and keep the simplicity of sensor nodes. The choice between MSSN and SENMA should be dependent on the application requirements.

The proposed scheduling algorithms are centralized, since the mobile sink completely decides the transmission strategies. Under the setup of SENMA, [21] proposed the distributed opportunistic scheduling algorithm, by assuming channel state information on sensor nodes. Compared with centralized algorithms, distributed algorithms can save protocol overheads. However, in the multiple access MSSN, since the scheduling criterion is more complicated, we consider that the development of distributed scheduling algorithms for MSSN is not cost-efficient.

Figure 4

Case II: total energy consumption E_all vs. $σ_{ξ}^{2}$

6.2. Algorithmic Extensions and Cross-layer Design

First, the final state configuration function, given by Eq. (19,27), corresponds to the “Application scenario 1” in [1]. As described in [1], the final state configuration is application specific. Different configurations can be applied with the algorithms proposed in this paper without further difficulty. In both [1] and this paper, we have assumed that the transmission rate R is constant. When this assumption does not hold, and multi-rate channel coding is feasible on sensor node, the strategy space of MTSA-MSSN will be the size of N·Sizeof {P_t}·Sizeof {R}, which corresponds to an increase by a factor of Sizeof {R}, the number of rate control levels. Suboptimal algorithms, such as the MSUS-MSSN, can also be extended to this multi-rate case.

Second, in the channel mode Eq. (3), the small scale multipath fading was not considered. By assuming a small scale fading model, e.g. the Rayleigh fading, in Eq. (3), we need to recalculate the PĚR function in Eq. (12), which is a function of the separating distance D(i), the transmission power level P_t(i), and the transmission rate R. The fading may not be overlooked in some scenarios, especially when the transmission rate is high, and the time diversity over fading states is not achievable. Although multiple receiving antenna diversity can be a solution, another more cost-efficient alternative is the cooperative transmission in a densely deployed sensor network [2]. It utilizes, by the theory of MIMO structure, nodes space diversity instead of receiving antenna diversity. Diverse coding schemes and channel models can be implemented in this framework with non-significant modifications on the scheduling algorithms. The details of the implementations are subject to future research.

Traditionally, packet transmission scheduling is included in the data link layer. However, by exploiting the tradeoff between the successful transmission and the energy consumption, the cross layer design of a consolidate physical and data link layer is needed. In [3], [4], Embedded Wireless Interconnect (EWI) was proposed as the potential universal architecture of wireless sensor networks. EWI is composed of two layers, which are the Wireless Link layer and the System layer, respectively. Under the architecture of EWI, the proposed transmission scheduling algorithms work on the Wireless Link layer of MSSN. It interacts with the upper System layer by the syntax of application information credits, which is then translated into the final state configuration function of the scheduling algorithms.

7. Conclusion

In this paper, we have studied the operation of MSSN when multiple nodes share one communication channel during the information retrieval. First, we have developed the optimal multinode scheduling algorithm MTSA-MSSN. Since the complexity of MTSA-MSSN increases exponentially with the number of nodes, we propose suboptimal algorithms, which run the single node scheduling algorithm TSA-MSSN individually on every node and then combine the results. The two suboptimal algorithms, MSPS-MSSN and MSUS-MSSN, exhibit the complexity as low as O(N). The performances of optimal and suboptimal algorithms are compared by means of computer simulations. It is shown that the suboptimal algorithms achieve nearly the same performance as the optimal MTSA-MSSN when the channel is “active.”

Footnotes

APPENDIX I

APPENDIX II

References

Song

Hatzinakos

, “Architecture of wireless sensor networks with mobile sinks: sparse deploying case,” IEEE Trans. on Vehicular Technology vol. 56, no. 4, July 2007, URL: www.comm.utoronto.ca/~songl/pdf/mssnl.pdf.

Song

Hatzinakos

, “Cooperative transmission in poisson distributed wireless sensor networks: protocol and outage probability.” IEEE Trans. on Wireless Communication vol. 5, no. 10, pp. 2834–2843, Oct. 2006. URL: www.comm.utoronto.ca/~songl/pdf/ctp.pdf.

Song

Hatzinakos

, “Embedded wireless interconnect for sensor networks: concept and example,” In Proc. IEEE 4th Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, 2007. URL: www.comm.utoronto.ca/~songl/pdf/cwi.pdf.

Song

Hatzinakos

, “A cross-layer architecture of wireless sensor networks for target tracking,” IEEE/ACM Trans. on Networking vol. 15, no. 1, pp. 145–158, Feb. 2007. URL.: www.comm.utoronto.ca/~songl/pdf/lesop.pdf.

Peter

Garrison

, “Microspics,” Air & Space Smithsonian, pp. 54. April/May 2000.

Standard IEEE 802.15.4. MAC and PHY Layer specification for low-rate wireless personal area networks (PR-WPANs).

Standard IEEE 802.11. Wireless LAN medium access control(MAC) and physical layer(PHY) specifications.

Tse

Hanly

S. V.

, “Multiaccess fading channels - Part I: polymatroid structure, optimal resource allocation and throughput capacities,” IEEE Trans. Inform. Theory vol. 44, no. 7, pp. 2796–2815. Nov. 1998.

Goldsmith

A. J.

, “Optimal resource allocation for pading broadcast channels - Part II: outage capacity,” IEEE Trans. on Information Theory vol. 47, no. 3, pp. 1103–1127, Mar. 2001.

10.

Hanly

S. V.

Tsc

, “Multiaccess fading channels - Part II: Delay-limited capacities,” IEEE Trans. on Information Theory vol. 44, no. 7, pp. 2816–2831. Nov. 1998.

11.

Jindal

Goldsmith

, “Outage capacities and optimal power allocation for fading multiple-access channels,” IEEE Trans. on Information Theory vol. 51, no. 4, Apr. 2005.

12.

Zhao

Shen

Mark

J. W.

, “Radio resource management for cellular CDMA systems supporting heterogeneous services,” IEEE Trans. on Mobile Computing vol. 2, no. 2, pp. 147–169, Apr.–Jun. 2003.

13.

Oottamakorn

Bushmitch

, “Resource management and scheduling for QoS-Capable home network wireless access point,” in Proc. IEEE CCNC′2004, pp. 7–12. 5–8 Jan. 2004.

14.

Pradhan

S. S.

Kusuma

Ramchandran

, “Distributed compression in a dense micro-sensor network,” IEEE Signal Processing Magazine vol. 19, no. 2, pp. 51–60. Mar. 2002.

15.

Proakis

J. G.

, Digital Communications, NJ: McGraw-Hill Inc., 1995.

16.

Bertoni

H. L.

, Radio Propogation for Modern Wireless Systems, NJ: Prentice Hall PTR, 2000.

17.

Pentland

, “Smart Rooms,” Scientific American, April 1996.

18.

Cover

T. M.

Thomas

J. A.

, Elements of Information Theory, NJ: John Wiley & Sons. Inc. 1991.

19.

Shah

R. C.

Roy

Jain

Brunette

. “Data MULES: Modeling a three-tier architecture for sparse sensor networks,” in Proc. of the First IEEE International Workshop on Sensor Network Protocals and Applications, Anchorage, Alaska, 11 May, 2003.

20.

Tong

Zhao

Adireddy

, “Sensor networks with mobile Agents,” in Proc. IEEE MilCom’2003.

21.

Zhao

Tong

, “Distributed opportunistic trabsmission for wireless sensor networks,” in Proc. IEEE ICASSP’2004.

22.

Bertsekas

, Dynamic Programming and Optimal Control, Belmont, MA, Athena Scientific, 1995.

Architecture of Wireless Sensor Networks with Mobile Sinks: Multiple Access Case

Abstract

Keywords

1. Introduction

2. System Description

2.1. Concepts and Assumptions

2.2. System State Vector Ě(i 0 )

Table 4 Communication Parameters Setup Parameter Unit Value Fd bit 128 × 8 Fb bit 20 × 8 R bits/sec 20000 β 3 A dB −31 Range m 50 σ n 2 dBm −92 ν s m/sec 20

6.1. Centralized vs. Distributed Scheduling

7. Conclusion

Footnotes

APPENDIX I

APPENDIX II

References

2.2. System State Vector Ě(i₀)

Table 4
Communication Parameters Setup

Parameter Unit Value

F_d bit 128 × 8

F_b bit 20 × 8

R bits/sec 20000

β 3

A dB −31

Range m 50

$σ_{n}^{2}$ dBm −92

ν_s m/sec 20