Quadratic Programming for TDMA Scheduling in Wireless Sensor Networks

Abstract

This paper presents a novel Multihop Aperiodic Scheduling (MAS) algorithm which guarantees energy-efficient data collection by Wireless Sensor Networks (WSNs) under delay constraints. Present Medium Access Control (MAC) protocols in WSNs typically sacrifice packet latency and/or the reliability of packet transfer to achieve energy-efficiency. Thus, the paper is concerned with developing a novel protocol to achieve energy efficient and reliable multihop data transfer in WSNs satisfying given latency requirements. Energy efficiency is achieved by optimizing the scheduling of the underlying Time Division Multiple Access (TDMA) system by minimizing the wake-up number of the nodes. Schedule optimization is transformed into a quadratic programming (QP) task, which is then solved by the Hopfield net in polynomial time. In this way, an energy efficient scheduling can be obtained which meets a given delay requirement in TDMA systems. The performance of the new algorithm has been evaluated by simulations and compared to the performance of well-known scheduling methods, such as SMAC, UxDMA (a slot assignment algorithm for WSN), and traditional tree-based protocols. The simulations have demonstrated that our method reduces global power consumption for time-driven monitoring.

1. Introduction

Due to the recent developments in communication technologies and microelectronics, Wireless Sensor Networks (WSNs) are capable of conveying high-resolution information processes to a Base Station (BS) [1, 2]. However, the longevity of such networks has become of crucial importance in applications like environment and health monitoring, where WSNs might have to be operational for several years [3, 4]. Therefore one of the most important problems of WSNs stems from the limited energy storage capacity which imposes severe limits on the longevity [5, 6].

The major energy consumption of a sensor node results from the active state of its radio component [7]. Thus, by “sleeping” (i.e., switching off the radio module), one may save a considerable amount of energy [8]. Therefore the lifespan of a wireless network is roughly defined by how often the electricity consuming parts are turned on. In WSN, the physical layer was designed with short radio range to meet the requirement of low energy consumption. As a result, the network frequently relies on multihop communication schemes to the BS but this procedure leads to asymmetry in the energy consumption; nodes close to the BS are forced to be engaged in higher forwarding activity [6]. Existing routing approaches of load and energy balancing employ periodical route changes [9, 10], however, most of the work does not take into account the underlying channel access method. Hence, the proper design of medium access (MAC) gives rise to new challenges and it is intensively researched [8, 11–13]. A large number of research work have proposed low power MAC protocols for multihop WSNs [14–17], which is going to be detailed in Section 2.

In WSN, the reduction of energy consumption must be one of the primary goals in the design, however, collision avoidance capability can also be a crucial metric. To achieve energy efficiency, we need to identify what are the main sources that cause inefficient use of energy as well as what tradeoffs we can make to reduce energy consumption. The following factors have been identified as the most significant ones regarding energy consumption [18].

Collision

When a transmitted packet is not delivered it has to be discarded and the retransmissions increase energy consumption as well as the latency.

Overhearing Overhead

This is due to the fact that a node accidentally picks up packets that are destined to other nodes.

Idle Listening

When the node listens to receive possible packets, which are not sent.

Control Packet Overhead

Sending and receiving control packets.

Plenty of channel access methods are proposed to overcome these drawbacks. There are two common solutions: (i) contention based; (ii) TDMA solutions. In case of contention-based MACs, nodes try to assign the channel themselves competitively. Since nodes do not cooperate, collisions happen and increase energy consumption and latency severely. However, collision can be eliminated by using four handshaking RTS/CTS strategies, the energy overhead is huge due to the extra energy consumption of control packets. Overhearing and idle listening are also typical in contention-based MACs and consume about half of the energy (one can see more details of exact measurements presented in [19]). These distributed protocols are reactive to environment changes, however they do not exploit the topology, routing, and traffic information, which with more efficient channel assignment could be achieved. In case of stochastic traffic pattern, contention-based solutions transmit the data in a very fast manner to the BS, but it still fails to provide energy efficient communication. On the other hand, the fully cooperative TDMA-based solutions communicate on different time slots to prevent conflicts and offer several advantages for data collection as compared to contention-based protocols. They eliminate collisions, overhearing, and idle listening and the network does not suffer from extra energy overhead (i.e., RTS/CTS overhead). Note, that idle listening inherently appears in TDMA systems, since the time slot has to be greater than the packet duration. On the other hand, they also permit nodes to enter into sleep modes during inactive periods, thus, achieving low duty cycles and conserving energy. From the point of quality of service (QoS) TDMA-based communications can provide provable guarantee on the completion time of data collection, for instance, in timely detection of events. On the other hand, TDMA needs tight synchronization and accurate traffic and topology information, which implies extra communication overhead compared to a contention-based MAC.

In this work, we present a novel scheduling algorithm to unite the advantages of TDMA and contention-based protocols, that is, energy-efficient communication with acceptable latency. Namely, we are seeking an energy optimal schedule for a given traffic demand and routing topology, while a given end-to-end latency requirement is satisfied (i.e., the length of the schedule does not exceed a predefined threshold). This gives a cross layer perspective to our work, as the application and the routing information are used to determine the schedule. This cross layer optimization will be carried out by Binary Quadratic Programming (BQP). BQP is a well-known NP-hard problem, but we solve it by the Hopfield neural network (HNN). However, other solvers (e.g., semidefinite relaxation [20]) can also be used.

The rest of this paper is organized as follows: (i) Section 2 discusses the related works; (ii) Section 3 describes the system model; (iii) Section 4 introduces the optimization problem to be solved; (iv) Section 5 presents the HNN to minimize the penalty functions mapped into quadratic programming and realize feasible schedules; (v) Section 6 evaluates the performance by extensive simulations; (vi) some concluding remarks can be found in Section 7.

2. Related Works

In the recent years, a large number of the energy-efficient MAC schemes in the data link layer have been proposed for WSNs in recent years [8, 21]. Current MAC design for WSNs can be broadly divided into two common solutions, contention based and scheduled based (or TDMA protocols).

In the contention-based scheme, nodes try to access the channel randomly, independently from each other, such as ALOHA [22]. ALOHA has been improved in many ways to achieve different performance requirements (e.g., no collision) by using such methods as the four-way handshaking carrier sense multiple access with collision avoidance (CSMA/CA) [23]. In WSN, B-MAC [24] is the most popular example of the contention-based protocol, and it is mainly built on the well-known standardized protocol for wireless ad hoc networks the IEEE 802.11 [25]. The B-MAC protocol reduces idle listening and provides an asynchronous channel access method, however X-MAC [26] and C-MAC [27] made an improvement on it by trying to use shorter preambles and avoid the overhearing among neighboring nodes. Contention-based protocols are very important channel access methods in the case of rare, but bursty traffic, which is the typical in event driven mode.

TDMA-based packet transmission scheduling schemes could be very efficient if the users are known and their number is fix, the data arrives regularly (e.g., every one minutes the temperature value must be delivered to the BS and topology are static). Time-slotted communication is robust during heavy traffic loads while contention-based access protocols may fail to allocate the medium successfully when the data rates and the number of sources are high. The TDMA-based protocols can also save more energy, since each node can stay in sleep mode and wakes up during its own slot time. For these reasons, TDMA has been a subject of extensive research and there are also several TDMA commercial standards and applications [28]. Scheduled or TDMA-based protocols use topology information as a basis of scheduling. Based on tight synchronicity among their neighbors, time slots are scheduled for access in such a way that no two interfering nodes access the channel at the same time. Note that the synchronization method is out of the scope of this paper, however, one must note that clock drifts can cause energy overhead in TDMA systems (i.e., since synchronicity could only be guaranteed only with a certain accuracy, hence receiver must wake up a certain guard time before the sender does). The most popular TDMA-based MAC protocols proposed for WSNs are as follows: S-MAC [29] is one of the standard solution in the TinyOS [30] operating system designed to be used with networked sensors and it supports the Mica2 platform [31]. The S-MAC is a method using loose synchronization and RTS/CTS handshaking which occurs significant energy overhead in case of small packets. Furthermore, the paper [32] proposes SMACS as an energy-efficient interference free TDMA-based protocol. A link is only active (i.e., it consumes energy) in its own slot when a packet is generated to be sent and one frame contains all the slots. Hence time slot assignment is the main component of TDMA protocols in wireless networks. Slot assignment problem is NP hard [28]. In paper [33], the protocols RAND, MNF, and PMNF are proposed which provide heuristic solutions to the slot assignment problem. In [34] authors presents DRAND a distributed version of RAND, which runs fast and efficiently. This slot assignment solution uses constant frame size such as SMACS or SMAC, however, a hybrid protocol Z-MAC [35] protocol contains DRAND and adapts the size of the frame. Static frame size is not optimal because of the asymmetry of the data collection tree and traffic pattern [28]. Figure 1 summarizes the typical frame constructions.

Figure 1

Traditional scheduling solutions of different MAC protocols. The possible active time slot indicates the fact that the node has the right to send (having the time slot) but it has no packet to transmit.

In [36] scheduling for QoS routing is presented, where QoS means that traffic requires a given number of slots per frame in the QoS route and formulates it as a slot shortage problem. This paper proposed a distributive solution for the slot shortage problem, which even works in mobile multihop wireless networks. However the protocol presented in this paper assumes static topology and the primary QoS metric is latency instead of data rate. Goldsmith et al. [37] also uses cross-layer-based optimization perspective as Jurdak et al. [38, 39], however, none of them build energy optimal schedules with respect to a given data collection time.

In the rest of the section we analyze the solutions assuming that the topology and the data collection tree are given. A very good summary of such scheduling algorithms for tree networks can be found in [28]. According to [28], schedules can be optimal in terms of the following performance metrics: (1) energy consumption: the energy consumed by the data gathering operation; (2) schedule length/data collection time: the time duration in which the last generated packet is gathered; (3) latency: the maximum end-to-end latency of data gathering; (4) fairness: a metric to determine whether users or applications are receiving a fair share of system resources. Ukai et al. presented a novel formulation for scheduling in [40], whereas one can find suboptimal schedule by shortest path search algorithm. In [41], Furuta et al. proposed an integer linear programming formulation of the same TDMA scheduling problem, which can be a practical real-time solution for large-scale sensor networks. Goldsmith et al. have also provided very elegant ways to build energy optimal schedule in [42], where the authors analyzed the tradeoff between data collection time (i.e., the schedule length) and energy consumption and proposed a scheduling algorithm which is proven to be energy optimal. Energy optimality is achieved under the condition that sensor nodes should wait for transmission completion of its child nodes. Hence, relay nodes have to only wake up at once, which minimizes the number of switches from sleep mode to active mode. Minimization of this number is crucially important, since (1) transient mode consumes extra energy; (2) guard time affects overhead. Hence, if a node waits for the transmission of its children then it is possible to aggregate the received packets. Thus, no extra energy is consumed by switches from sleep mode to active mode, which also minimizes the listening duration because of guard time. On the other hand, Varaiya et al. minimize schedule length (i.e., the data collection time) with centralized and distributed algorithms, respectively, in [43]. A previous work of Varaiya called PEDAMACS, can be found in [44]. Moreover the TreeMAC protocol [45] arranges schedule in order to maximize the throughput of the network.

In this paper, we define the scheduling problem such as Varaiya did in [43], thus the optimal schedule depends on the number of generated packets and the data collection tree. However, most of the solution only optimizes schedules in terms of minimizing either the schedule length or energy consumption (see Figure 2). We consider both performance metrics in order to strike an optimal trade-off between longevity and QoS. To demonstrate this point, in Figure 2 the energy and the schedule length minimal solutions are presented: (i) scheduling of Goldsmith et al. [42] does not exploit time slots for a given node until each packet arrived from its children; (ii) scheduling of [43] exploits time slots in a parallel way to minimize schedule length, but it suffers from significant energy overhead arisen from the extra on/off switches. In most health monitoring application a given data collection time is given, but energy minimization is still the primary objective. This paper presents a fast data gathering (comparable to [43]) with minimal energy consumption (comparable to [42]). This improvement is achieved from reducing the number of wake-ups using the information of application and routing layer.

Figure 2

Recent scheduling solutions: Goldsmith et al. optimizes for energy consumption, Varaiya et al. optimizes for latency and throughput.

3. The System Model

In this section, we present the system model concerning (i) the basic data collection framework; (ii) the energy model; (iii) the network model; (iv) the interference model.

3.1. The Data Collection Framework

In the case of wireless body-area monitoring network, sensor nodes worn on or implanted in the body continuously gather information about the monitored patient's physiological condition, such as electrocardiogram (ECG), pulse, blood oxygen saturation, skin temperature, blood pressure, and hemodynamic calculator [46]. These important measurements are stored in the local memory buffer of the node until the data is downloaded to the BS, when the patient arrives at a data collection point in a hospital. In this case it is imperative that the sensed data is acquired by the BS in an energy efficient way. This can be ensured by a proper scheduling algorithm. The sensor nodes located at different points on the human body transmit data in a multihop manner to the BS. Note, that both on-body and out-body sensors can be used to relay packets. In order to achieve efficient data transfer only a few protocols are designed specifically for multihop wireless body area network (WBAN) communication. One concern is to minimize the thermal effects of the implanted devices by balancing the traffic over a tree-like topology network.

In this paper, we are interested in developing an optimal scheduling for downloading the data from the low-power body sensors to BS. More specifically, the sensor nodes powered by limited capacity batteries, forward packets to other relay nodes by using a single-transmit and a single-receive antenna. The sensor nodes transmit the sensed information at a constant low power to their parents (i.e., parent node is the one which is selected from the routing table to relay the packet in the next hop) in a time-division manner based on the TDMA scheduling. The time axis is not divided into periodical frame periods such as in the case of [43] illustrated in Figure 2. Instead of using fixed frame size, a node is scheduled based on the routing condition and on the traffic requirements of the applications. For example, if a node has more tasks (sensed information and received packets to relay), then it wakes up more frequently. Based on this information each active time slot with a length of $T_s$ is known to the sensor node. According to our novel packet scheduling scheme the BS decides on the time instant when a given sensor node utilizes the channel for $T_s$ length of time. The proposed scheduling is made available to the nodes by using traditional dissemination protocols, which is detailed in Section 6. In the next subsection the energy model is presented which is based on the specification of Mica2 node with CC1100 transceiver.

3.2. The Energy Model

The target platform is the Berkeley Mica2 node [31] which is one of the most widely used WSN platforms. The platform has an 8 MHz processor, 4 kB of RAM, 128 kB of flash memory, and a 433 MHz wireless radio transceiver. The transfer rate is 38.4 kbps and it is powered by two AA batteries. Parameters related to energy use are listed in Table 1.

Table 1

Time, power and energy consumptions of a Mica2 node.

Operation process	Time	Power cons.	Energy cons.
Sleep	—	90 μW	—
Radio initialization	0.35 ms	18 mW	6.3 μJ
Turn on Radio	1.5 ms	3 mW	4.5 μJ
Switch to RX/TX state	0.25 ms	45 mW	11.25 μJ
Receive 1 byte	0.416 ms	45 mW	18.72 μJ
Transmit 1 byte	0.416 ms	60 mW	24.92 μJ

The slot size has to be greater than the length of packet times the duration needed to transmit/receive a byte plus the guard time. Formally we use the following notation:

$\begin{array}{c}{T}_s>L_p{T}_c,\end{array}$

(1)

where $L_p$ is the number of bytes in a packet (with headers) and $T_c$ is the time to transmit/receive a byte. Because of clock drift the receiver must wake up earlier with the so-called guard time, $T_g$ . Hence,

$\begin{array}{c}{T}_s=T_g+L_p{T}_c.\end{array}$

(2)

Assuming that the default packet size is 28 bytes ( $L_p=28$ ) and the activation time of a sensor is 22 μJ (see Table 1), the following energy consumptions per slot can be derived for the receiver node:

$\begin{array}{c}{E}_{\text{RX}}=\left(22+18.72\left(T_g+L_p\right)\right)\hspace{1em}\mu \text{J},\end{array}$

(3)

and for the transmitter node

$\begin{array}{c}{E}_{\text{TX}}=\left(22+24.92L_p\right)\hspace{1em}\mu \text{J}.\end{array}$

(4)

During the inactive period, no data is exchanged between the sensor nodes. To efficiently save the energy, each sensor node is active during a time slot only when it has packet(s) to send or to receive, otherwise, it is in the sleep state and consumes $E_s\hspace{0.17em}\hspace{0.17em}[\mu \text{J}]=90·T_s$ . For these reasons, if a node has to send Y packets and receive $Y-X$ packets, then the following overall energy is consumed:

$\begin{array}{c}E=Y\cdot E_{\text{TX}}+\left(Y-X\right)\cdot E_{\text{RX}}+\left(K-2Y-X\right)E_s,\end{array}$

(5)

where E is the total energy of the battery, hence K is the maximum lifespan of the network. One can see that the lifespan is basically determined by the traffic load X. In the next subsection the network model is introduced.

3.3. The WSN Model

We assume that the WSN has N static sensor nodes, which are able to transmit packets by using single omnidirectional antennas, and there exists a BS node to collect the data from the sensor nodes. These sensor nodes do not only send their own sensed data but they relay packets generated by other sensor nodes, as well. Each node has a local memory buffer, where the generated or received packets are temporarily stored. The WSN can be represented by a graph $G=(V,E)$ , where $V=\{v_1,v_2,\dots ,v_N\}$ denotes the set of nodes, and E denotes the set of edges referred to the communication links. If $\{v_i,v_j\}\subseteq V$ , the edge $e=(v_i,v_j)\in E$ if and only if $v_j$ is located within the transmission range of $v_i$ . Let us define the adjacency matrix A of graph G (the size of matrix A is $N\times N$ ):

$\begin{array}{c}\mathbf{A}={\left[a_{ij}\right]}_{i,j=1,\dots ,N},\end{array}$

(6)

where

$\begin{array}{c}{a}_{ij}=1,\end{array}$

(7)

if $e=(v_i,v_j)\in E$ . These assumptions entail that all the sensor nodes have the same communication range r, the communication links are symmetrical, and no lossy links are assumed. Hence A is a symmetric matrix and represents the neighborhood information. This neighborhood information can be constructed either by measurements or by using general fading models.

Figure 3 shows a network example, where direct links only exist in limited range. Adjacency matrix of the example in Figure 3 is the following:

$\hspace{0.17em}\hspace{0.17em}\mathit{A}=\left(\begin{array}{ccccccccccc}0& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 1& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 0& 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right).$

(8)

Figure 3

Nodes can only communicate in limited range r.

To collect data a tree is constructed (which the most popular data gathering topology [43, 45]). The data gathering tree is routed at a BS node and each intermediate node collects the data from its children nodes and then forwards the data to its parent node. The routing tree is constructed by running the distributed Bellman-Ford algorithm (such as ESR, DSR). In Figure 4 a typical routing tree is illustrated.

Figure 4

Example of a data collection tree. Nodes forwards the data to its parent node toward BS.

A static routing tree can be represented by a routing matrix with size $N\times N$ :

$\begin{array}{c}\mathit{R}={\left[r_{ij}\right]}_{i,j=1,\dots ,N},\end{array}$

(9)

where

$\begin{array}{c}{r}_{ij}=1,\end{array}$

(10)

if node $v_j$ is the parent of node $v_i$ (i.e., if node $v_i$ sends a packet, it sends to node $v_j$ ). The routing matrix of topology presented in Figure 4 is given as follows:

$\begin{array}{c}\mathit{R}=\left(\begin{array}{ccccccccccc}0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}\right).\end{array}$

(11)

Note that multiple packet transmissions are permitted, however, packet collision or interference has to be avoided.

3.4. The Interference Model

Due to the broadcast nature of the wireless medium, interference or collisions may occur among the nodes within the same transmission range. Two types of interference exist: primary interference and secondary interference [47]. Typical examples of primary interference is sending and receiving or receiving from two different transmitters at the same time slot. Secondary interference occurs when there are two parallel transmissions from different senders to different nodes being in the same collision domain (i.e., one of the transmission disturbs the signal at the receiver of the other transmission). Primary and secondary interferences are to be avoided in our approach. We use the protocol interference model [48] in this paper. In the protocol model, each node $v_i$ has a fixed transmission range d and an interference range D, where $D\ge d$ . For the sake of simplicity let us assume that $D=d$ . In this case, according to the adjacency matrix, we define the interference matrix as follows:

$\begin{array}{c}\mathit{F}={\mathit{A}}^2+\mathit{A}-\mathrm{diag}\left({\mathit{A}}^2+\mathit{A}\right).\end{array}$

(12)

This construction is motivated by the fact that links are defined as follows:

$\begin{array}{c}\mathit{F}={\left[f_{ij}\right]}_{i,j=1,\dots ,N},\end{array}$

(13)

where

$\begin{array}{c}{f}_{ij}=1,\end{array}$

(14)

if node $v_j$ is not allowed to transmit parallel with node $v_i$ .

Figure 5 illustrates the interference domain of a given node. As summary interference can occur during transmission of node 8 (Figure 5) because of the following reasons:

• (i)

the receiver node (3) tries to send at the same time as node 8;

(ii)

a node (e.g., one of 7 or 10) sends packet to the receiver of node 3;

(iii)

a node in the collision domain of the receiver (e.g., 7, 9 or 10) sends packet at the same time, effecting collision at node 3;

(iv)

the sender node disturbs other receivers' collision domain, when another node (e.g., 11) is transmitting.

Figure 5

Collision situations in WSN. Only a few parallel transmission is possible while node 8 is sending a packet.

Note that we make the diagonal element of matrix F zeros to represent that a node does not conflict with itself. We also note that matrix F symmetric, because of the symmetric feature of adjacency matrix. To give an example the interference matrix of topology of Figure 3 is the following:

$\begin{array}{c}\mathit{F}=\left(\begin{array}{ccccccccccc}0& 1& 1& 1& 1& 1& 1& 1& 0& 1& 0\\ 1& 0& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 1& 1& 1& 1& 1\\ 1& 1& 0& 0& 1& 1& 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 0& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 0& 1& 0& 1& 1& 1\\ 0& 0& 1& 0& 0& 0& 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 0& 0& 1& 1& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 1& 1& 1& 0\end{array}\right).\end{array}$

(15)

Let us analyze the 8th row vector:

$\begin{array}{c}{\mathit{F}}_8=\left(\begin{array}{ccccccccccc}1& 0& 1& 0& 0& 0& 1& 0& 1& 1& 1\end{array}\right).\end{array}$

(16)

If the vector contains “1” in a given position then the corresponding node is not allowed to send packet at the same time as node 8 (e.g., 1, 3, 7, 9, 10, 11).

4. The Scheduling Problem

In this section, we formulate the scheduling problem of MAS. In order to do this we need a data structure to represent a schedule.

4.1. Representation of a Schedule

The scheduling is represented by a binary matrix C called scheduling matrix, where

$\begin{array}{c}\mathit{C}\in {\left\{\mathrm{0,1}\right\}}_{N\times L}.\end{array}$

(17)

The number of rows N is equivalent with the number of nodes in the network and L represents the number of time slots during which the data collection must be completed. The element $c_{jk}=1$ if node $v_j$ sends a packet to the receiver defined by the routing tree at time instant k, and 0 otherwise.

A possible schedule is given as follows:

$\begin{array}{c}\mathit{C}=\left(\begin{array}{cccccccc}0& 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 0\\ 1& 1& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\end{array}\right).\end{array}$

(18)

This particular matrix represents a schedule, where the different rows of the matrix define the TX schedule of the radios of the different nodes. Note that the RX schedule is uniquely determined by the scheduling matrix because of the tree topology of the data collection. If a node should send a packet according to the TX schedule then the first packet of the buffer is transmitted. For example, let us analyze the row vector related to node $v_4$ :

$\begin{array}{c}{\mathit{c}}_4=\left(\begin{array}{cccccccc}1& 1& 0& 1& 0& 0& 0& 0\end{array}\right).\end{array}$

(19)

Based on this specific schedule, node $v_4$ transmits packet at time instants 1, 2, and 4 to its parent, where the parent is determined by routing matrix R .

Returning to the challenge, we are seeking an optimal scheduling matrix ${\mathbf{C}}_{\text{opt}}$ of type $N\times L$ , which guarantees interference free transmissions, minimizes the idle wake-ups and the energy consumption. In the case of exhaustive search the number of steps to obtain the solution is $𝒪(2^{NL})$ . Thus, the endeavour is to find a feasible and efficient solution obtained in a much shorter time. To accomplish this objective, first we map the problem and the constraints into an objective function. Having the scheduling problem mapped into a quadratic objective function will let us use fast algorithms developed for quadratic optimization to solve the scheduling problem realtime.

Note that if we choose $L=K$ from (5), we are seeking schedule which is valid for the whole lifespan of the network. If L is too large then the whole problem is broken into smaller sized scheduling problems by choosing the size $L(p)$ as follows:

$\begin{array}{c}L={{\displaystyle \sum }}_{p=1}^{P}L\left(p\right),\end{array}$

(20)

where $L(p)$ is the size of the pth smaller timescale problem.

Based on the discussion above, a WSN network is defined by its adjacency ${\mathit{A}}_{N\times N}$ , routing ${\mathit{R}}_{N\times N}$ , and interference ${\mathit{F}}_{N\times N}$ matrices. Furthermore let matrix ${\mathit{C}}_{N\times L(p)}$ denote the scheduling. In this and following subsections we look for a scheduling matrix, which guarantees feasibility and efficiency in terms of minimizing the following heuristic cost function and penalty functions.

4.2. The Objective Function

In this section we develop the objective function the optimization of which will guarantee the energy efficiency in terms of minimizing the RX/TX switches.

Since activation of the radio needs energy, it is worth selecting a schedule, in which the slots requiring radio activities (sending or receiving) follow each other to avoid frequent activations and deactivations. The following function rewards the situation when the receiver remains awake after an active slot, so the number of on/off switches is minimal by fulfilling the following expression:

$\begin{array}{c}\arg \hspace{0.17em}\underset{\mathit{C}}{\min }{{\displaystyle \sum }}_{j=1}^N\hspace{0.17em}{{\displaystyle \sum }}_{k=1}^{L\left(p\right)-1}\left(c_j\left(k\right)+c_j\left(k+1\right)-2c_j\left(k\right)c_j\left(k+1\right)\right).\end{array}$

(21)

4.3. Penalty Functions

The following penalty functions are developed to guarantee the feasibility and validity of the scheduling matrix C .

4.3.1. Minimizing the Interference

In wireless networks minimizing the interference is equivalent with minimizing the number of collisions. Formally it means the minimization of

$\begin{array}{c}\underset{\mathbf{C}}{\min }{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\mathit{C}\left(k\right)\mathit{F}{\mathit{C}}^T\left(k\right),\end{array}$

(22)

where $\mathit{C}(k)$ denotes the kth column of scheduling matrix C , the schedule corresponding to the time instant k. The quadratic function $\mathit{C}(k)\mathit{F}{\mathit{C}}^T(k)$ gives the number of conflicts at time slot k. If this expression is zero then there is no packet which has collided.

4.3.2. Fulfilling the Transmission Requirements

Let us assume that the number of packets generated at node $v_j$ is denoted by $x_j:x_j\ge 0$ and amount of packets must then be sent during $L(p)$ time slots to the BS from node $v_j$ . Let us denote the number of transmissions needed (sending and forwarding) at node $v_j$ as $s_j\ge x_j$ , where $s_j$ includes not only the sensed data packets but the packets to relay, as well. It is easy to see, that $s_j$ at each node $v_j\in V$ can be easily calculated by Algorithm 1. This algorithm evaluates the traffic state $s_j$ for all j runs from 1 to N.

Algorithm 1: Calculating the traffic vector.

Require: $\mathbf{x},\mathbf{R},L(p)$

  $\mathbf{s},\mathbf{z}\leftarrow \mathbf{x}$

 for $k\leftarrow 1$ to $L(p)$ do

   $\mathbf{z}\leftarrow \mathbf{z}·\mathbf{R}$

   $\mathbf{s}\leftarrow \mathbf{s}+\mathbf{z}$

end for

Therefore $s_j$ has to be equal with the sum of jth row in the scheduling matrix to perform all tasks provided by node $v_j$ . Formally,

$\begin{array}{c}\forall v_j\in V:{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)=s_j.\end{array}$

(23)

This equation can be rewritten as the following minimization problem:

$\begin{array}{c}\underset{\mathit{C}}{\min }{{\displaystyle \sum }}_{j=1}^N\left|s_j-{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right|.\end{array}$

(24)

Instead of using the absolute value let use minimize the following quadratic form:

$\begin{array}{c}\underset{\mathit{C}}{\min }{{\displaystyle \sum }}_{j=1}^N{\left(s_j-{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)}^2.\end{array}$

(25)

Note, that if $L(p)$ is too short then the minimum of (25) can be larger than zero, meaning that the remaining part of the traffic has to be forwarded in the next $L(p+1)$ session (e.g., as new task).

4.3.3. Minimizing the Remaining Number of Packets in the Network

The traffic generated at each sensor node ( $s_j$ ) has to be collected by the BS for all j. It entails that the input and the output traffic in the network have to be the same. A scheduling vector of time instant k is denoted by $\mathit{C}(k)$ which is the kth column vector of the scheduling matrix. Let us denote the buffer state vector in time instant k with $\mathit{z}(k)$ . Note, that multiplying the kth schedule vector and the routing matrix, the buffer state vector at the next time instant can be computed as

$\begin{array}{c}\mathit{z}\left(k+1\right)=\mathit{z}\left(k\right)+{\mathit{C}}^T\left(k\right)\mathit{R}.\end{array}$

(26)

The received vector r at time instant k represents the number of incoming packets and it is $\mathit{z}(k+1)-\mathit{z}(k)={\mathit{C}}^T(k)\mathit{R}$ . It is easy to see, that the number of incoming packets at time instant k at node $v_i$ is

$\begin{array}{c}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right).\end{array}$

(27)

The number of packets sent by a node $v_i$ is

$\begin{array}{c}{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right).\end{array}$

(28)

The number of incoming packets must equal the number of outgoing packet for each node, if

$\begin{array}{c}\forall v_i\in V:x_i+\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)={{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right).\end{array}$

(29)

This can be reformulated as the following optimization task:

$\begin{array}{c}\underset{\mathit{C}}{\min }{{\displaystyle \sum }}_{i=1}^N{\left(x_i+\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)-\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right)\right)\right)}^2.\end{array}$

(30)

4.3.4. Minimizing the Number of Idle Wake-Ups

The previous conditions guarantee that the information generated at sensor nodes arrive at the BS without interference. The penalty function developed in this subsection is to ensure that relay nodes should only wake up if there are packets to forward. This can be guaranteed if

$\begin{array}{c}\hspace{1em}\hspace{1em}\forall v_i\in V,\hspace{1em}\forall l=1\cdots L\left(p\right),\\ \hspace{0.5em}{{\displaystyle \sum }}_{k=1}^l\hspace{0.17em}\left({{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)={{\displaystyle \sum }}_{k=1}^l{\mathit{c}}_i\left(k\right)\end{array}$

(31)

holds for each time instant. Formula (31) can be rewritten as follows:

$\begin{array}{cc}\hfill & \forall l=1\cdots L\left(p\right):\hfill \\ \hfill & \underset{\mathit{C}}{\min }{{\displaystyle \sum }}_{i=1}^N{\left({{\displaystyle \sum }}_{k=1}^l\hspace{0.17em}\left({{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)-{{\displaystyle \sum }}_{k=1}^l{\mathit{c}}_i\left(k\right)\right)}^2.\hfill \end{array}$

(32)

4.4. The Overall Objective Function

If we could minimize the previously defined objective function and four penalty functions simultaneously, then it will yield the scheduling matrix having the following properties:

• (i)

the schedule length is L;

(ii)

all the sensed data packets $x_j$ at each node $v_j$ and incoming packet from other nodes are forwarded toward the BS;

(iii)

schedules do not interfere with each other;

(iv)

a node only wakes up if there is packet to send.

Therefore it is expected that the algorithm minimizing these objectives by minimizing the objective function (21) and the penalty functions (22), (25), (30), (32), can construct feasible and energy-efficient scheduling matrix C . In the next section we transform these optimization tasks into a single quadratic optimization by combining the objective function in an additive manner.

5. Quadratic Programming for Scheduling

Since the number of binary matrices is exponential with the number of nodes multiplied by the length of the schedule, exhaustive search with complexity

$\begin{array}{c}\mathcal{O}\left(2^{N\cdot L\left(p\right)}\right)\end{array}$

(33)

cannot be applied to solve the optimizations derived in the previous section. Thus, our goal is to develop a polynomial time solution by QP as it has been presented in [49–51]. In order to develop this solution let us first summarize the general background of QP.

5.1. Quadratic Programming

Let us assume that matrix W is a symmetric matrix of type $n\times n$ and vector b is of length n. In QP we seek the optimal n dimensional vector y which minimizes the following quadratic function [52]:

$\begin{array}{c}f\left(y\right)=\frac{1}{2}{\mathit{y}}^T\mathit{W}\mathit{y}+{\mathit{b}}^T\mathit{y},\end{array}$

(34)

subject to one or more constraints of the form of

$\begin{array}{c}\mathit{A}\mathit{y}\le \mathit{v},\\ \mathit{B}\mathit{y}=\mathit{u}.\end{array}$

(35)

If QP contains only linear equation constraints then it can be solved as presented in [53]. In other cases, if the matrix W is positive definite, then the function $f(y)$ is convex and the problem can be solved with the ellipsoid method [20]. When W is indefinite the problem is NP hard (for details see in [54]).

A frequently used powerful heuristic algorithm to solve QP is the Hopfield Neural Network (HNN). This neural network is described by the following state transition rule:

$\begin{array}{c}{y}_i\left(k+1\right)=\mathrm{sgn}\left({{\displaystyle \sum }}_{j=1}^N{\widehat{W}}_{ij}y{\left(k\right)}_j-{\widehat{b}}_i\right),\hspace{1em}i={\mathrm{mod}}_{N}k,\end{array}$

(36)

where

$\begin{array}{c}\mathit{d}=-\mathrm{diag}\left(\mathit{W}\right),\\ \widehat{\mathit{W}}=-\mathit{W}-\mathrm{diag}\left(\mathit{d}\right),\\ \widehat{\mathit{b}}=\mathit{b}-\frac{1}{2}\mathit{d}.\end{array}$

(37)

Using the Lyapunov method, authors in [55] proved that HNN converges to its fix point, as a consequence HNN minimizes a quadratic Lyapunov function:

$\begin{array}{c}\mathcal{L}\left(\mathit{y}\right):=-\frac{1}{2}{{\displaystyle \sum }}_{i=1}^N\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\widehat{W}}_{ij}{y}_i{y}_j+{{\displaystyle \sum }}_{i=1}^N{y}_i{\widehat{b}}_i=-\frac{1}{2}{\mathit{y}}^T\widehat{\mathit{W}}\mathit{y}+{\widehat{\mathit{b}}}^T\mathit{y}.\end{array}$

(38)

Thus, HNN is able to solve combinatorial optimization problems in polynomial time under special conditions [56–58]. As a result, one can see that there are quite a number of algorithms which can provide efficient solution to QP. Therefore it motivates us to map the scheduling problem to QP, which is done in the next subsection.

5.2. The Scheduling Problem as QP

First the binary scheduling matrix C is mapped into a binary column vector y as follows:

$\begin{array}{cc}\hfill \mathit{C}& =\left(\begin{array}{cccc}{C}_{11}& C_{12}& \cdots & C_{1L}\\ C_{21}& C_{22}& \cdots & C_{2L}\\ ⋮& ⋮& \ddots & ⋮\\ C_{J1}& C_{J2}& \cdots & C_{JL}\end{array}\right)⟶\hfill \\ \hfill \mathit{y}& ={\left(C_{11},C_{21},\dots ,C_{J1},C_{12},\dots ,C_{J2},C_{1L},\dots ,C_{JL}\right)}^T.\hfill \end{array}$

(39)

The objective function and various penalty functions are transformed into quadratic forms in the next paragraph. Once we have mapped each penalty function into a corresponding quadratic form, then we add them up to form an overall QP which then represents the scheduling problem.

5.2.1. Minimizing the Number of Radio On/Off Switches

The following mapping has to be carried out in order to construct a QP for this objective function:

$\begin{array}{cc}\hfill & {{\displaystyle \sum }}_{j=1}^N\hspace{0.17em}{{\displaystyle \sum }}_{k=1}^{L\left(p\right)-1}\left(c_j\left(k\right)+c_j\left(k+1\right)-2c_j\left(k\right)c_j\left(k+1\right)\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}=\frac{1}{2}{\mathit{y}}^T{\mathit{W}}_O\mathit{y}+{\mathit{b}}_O^T\mathit{y}.\hfill \end{array}$

(40)

Similarly to the previous subsection this construction penalizes the wrong solutions. For example a schedule has to be penalized if a node does not wake up again to transmit or receive after a some preceding radio activity. On the other hand, the schedule is rewarded in the case of the continuous radio activity. The corresponding objective function is described by (21).

Having solved (40) one obtains the following ${\mathit{W}}_O$ matrix and ${\mathit{b}}_O$ vector as follows:

$\begin{array}{c}{\mathit{b}}_O={\left(-0.5,-1,-1,\dots ,-1,-0.5\right)}_{\left(NL\left(p\right)\times 1\right)},\end{array}$

(41)

$\begin{array}{c}\begin{array}{c}{\mathit{W}}_O\end{array}=-\left(\begin{array}{cccccc}{\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}& \cdots & \cdots & {\mathit{0}}_{N\times N}\\ {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}\\ {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}\\ & & \ddots & \ddots & \ddots & \\ {\mathit{0}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}\\ {\mathit{0}}_{N\times N}& \cdots & \cdots & {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}& {\mathit{0}}_{N\times N}\end{array}\right).\end{array}$

(42)

5.2.2. Handling the Interference Constraint

In order to obtain the parameter of QP over binary vector y for the interference constraint, the following equation will yield the corresponding ${\mathit{W}}_A$ and ${\mathit{b}}_A$ :

$\begin{array}{c}{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\mathit{C}\left(k\right)\mathit{F}{\mathit{C}}^T\left(k\right)=\frac{1}{2}{\mathit{y}}^T{\mathit{W}}_A\mathit{y}+{\mathit{b}}_A^T\mathit{y}.\end{array}$

(43)

It is easy to see that

$\begin{array}{c}{\mathit{b}}_A={\mathit{0}}_{NL\left(p\right)\times 1},\end{array}$

(44)

$\begin{array}{c}{\mathit{W}}_A=2\left(\begin{array}{cccc}{\mathit{F}}_{N\times N}& {\mathit{0}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}\\ {\mathit{0}}_{N\times N}& {\mathit{F}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{0}}_{N\times N}& {\mathit{0}}_{N\times N}& \cdots & {\mathit{F}}_{N\times N}\end{array}\right),\end{array}$

(45)

where F is the interference matrix.

5.2.3. Handling the Transmission Requirements

To obtain the parameters of the corresponding QP the following equation has to be solved for ${\mathit{W}}_B$ and ${\mathit{b}}_B$ :

$\begin{array}{c}{{\displaystyle \sum }}_{j=1}^N{\left(s_j-{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)}^2=\frac{1}{2}{\mathit{y}}^T{\mathit{W}}_B\mathit{y}+{\mathit{b}}_B^T\mathit{y},\end{array}$

(46)

where vector y denotes the quantity of packets to be sent in a given time interval $L(p)$ . Let us rewrite the left side of (46) as

$\begin{array}{cc}\hfill & {{\displaystyle \sum }}_{j=1}^N{\left(s_j-{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)}^2\hfill \\ \hfill & \hspace{1em}\hspace{1em}={{\displaystyle \sum }}_{j=1}^N\left(s_j^2+{\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)}^2-2s_j{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}={{\displaystyle \sum }}_{j=1}^N\left(s_j^2\right)+{{\displaystyle \sum }}_{j=1}^N{\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right)}^2-2{{\displaystyle \sum }}_{j=1}^N\left(s_j{{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_j\left(k\right)\right).\hfill \end{array}$

(47)

Note, that ${\sum }_{j=1}^N{s}_j^2$ is constant, which can be neglected from the point of minimization. By solving (46) one obtains

$\begin{array}{c}{\mathit{b}}_B={\left(\mathit{s},\mathit{s},\dots ,\mathit{s}\right)}_{NL\left(p\right)\times 1},\\ {\mathit{W}}_B=2\left(\begin{array}{cccc}{\mathit{I}}_{N\times N}& {\mathit{I}}_{N\times N}& \cdots & {\mathit{I}}_{N\times N}\\ {\mathit{I}}_{N\times N}& {\mathit{I}}_{N\times N}& \cdots & {\mathit{I}}_{N\times N}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{I}}_{N\times N}& {\mathit{I}}_{N\times N}& \cdots & {\mathit{I}}_{N\times N}\end{array}\right),\end{array}$

(48)

where ${\mathit{I}}_{N\times N}$ is the identity matrix.

5.2.4. Handling the Constraint on the Remaining Number of Packets in the Network

Since the incoming traffic must be the same as the outgoing traffic for each node, we have

$\begin{array}{cc}\hfill & {{\displaystyle \sum }}_{i=1}^N{\left(\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)-\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right)\right)\right)}^2\hfill \\ \hfill & \hspace{1em}\hspace{1em}=\frac{1}{2}{\mathit{y}}^T{\mathit{W}}_D\mathit{y}+{\mathit{b}}_D^T\mathit{y}.\hfill \end{array}$

(49)

Let us rewrite the left side of (49):

$\begin{array}{cc}\hfill & {{\displaystyle \sum }}_{i=1}^N{\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)}^2+{{\displaystyle \sum }}_{i=1}^N{\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right)\right)}^2\hfill \\ \hfill & \hspace{1em}\hspace{1em}-2{{\displaystyle \sum }}_{i=1}^N\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}\hspace{0.17em}{{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)\left({{\displaystyle \sum }}_{k=1}^{L\left(p\right)}{\mathit{c}}_i\left(k\right)\right).\hfill \end{array}$

(50)

Evaluating the formula above results in the following quadratic form:

$\begin{array}{c}{\mathit{b}}_C={\mathbf{0}}_{NL\left(p\right)\times 1},\\ {\mathit{W}}_C=2\left(\begin{array}{cccc}{\mathit{P}}_{N\times N}& {\mathit{P}}_{N\times N}& \cdots & {\mathit{P}}_{N\times N}\\ {\mathit{P}}_{N\times N}& {\mathit{P}}_{N\times N}& \cdots & {\mathit{P}}_{N\times N}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{P}}_{N\times N}& {\mathit{P}}_{N\times N}& \cdots & {\mathit{P}}_{N\times N}\end{array}\right),\end{array}$

(51)

where matrix P of type $N\times N$ can be constructed as

$\begin{array}{c}\mathit{P}={\mathit{D}}_C+{\mathit{I}}_{N\times N}-2{\mathit{R}}_{N\times N}.\end{array}$

(52)

Note, that ${\mathit{D}}_C$ is defined in (53).

$\begin{array}{c}{\mathit{D}}_C=\left(\begin{array}{cccc}{\mathit{R}}_{\mathrm{1,1}}^2+{\mathit{R}}_{\mathrm{1,2}}^2+\cdots +{\mathit{R}}_{1,N}^2& {\mathit{R}}_{\mathrm{1,1}}{\mathit{R}}_{\mathrm{2,1}}+\cdots +{\mathit{R}}_{1,N}{\mathit{R}}_{2,N}& \cdots & {\mathit{R}}_{\mathrm{1,1}}{\mathit{R}}_{N,1}+\cdots +{\mathit{R}}_{1,N}{\mathit{R}}_{N,N}\\ {\mathit{R}}_{\mathrm{1,1}}{\mathit{R}}_{\mathrm{2,1}}+{\mathit{R}}_{\mathrm{1,2}}{\mathit{R}}_{\mathrm{2,2}}+\cdots +{\mathit{R}}_{1,N}{\mathit{R}}_{2,N}& {\mathit{R}}_{\mathrm{2,1}}^2+{\mathit{R}}_{\mathrm{2,2}}^2+\cdots +{\mathit{R}}_{2,N}^2& \cdots & {\mathit{R}}_{\mathrm{2,1}}{\mathit{R}}_{N,1}+\cdots +{\mathit{R}}_{2,N}{\mathit{R}}_{N,N}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{R}}_{\mathrm{1,1}}{\mathit{R}}_{N,1}+{\mathit{R}}_{\mathrm{1,2}}{\mathit{R}}_{N,2}+\cdots +{\mathit{R}}_{1,N}{\mathit{R}}_{N,N}& {\mathit{R}}_{\mathrm{2,1}}{\mathit{R}}_{N,1}+{\mathit{R}}_{\mathrm{2,2}}{\mathit{R}}_{N,2}+\cdots +{\mathit{R}}_{2,N}{\mathit{R}}_{N,N}& \cdots & {\mathit{R}}_{N,1}^2+{\mathit{R}}_{N,2}^2+\cdots +{\mathit{R}}_{N,N}^2\end{array}\right).\end{array}$

(53)

5.2.5. Handling the Constraint on Minimizing the Number of Idle Wake-Ups

In order to map this constraint into a quadratic form the following transformation has to be carried out:

$\begin{array}{cc}\hfill \forall l& =1\cdots L\left(p\right):{{\displaystyle \sum }}_{i=1}^N{\left({{\displaystyle \sum }}_{k=1}^l\left({{\displaystyle \sum }}_{j=1}^N{\mathit{c}}_j\left(k\right)\mathit{R}\left(j,i\right)\right)-{{\displaystyle \sum }}_{k=1}^l{\mathit{c}}_i\left(k\right)\right)}^2\hfill \\ \hfill & =\frac{1}{2}{\mathit{y}}^T{\mathit{W}}_D\mathit{y}+{\mathit{b}}_D^T\mathit{y}.\hfill \end{array}$

(54)

In this case we penalize the wrong solutions. In order to solve this equation first let us analyze the traffic vector (i.e., the number of packets waiting in the buffers) at the different time instances. Obviously the traffic vector is $\mathit{z}(0)=\mathit{x}$ at time instant 0. At time instant 1 the traffic vector updated as follows:

$\begin{array}{c}\mathit{z}\left(1\right)=\mathit{x}-\mathit{c}\left(1\right)+{\mathit{c}}^T\left(1\right)\mathit{R}.\end{array}$

(55)

Note, that it is only true if $\mathit{c}(1)$ contains only “1”-s, if there is at least one packet to send. This formula can be evaluated recursively and the traffic vector can be calculated for every time instance. It is easy to see that $\mathit{c}(2)$ has to be penalized if it contains “1” at a location where there is no packets in the buffer. Thus the penalty

$\begin{array}{c}\left(\mathit{1}-\mathit{z}\left(1\right)\right)\mathit{c}\left(2\right)\end{array}$

(56)

is positive if there is no packet at the buffer, but node (2) is waken up. On the other hand, it is negative if there is more than one packet in the buffer. Substituting (55) into (56) we get

$\begin{array}{cc}\hfill & \left(\mathit{1}-\mathit{x}-\mathit{c}\left(1\right)+\mathit{c}{\left(1\right)}^T\mathit{R}\right)\mathit{c}\left(2\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}=\mathit{c}\left(1\right)\left(\mathit{I}-\mathit{R}\right)\mathit{c}\left(2\right)-\left(\mathit{x}-1\right)\mathit{c}\left(2\right).\hfill \end{array}$

(57)

Following this method recursively, we get the matrix of QP defined as

$\begin{array}{c}{\mathit{b}}_D=\left(\mathit{x}-1,\mathit{x}-1,\dots ,\mathit{x}-1\right),\end{array}$

(58)

$\begin{array}{c}{\mathit{W}}_D=2\left({\mathit{D}}_D\cdot {\mathit{D}}_D^T\right),\end{array}$

(59)

where matrix ${\mathit{D}}_D$ of type $NL(p)\times NL(p)$ can be calculated as

$\begin{array}{c}{\mathit{D}}_D=\left(\begin{array}{cccc}{\mathit{I}}_{N\times N}-\mathit{R}& {\mathit{0}}_{N\times N}& \cdots & {\mathit{0}}_{N\times N}\\ {\mathit{0}}_{N\times N}& {\mathit{I}}_{N\times N}-\mathit{R}& \cdots & {\mathit{0}}_{N\times N}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{0}}_{N\times N}& {\mathit{0}}_{N\times N}& \cdots & {\mathit{I}}_{N\times N}-\mathit{R}\end{array}\right).\end{array}$

(60)

5.3. Constructing the Overall QP for the Scheduling Problem

Based on the previously defined quadratic forms belonging to the different objective functions we combine them into an overall objective function as follows:

$\begin{array}{c}\underset{}{\min }\frac{1}{2}{\mathit{y}}^T\mathit{W}\mathit{y}+{\mathit{b}}^T\mathit{y},\end{array}$

(61)

where

$\begin{array}{c}\mathit{W}={\mathit{W}}_O+\alpha {\mathit{W}}_A+\beta {\mathit{W}}_B+\gamma {\mathit{W}}_C+\delta {\mathit{W}}_D,\\ \mathit{b}={\mathit{b}}_O+\alpha {\mathit{b}}_A+\beta {\mathit{b}}_B+\gamma {\mathit{b}}_C+\delta {\mathit{b}}_D.\end{array}$

(62)

Note that, the objectives can be controlled with heuristic constants α, β, γ, δ in order to strike a good tradeoff between the importance of different requirements. Having these quadratic form at hand now we can apply the HNN (described in Section 5.1) to provide an approximate solution to the QP in polynomial time.

In the next section simulation results illustrate the advantages of our novel proposed scheduling algorithm.

6. Performance Evaluation

In this section we evaluate the performance of the novel algorithm and compare it to the traditional solutions.

We use a variety of microbenchmark tests to show how MAS improves channel access functionality. These benchmarks show the throughput and energy consumption of MAS, TreeMAC, PEDAMACS, S-MAC, and UxDMA, protocols developed by Varaiya et al. and Goldsmith et al., respectively. We will demonstrate that there is a tradeoff among throughput, latency, and energy consumptions. The figures obtained from the microbenchmarks empirically characterize the performance of MAS and provides an insight of the expected behavior of the scheduling algorithms in TDMA systems. To illustrate the effectiveness of our centralized scheduling algorithm, we compare MAS to existing MAC protocols, especially with the S-MAC, TreeMAC, protocols developed by Varaiya and Goldsmith and UxDMA-based TDMA protocol.

The protocol developed by Goldsmith et al. [42] minimizes this number and also minimizes the the energy consumption of the nodes in the network, but it provides less throughput. On the other hand the two protocols developed by Varaiya et al. [43] provide relatively high throughput and minimizes the length of schedule, however they are not energy efficient in terms of minimizing the RX/TX switches. We also implemented TreeMAC [45] in order to analyze its throughput, whereas the primary goal was to maximize capacity. Our proposed protocol can achieve high throughput being comparable to protocol developed by Varaiya, on the other hand it works in an energy-efficient manner which extends the lifespan of the corresponding WSN. As a result, we managed to develop an adjustable protocol which provides a good tradeoff between throughput and energy efficiency.

At the last subsection we will summarize the complexity of the algorithms.

6.1. The Simulation Method

Each protocol has been simulated on a large set of traffic and topology parameters, which will characterize the protocol performance empirically. The purpose of these Matlab-based microbenchmarks is to show how the investigated protocols perform with different network topologies.

We simulated TDMA-based protocol variants using time slot assignment method called UxDMA [33]. Three different versions of UxDMA time slot assignment have been implemented. The data payload is the default payload for TinyOS applications; however, the protocols send only packets with length specified by higher level services. When we performed our tests, we used the parameters of Mica2 wireless sensor node to perform our tests (Table 2). All tests performed in an 100 m times 100 m area with nodes with no line-of-sight communication to every other node. The topology of the simulated networks is static, and we used both homogeneous and heterogeneous initial packed load on the sensor nodes. (In case of homogeneous packet load one packet is generated on each sensor node to send. In case of heterogeneous packet loads the initial number of packets are generated in random fashion.)

Table 2

Length of data and control packets used by protocols MAS, UxDMA, and S-MAC.

	MAS	UxDMA	S-MAC
Data Packet Length (bytes)
Preamble	8	8	8
Synchronization	0	0	0
Header	6	6	6
Footer (CRC)	2	2	2
Data Length	26	26	26
Total	42	42	42
Control Packet Length (bytes)
Preamble	8	0	8
Synchronization	0	0	0
Header	6	0	6
Footer (CRC)	2	0	2
Data Length	26	0	6
Total	42	0	18

The multihop data collection trees were obtained by the Bellman-Ford algorithm using hop count as link metric. To determine the number of radio switches of each protocol, we implemented counters in the simulation that kept track of how many times the various operations were performed.

In all cases, we measured the data throughput, schedule length, and number of radio switches of the network. In all tests “packet size” is referring to the size of the data payload without the header information. The overhead attributed to each protocol is shown in Table 2. Note that control packets in S-MAC are less (18 bytes) than in the case of MAS, however, the S-MAC overheads consume energy at every packets. On the other hand MAS produces control overhead to disseminate the actual schedule but it happens less frequently.

The time synchronization of the nodes could be performed by FTSP protocol [59]. This protocol is fast enough and requires only one dissemination cycle by the BS. The dissemination of the schedule tables can be integrated into the FTSP method. The topology and interference discovery we used is similar as Varaiya et al. introduced in [43]. This protocol operates in two phases: (i) first all nodes determine their neighbors and broadcasts their information about the neighbors, (ii) this information reaches the BS then the BS determines the routing matrix, and interference matrix, topology matrix. The amount of packet which have to be scheduled may be included into the previous data messages, therefore with the discovery protocol the BS can acquire information about the number of packet to be scheduled.

In the simulation the synchronization packets, the network topology discovery packets, and schedule control packets of each protocol are neglected (i.e., each solution requires the same amount of packets to keep the nodes' synchronicity and to disseminate actual schedule).

6.2. Throughput

Throughput or channel utilization is one of the most important metrics for MAC protocols which illustrates protocol efficiency. High channel utilization is critical for delivering a large number of packets in a short amount of time. In sensor networks, the speed of data transfer can be important, for example, to detect emergency situations. MAS minimizes the time to send packets as opposed to TDMA systems with fix frame size. MAS also achieves lower contention than the contention-based protocols. In the test we analyze the performance over 100 different network topologies including 30 nodes and the BS collects total number of 30 packets generated from sensor nodes. Each node generates one packet in homogeneous scenario. The throughput of the network was taken as the average of the 100 different simulation results. The throughput achieved by the different protocols is shown in Figures 6 and 7. Whenever the initial packet load is heterogeneous the achieved throughput is better than in case of homogeneous load. One may notice that the TreeMAC protocol falls back due to the enormous number of unused timeslots.

Figure 6

Throughput comparison of the simulated protocols in case of WSN with 30 nodes and homogeneous packet load.

Figure 7

Throughput comparison of the simulated protocols in case of WSN with 30 nodes and heterogeneous packet load.

Varaiya's method gives the best solution as far as the throughput is concerned, however our solution only slightly differs from that that of Varaiya's. One can see that MAS aims to find the optimal solution which has a maximal throughput. In general, better throughput is accomplished with our novel scheduling algorithm: MAS outperforms S-MAC, PEDAMACS, Goldsmith's method, and all variant of the UxDMA-based TDMA protocols. Furthermore, the TreeMAC solution, which is also developed for good throughput, is also outperformed by MAS. S-MAC has a lower channel utilization performance only because of suffering from the overhead of RTS-CTS (Request To Send, Clear To Send) exchanges. Instead of using control messages like RTS-CTS for hidden terminal support, MAS uses a control packet to inform the nodes about the optimal schedule, this control packets also used for synchronizing the nodes. In Figure 8, one can see as the number of nodes increases in the network the performance of MAS converges to performance of Varaiya's protocol. MAS can utilize several times more time slots, than the static frame-based TDMA solutions. The tests demonstrated that channel utilization of MAS is higher than the traditional MAC solutions and also higher from novel distributed solutions.

Figure 8

Throughput comparison of the simulated protocols in the case of different network size, using homogeneous packet load.

6.3. Energy Efficiency

We designed MAS to operate in an energy-efficient manner by minimizing the number of radio on/off and the number TX/RX switches. In the previous subsection we demonstrated that the throughput of MAS is high and now we show that the novel method is also energy efficient. Low duty cycle applications have extremely low network throughput, and vice versa, high-throughput applications need a lot of energy. However, some applications, such as bulk data transfer also need protocols ensuring high throughput with energy efficiency. In this subsection we evaluate the number of radio switches of different protocols in different network scenarios. Figure 9 shows the number of radio switches of the different methods according to the network size.

Figure 9

Number of radio switches in schedule of the simulated protocols in the case of different network size, using homogeneous packet load.

Figure 10 summarizes the overall number of radio switch overhead of the network, whose result is simulated as the average of 100 different scenarios with 30 nodes and one packet on each node. The protocol designed by Goldsmith is the best from this point of view. Both the traditional TDMA and Varaiya's protocol has more energy overhead than Goldsmith's method.

Figure 10

Average number of radio switches in a network containing 30 nodes, using homogeneous packet load.

In case of heterogeneous initial packet load the differences are even bigger. In Figure 11, one can see the number of radio switches of the different protocols. The scenario is the same: 30 nodes and random number of packets packets. The energy efficiency of the MAS protocol is between the methods developed by Varaiya and Goldsmith.

Figure 11

Number of radio switches in schedule of the simulated protocols in the case of different network size—heterogeneous initial packet load.

6.4. Latency

When the MAC protocol is permitted to increase latency, we can reduce the duty cycle of the node and conserve energy. The latency is measured by the total length of schedule.

Result of test for evaluating end-to-end latency can be seen in Figure 12 for homogeneous packet load and in Figure 13 for heterogeneous load. Figure 14 summarizes schedule length differences amongst the tested protocols. MAS protocol has better values for heterogeneous packet load, outperforms the Goldsmith's method and performs as well as the Varaiya's method. Note that in the case of UxDMA, minimization of frame size is the primary objective in order to yield as low latency as possible. However, it is clear from figures that the end-to-end delay is much worse in the case of static frame sized TDMA protocol than in the case of MAS or S-MAC.

Figure 12

Schedule length comparison of the simulated protocols in the case of different network size—homogeneous packet load.

Figure 13

Schedule length comparison of the simulated protocols in the case of different network size—heterogeneous packet load.

Figure 14

Schedule length comparison of the simulated protocols—WSN with 30 nodes.

Based upon the previous test, we have a new protocol which achieves good throughput, minimizes the number of radio switches (and the consumed energy) and has minimal latency as well. It combines the good properties of several protocols.

6.5. Complexity Analysis of the Algorithms

The complexity of the protocols is an important metrics in order to determine how fast we can achieve the scheduling and the corresponding timeslot assignment. Table 3 summarizes the complexity of the investigated protocols. All of tested protocols has polynomial or better complexity, however it is obvious that the novel MAS protocol may be slower than the others.

Table 3

Algorithmic complexity of investigated protocols, where $d_{\max \hspace{0.17em}}$ denotes the maximal degree of nodes in the topology tree.

Method	Complexity
MAS	$𝒪(L^2*N^2)$
SMAC	$𝒪(1)$
TDMA	$𝒪(1)$
RAND	$𝒪(N^2)$ (coloring)
MNF	$𝒪(N^2)$ (coloring)
PMNF	$𝒪(N^2)$ (coloring)
TreeMAC	𝒪(N * Number of levels in topology tree)
PEDAMACS	$𝒪(L*N*d_{\max \hspace{0.17em}})$ + coloring
Varaiya	$𝒪(L*N*d_{\max \hspace{0.17em}})$ + coloring
Goldsmith	$𝒪(L*N*d_{\max \hspace{0.17em}})$

7. Conclusions

We have proposed a novel protocol to provide an optimal scheduling for data collection in Wireless Sensor Networks. The objective was to minimize the number of radio RX/TX switches in order to achieve minimum energy overhead. Other factors, such as (i) achieving interference free communication; (ii) minimizing the number of idle wake-ups; (iii) gathering the specified amount of packets within the given latency constraints, have been taken into account as penalties. Then optimal scheduling has been transformed into quadratic functions, which can then be solved heuristically in polynomial time by using the Hopfield Neural Network. Simulations have demonstrated that the novel MAS protocol minimizes energy consumption and delays. The performance evaluation has shown that the achieved end-to-end latency is as good as either the traditional contention or the traditional scheduled based solutions. On the other hand, MAS consumes less energy by minimizing the number of radio switches. Furthermore, MAS manages to achieve high channel utilization (comparable to Varaiya's method), with low energy consumption (comparable to Goldsmith's method).