A method of data propagation with operator intent delivery for wireless sensor networks

Abstract

In this paper, we propose a data propagation method with operator intent delivery in Wireless Sensor Networks (WSNs). The proposed algorithm propagates data by controlling the state of a sensor node depending on the delay requirements of a specific application. Also, the proposed algorithm allows users to interact with the WSNs to convey desired parameter values for the operations. Simulation results indicate that the proposed algorithm achieves reliable data propagation and user intent delivery while saving energy consumption.

Keywords

Wireless sensor networks data propagation parameter setting

1. Introduction

Wireless Sensor Networks (WSNs) usually need to survive for a long time. Therefore, low duty cycle has been a critical challenge to reduce the energy consumed by unnecessary idle listening [1,24]. However, delay-sensitive applications such as emergency and rescue applications, require their own specific functionalities for reliable data delivery. For these applications, it is important to design efficient algorithms with the aim of performance guarantee for the WSNs. Also, in order to change parameters of a WSN control algorithm, user needs to interact with the WSN.

Biologically inspired modeling techniques have received considerable attention as a new way for the realization of WSNs that are robust, scalable and adaptable, yet retain their individual simplicity in computer networks [4,5,8,15,19]. In specific, epidemic-based methods have been proposed for use in data dissemination, routing, and broadcasting protocols [6,10,11,13,14,16–18,23]. Epidemic-based communications provide an effective means of transferring data in WSNs, in which the infection transmission process corresponds to the message passing among sensors. The analogy between information dissemination in WSNs and transmission of epidemics in communities is evident: a sensor node can be referred to as infected when it receives a piece of information and stores it, and can otherwise be considered susceptible. An epidemic is regarded as a chain reaction in transmission of an infection. One of the prominent works of data dissemination modeled by epidemic theoretical concepts is SPIN [13]. These researchers focused on the efficient dissemination of individual sensor observations to all the sensors and proposed data descriptors to eliminate the chance of redundant transmission in WSNs. Other authors proposed a TDMA based data dissemination protocol for WSN to offer a degree of reliability [14]. The Firecracker protocol [16] used a combination of routing and broadcast principles to rapidly disseminate data throughout WSNs. Trickle [17] was proposed for propagating and maintaining code updates as fast as possible to all nodes in the network. The key contribution of this protocol was ‘its polite gossip’ that used suppression and dynamic adjustment of the broadcast rate to limit transmissions among neighboring nodes. It only provided a mechanism by which a node might decide when to propagate the code. Deluge [11] added a feature that supports transfer of large data objects based on Trickle principles. Still other authors proposed a gossip-based approach where each node decides to forward a message to another node based on some probability [10]. The problem with gossip is that, if a source has very few neighbors, then the nodes will not gossip and the information dies out. Middleware has been proposed [18] to provide controlled epidemic style dissemination using information dissemination techniques to tune the process according to the desired reliability. In another case [23] an MRO (multi-rumor overwriting) model was proposed. The model described dissemination and interaction of periodically sensed data, which were distributed by gossiping, without increasing the traffic on the network. However, these existing algorithms have not achieved satisfying a desired level of performance of the delay-sensitive application.

In order to convey user intent to the WSN, a centralized method was explored [7,12]. More decentralized approaches include methods to allow the user to adjust the autonomy of a small subset of nodes to influence the WSN behavior [2]. Previous existing approaches relay commands from the operator to the WSNs by broadcasting parameter changes or user intent to all nodes in the WSNs or by using tele-operation of a leader node. However, these methods are not feasible to the system with a large number of sensor nodes. Instead, the operator should control the WSN as a single entity. A leader-based control is proposed to deal with the complexity of controlling a WSN [9,20–22]. In a leader-based control, the operator selects a single leader (or groups of nodes) and directly controls the leader, such influences the propagation effects on the remaining sensor nodes based on local control laws used by the sensor nodes. Walker et al. [21,22] focused on two leader-based methods of information propagation and compared the ability of operators to manage the WSN system to the desired goals. Goodrich et al. [9] worked on a leader-based control using teleoperated leaders based on Couzin’s control laws. Pendleton et al. [20] similarly implemented a leader-based model using both virtual agents and a human operator as leaders. However, as the number of nodes involved in the task grows large, such approaches can become less effective and unstable due to a lack of scalability.

To address these concerns, we extend the existing study proposed in [3] and provide a user control of WSNs by conveying user intent or parameter changes for the operation of the WSN systems. The previous work [3] was based on epidemic theory which models propagation process of an infection. The algorithms inspired by epidemic theory were mainly for the data propagation for all nodes in WSN within a given delay requirement. In this paper, we propose a new interaction algorithm for WSNs to convey desired operator intent for the appropriate propagation process. That is, we extend the existing study for the operator intent delivery and newly propose a scheme, which conveys user intent or parameter changes for the operation of the WSN systems.

2. Data propagation with operator intent

In this section, we introduce a data forwarding method based on epidemic theory. Then, we propose an autonomous real-time controller for the operator intent propagation based on the leader-based control. The proposed method influences the WSN operation by indirectly propagating the operator intent and the parameter changes within the framework of local rules in a decentralized manner.

2.1. Model

We introduce a data forwarding method proposed in [3]. Let $N = {1, 2, \dots, N}$ denote the set of sensor nodes in a WSN. Each sensor node can be only in one of two states; active or sleep. Sensor nodes turn off their radios when asleep and turn them on when active to exchange information packets. The discrete dynamic model for WSN is defined as: $\begin{array}{l} (1) & N_{s} (n + 1) = max (min (N_{s} (n) - α (n) N_{a} (n) N_{s} (n) + β N_{s} (n), N_{t} (n) - N_{a, min}), 0) \\ (2) & N_{a} (n + 1) = min (max (N_{a} (n) + α (n) N_{a} (n) N_{s} (n) - β N_{a} (n), N_{a, min}), N_{t} (n)) \\ (3) & N_{t} (n) = N_{s} (n) + N_{a} (n), \end{array}$ where $N_{s} (n)$ and $N_{a} (n)$ are the number of nodes in sleep state and in active state at time slot n, respectively, α is the infectivity rate, β is a control parameter, and $N_{t}$ is the total number of sensor nodes. The value of $N_{a, min}$ is the minimum $N_{a}$ needed to ensure a certain level of reliability, and can be determined based on the desired delivery ratio. We denote $d (n)$ and $d_{r}$ as the maximum measured delay among nodes and the delay requirement of the application, respectively. Equations (1)–(3) show that the number of active nodes are calculated with dynamic infectivity α. The dynamics of α is modeled by the following equation: $\begin{matrix} (4) & \begin{array}{l} α (n + 1) = (1 - ε) α (n) + η Φ (σ (n)) \\ σ (n) = d (n) - d_{r}, \end{array} \end{matrix}$ where $ε (≪ 1)$ is a positive constant and η is the control parameter to be chosen. The function Φ is an increasing function from the interval $[- d_{M}, \infty]$ , where $d_{M}$ is the upper bound of delay requirement. The combined model of (1)–(4) determines that when the measured delay exceeds the delay requirement, the value of α increases, which leads to new active nodes among the total nodes. Alternatively, when the measured delay is less than the delay requirement, the value of α decreases, resulting in an increased number of sleeping nodes. Using the value of $N_{a}$ determined by (2) and (4), each sensor node decides whether it will have active or inactive status for the next controller time slot. If the maximum measured delay exceeds the required delay, the values of α and $N_{a}$ increase, resulting in a higher probability of being active. This leads to delay reduction and more frequent packet transmission, but if the maximum measured delay is smaller than the required delay, the value of α and $N_{a}$ decreases, resulting in energy savings by increasing sleep time.

2.2. Conveying operator intent to the WSNs

The data propagation model of (1)–(4) depends on some parameters such as β, $d_{r}$ , for the WSN operation. Theses parameters should be properly conveyed from the operator to the WSNs. In this paper, we focus on indirect parameter setting aided by an autonomous algorithm. To establish control model of a user-WSN interaction, we consider a system with inputs controlled by a user, that is, the user controls the behavior of the WSN by interacting with sensor nodes.

Let $u (t)$ be the input to the system at time t and $x (t)$ be the state of the system at time t. In specific, $x (t)$ represents the states of all sensor nodes at time t and can be indicated as vector $x (t) = {[\begin{matrix} x_{1} (t) & x_{2} (t) & \dots & x_{N} (t) \end{matrix}]}^{T}$ , where $x_{i} (t)$ is the state vector of sensor node i at time t. The sensor node i interacts with its neighbors with the state values $x_{i}$ . With the state vector of its neighbor node and its own state vector, each sensor node updates its state value according to the proposed controller. We denote $N_{i}$ as the set of neighbor nodes of node i. The user interacts with the WSNs by applying control input to a single node (gateway node), while the other nodes interact with each other according to the proposed dynamics. With this respect, we propose the dynamics of the system as follows: $\begin{matrix} (5) & \dot{x} (t) = f (x (t), u (t)) \end{matrix}$ The user applies the desired input to the Nth node, while the other sensor nodes propagate indirectly by interacting with each other following the local control law of each node: $\begin{matrix} (6) & \begin{array}{l} {\dot{x}}_{i} (t) = \sum_{j \in N_{i}} (x_{j} (t) - x_{i} (t)), if i \neq N \\ {\dot{x}}_{i} (t) = 0, if i = = N \end{array} \end{matrix}$ We consider that input function $u (t)$ is piecewise constant having a finite linear combination of indicator functions of intervals. The user input is directly applied for Nth node by letting $x_{N} (t) = u (t)$ . Therefore, user directly controls the state of a single gateway node and the interactions between the nodes are handled autonomously. The human operator takes actions independent of the number of nodes and supervises the WSN system as a single entity, resulting in a control complexity of $O (1)$ .

Let us denote $x_{s} = {[\begin{matrix} x_{1 s} & x_{2 s} & \dots & x_{N s} \end{matrix}]}^{T}$ as a steady state vector $x (t)$ , where $x_{i s}$ is the steady state of node i. For a desired user input $u (t) ≃ u$ , the steady states of $x_{i}$ is derived as follows: $\begin{matrix} (7) & \begin{array}{l} x_{i s} = \frac{1}{N_{i}} (1_{(i, 1)} x_{1 s} + 1_{(i, 2)} x_{2 s} + \dots + 1_{(i, N)} x_{N s}), \forall i \in N, i \neq N \\ x_{N s} = u \end{array} \end{matrix}$ Then, (7) is rewritten as $\begin{matrix} (8) & {Ax}_{s} = b \end{matrix}$ where $\begin{array}{l} (9) & A = [\begin{matrix} 1 & - \frac{1}{N_{1}} 1_{(1, 2)} & \dots & - \frac{1}{N_{1}} 1_{(1, N - 1)} \\ - \frac{1}{N_{2}} 1_{(2, 1)} & 1 & \dots & - \frac{1}{N_{2}} 1_{(2, N - 1)} \\ ⋮ & ⋱ & ⋱ & ⋮ \\ - \frac{1}{N_{N - 1}} 1_{(N - 1, 1)} & - \frac{1}{N_{N - 1}} 1_{(N - 1, 2)} & \dots & - \frac{1}{N_{N - 1}} 1_{(N - 1, N - 1)} \end{matrix}] \\ (10) & b = u {[\begin{matrix} \frac{1_{(1, N)}}{N_{1}} & \frac{1_{(2, N)}}{N_{2}} & \dots & \frac{1_{(N - 1, N)}}{N_{N - 1}} \end{matrix}]}^{T} \end{array}$ where $\begin{matrix} (11) & 1_{(i, j)} = \{\begin{matrix} 1 & if j \in N_{i} \\ 0 & else \end{matrix} \end{matrix}$ Note that $\sum_{j \in N_{i}} 1_{(i, j)} = N_{i}$ . Then, the steady state $x_{s}$ is derived as follows: $\begin{matrix} (12) & x_{s} = A^{- 1} b = {[\begin{matrix} u & u & \dots & u \end{matrix}]}^{T} \end{matrix}$

In order to ensure the stability of the proposed system, we define $y (t) = {[\begin{matrix} y_{1} (t) & y_{2} (t) & \dots & y_{N - 1} (t) \end{matrix}]}^{T}$ where $y_{i} (t) = x_{i} (t) - x_{i s}$ . Then, the state space model for control design is written as follows: $\begin{matrix} (13) & \dot{y} (t) = A_{s} y (t) \end{matrix}$ where $\begin{matrix} (14) & A_{s} = [\begin{matrix} - N_{1} & 1_{(1, 2)} & \dots & 1_{(1, N - 1)} \\ 1_{(2, 1)} & - N_{2} & \dots & 1_{(2, N - 1)} \\ ⋮ & ⋱ & ⋱ & ⋮ \\ 1_{(N - 1, 1)} & 1_{(N - 1, 2)} & \dots & - N_{N - 1} \end{matrix}] \end{matrix}$ With the equilibrium point $y_{s}$ , we define $e = y - y_{s}$ as the error. Then the error dynamics can be described as $\begin{array}{rcl} (15) & \dot{e} & = & A_{s} (e + y_{s}) \\ (16) & = & A_{s} e \end{array}$ We use Lyapunov Theory to claim that the proposed system will be convergent if we can find a Lyapunov function $V (e)$ that satisfies the following conditions:

$V (e)$ is positive definite;

$\dot{V} (e)$ is negative definite.

We assume that there exist positive definite matrices P and Q,

P = P^{T}

, such that

\begin{array}{rcl} (17) & P A_{s} + A_{s}^{T} P = - Q . \end{array}

Consider the Lyapunov function in the following form:

\begin{matrix} (18) & V (e) = \frac{1}{2} e^{T} P e . \end{matrix}

Then, obviously

V (e) ⩾ 0

and we can get the time derivative

\dot{V} (e)

as follows:

\begin{array}{rcl} \dot{V} (e) & = & \frac{1}{2} ({\dot{e}}^{T} P e + e^{T} P \dot{e}) \\ = & \frac{1}{2} e^{T} (A_{s}^{T} P + P A_{s}) e \\ = & - \frac{1}{2} e^{T} Q e ⩽ 0 \end{array}

Based on the above analysis, both conditions of the Lyapunov function

V (e)

have been satisfied, thus we can claim that the system is stable and the error dynamics will converge to zero exponentially, i.e., the trajectory of system state will converge to the steady state as time goes to infinity.

3. Simulation results

The simulations are conducted using a simulator written in MATLAB. The simulator captures real life events such as carrier sensing, backoff, and collisions. At the beginning of a simulation, nodes are randomly placed inside the simulation area, and the source node is placed at the center. Once nodes are deployed, nodes start duty-cycling by switching between active and sleep mode. At some point, the source node starts generating packets periodically at a fixed rate. The packets are stamped with sequence numbers, so that a node does not receive or forward duplicate packets. The goal of the source node is to send the packet to all the other nodes in the network, within a given delay. The evaluation metrics are the average number of active sensor nodes varying delay requirements, the state value of each sensor node under the given user input, and the average state values varying user inputs. The default parameters used in the simulations are listed in Table 1. A point in the graph is an average of 1000 simulation runs, with different delay requirements and different user inputs.

Table 1
Default parameters used in simulations

Parameter name Default value

simulation area $100 m \times 100 m$

number of nodes 100, 200

transmission range 20 m

carrier sense range 40 m

duty cycle (wakeup interval) 1 s

packet generation interval 60 s

current consumption: Tx 17.4 mA

current consumption: Rx 19.7 mA

current consumption: mode switch 10.05 mA

mode switch time 300 μs

backoff time 30 ms

initial $N_{a}$ 30

β 0.1

η 0.0001

ε 0.001

Parameter name	Default value
simulation area	$100 m \times 100 m$
number of nodes	100, 200
transmission range	20 m
carrier sense range	40 m
duty cycle (wakeup interval)	1 s
packet generation interval	60 s
current consumption: Tx	17.4 mA
current consumption: Rx	19.7 mA
current consumption: mode switch	10.05 mA
mode switch time	300 μs
backoff time	30 ms
initial $N_{a}$	30
β	0.1
η	0.0001
ε	0.001

The parameter $N_{a}$ decides the average number of nodes that wake up at a particular active period. If $N_{a}$ is too low, the packet will die out before being disseminated throughout the entire network. Figure 1 shows the average of $N_{a}$ varying delay requirements. We can observe that the number of active sensor nodes is successfully controlled by the delay requirement. In specific, as the delay requirement becomes larger, the value of $N_{a}$ decreases, which makes the number of sleep nodes increase. On contrary, the value of $N_{a}$ increases when the delay requirement becomes stricter.

Figure 2 shows the trajectories of state vectors of node 1, node 2, and node 3. We change parameter setting $[β, d_{r}]$ by letting $u (t) = {[4, 4]}^{T}$ . In spite of the different initial values of parameter state vector, the value of parameter state of each node converges to the desired global configuration, which is set by the user. Also, by guiding the gateway node to the desired configuration, the user can change the parameter of the algorithm of all sensor nodes autonomously.

Figure 3 shows the steady states of nodes varying user inputs. The graph represents averaged state vector. We can observe that the values of state vector of each node are successfully converged to the user inputs. Therefore, the combinations of data propagation algorithm and user intent conveying algorithm would be effective in modifying the behavior to achieve the desired configuration with such a WSN system.

Fig. 1.

Average $N_{a}$ varying delay requirements.

Fig. 2.

State adaptation of $n_{1}$ , $n_{2}$ , and $n_{3}$ .

Fig. 3.

Steady states of nodes varying user inputs.

4. Conclusions

In this paper, we propose a data propagation method with user command delivery for WSN systems. The proposed algorithm determines the state of node according to the delay requirement of an application. Also, user command or parameter configurations are delivered to the WSN by indirect state adaptation within the framework of local rules in a decentralized manner. Theoretical analysis and simulation results show that the proposed algorithm achieves reliable data propagation and properly influences the WSN operation by propagating the user input to the WSN system.

Footnotes

Acknowledgements

This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning (2017R1A2B1007779).

References

Bachir,

Dohler,

Watteyne and

K.K.

Leung, MAC essentials for wireless sensor networks, IEEE Communications Surveys & Tutorials 12 (2010), 222–248. doi:10.1109/SURV.2010.020510.00058.

Bashyal and

G.K.

Benayagamoorthy, Human swarm interaction for radiation source search and localization, in: IEEE Swarm Intelligence Symposium 2008.

Byun, A reliable data delivery scheme with delay constraints for wireless sensor networks, Journal of High Speed Networks 21 (2015), 195–203. doi:10.3233/JHS-150520.

Charalambous and

Cui, A biologically inspired networking model for wireless sensor networks, IEEE Network 24 (2010), 6–13. doi:10.1109/MNET.2010.5464221.

Cheng,

C.K.

Tse and

F.C.M.

Lau, A bio-inspired scheduling scheme for wireless sensor networks, in: IEEE Vehicular Technology Conference, 2008, pp. 223–227.

De,

S.K.

Das,

Gao and

Zuo, Epidemic Models, Algorithm and Protocols in Wireless Sensor and Ad-hoc Networks, John Wiley & Sons, 2008. doi:10.1002/9780470396360.ch3.

X.C.

Ding,

Powers,

Egerstedt,

Young and

Balch, Executive decision support: Single agent control of multiple UAVs, in: IEEE Robotics and Automation Magazine, 2009.

Dressler and

O.B.

Akan, A survey on bio-inspired networking, Computer Networks 54 (2010), 881–900. doi:10.1016/j.comnet.2009.10.024.

Goodrich,

Pendleton,

Sujit and

Pinto, Toward human interaction with bio-inspired robot teams, in: Proc. IEEE Int. Conf. Syst. Man, Cybern., 2011, pp. 2859–2864.

10.

Z.J.

Haas,

J.Y.

Halpern and

Li, Gossip-based ad hoc routing, IEEE/ACM Trans. Networking 14 (2006), 479–491. doi:10.1109/TNET.2006.876186.

11.

J.W.

Hui and

Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, in: Int. Conf. Embedded Networked Sensor Systems, 2004.

12.

Kira and

M.A.

Potter, Exerting human control over decentralized robot swarms, in: Proc. of the Intl, Conf. on Systems, Man, and Cybernetics, 2010.

13.

Kulik,

Rabiner and

Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, in: Proc. the Fifth ACM/IEEE Int. Conf. Mobile Computing and Networking, 1999, pp. 174–184.

14.

S.S.

Kulkarni and

Arumugam, INFUSE: a TDMA based data dissemination protocol for sensor networks, Technical Report MSU-CSE-04-46, Dept. of Computer Science, Michigan State University, 2004.

15.

Leibnitz and

Murata, Attractor selection and perturbation for robust networks in fluctuating environments, IEEE Network 24 (2010), 14–18. doi:10.1109/MNET.2010.5464222.

16.

Levis and

Culler, The firecracker protocol, in: Proc. the 11th ACM SIGOPS European Workshop, 2004.

17.

Levis,

Patel,

Culler and

Shenker, Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks, in: Proc. the 1st Conf. Symp. Networked Systems Design and Implementation, Vol. 1, 2004, pp. 2.

18.

Musolesi and

Mascolo, Controlled epidemic-style dissemination middleware for mobile ad hoc networks, in: Proc. 3rd Ann. Int. Conf. Mobile and Ubiquitous Systems, 2006, pp. 1–9.

19.

Nakano, Biologically inspired network systems: A review and future prospects, IEEE Trans. Systems, Man, and Cybernetics – Part C: Applications and Reviews 41 (2011), 630–643. doi:10.1109/TSMCC.2010.2090141.

20.

Pendleton and

Goodrich, Scalable human interaction with robotic swarms, American Institute of Aeronautics and Astronautics, 2015. doi:10.2514/6.2013-473.

21.

Walker,

S.A.

Amraii,

Chakraborty and

Sycara, Human control of robot swarms with dynamic leaders, in: Proc. IEEE/RSJ Int. Conf. Intell. Robot. Syst., 2014, pp. 1108–1113.

22.

Walker,

S.A.

Amraii,

Lewis,

Chakraborty and

Sycara, Human control of leader-based swarms, in: Proc. IEEE Int. Conf. Syst. Man, Cybern., 2013, pp. 2712–2717.

23.

Williamson,

Cellai,

Dobson and

Nixon, Modelling periodic data dissemination in wireless sensor networks, in: UKSim European Symposium on Computer Modeling and Simulation 2009, pp. 499–504. doi:10.1109/EMS.2009.31.

24.

Ye,

Heidemann and

Estrin, An energy efficient mac protocol for wireless sensor networks, in: IEEE INFOCOM, pp. 1567–1576, 2002.