Sage Journals: Discover world-class research

Abstract

The distributive nature of wireless sensor networks (WSNs) poses great challenges for the design of distributive scheduling to maximize network life and spatial reuse of time slot with minimum frame length. Most of the existing scheduling techniques are either centralized or contentional. The existing techniques cannot efficiently adapt to the dynamic wireless environment. In this paper, self-scheduled and distributed MAC (SSD-MAC) and self-distributive MAC (SD-MAC) medium access control algorithms are proposed to reduce the complexity and variety of scheduling problems. The proposed algorithms do not require any synchronization and can effectively adapt to dynamic topology changes without incurring global communication overhead. According to the proposed algorithms, each node maps a conflict-free time slot for itself up to 2-hop neighboring nodes. Consequently, each node successfully schedules a unique time slot for itself in a heuristic manner based on its local information. Moreover, the proposed algorithms also guarantee conflict-free edge coloring because all the incident edges to a single node are assigned to colors in such a way that none of the edges should have the same color. It has been demonstrated that, with regard to communication overhead, energy consumption and execution time through simulation proposed that algorithms outperform existing distributed randomized scheduling algorithm (DRAND).

1. Introduction

The progressive nature and exploration in wireless sensor networks (WSNs) have experienced unprecedented development and are considered to be the most preferable medium for communication [1–3]. Nowadays global businesses are mobile and distributed [4]. Consequently, WSNs provide a seamless bridge to permeate the gap between distance and movement. Therefore, the emergence of high data rate, low power consumption, and small sized sensor network applications due to the rapid advancement in microelectromechanical systems (MEMS) has increased the demand for wireless network services [5]. Typically, in WSNs, the sensor nodes are not isolated; rather they are geographically distributed and may significantly vary up to thousands of sensor nodes depending upon the application [6]. Figure 1 shows that each node is capable of sensing environmental variations and responding accordingly to those changes. Each sensor node immediately reacts to the environmental variations and routes the environmental changes to the sink node. Finally, the sink node translates and routes the aggregated data of all of the sensor nodes to the end user via a wireless radio interface [7, 8]. WSNs are envisioned enablers for a wide range of applications, ranging from health monitoring, environmental surveillance, home appliances, industrial process monitoring, and inventory tracking to even providing networking facilities in or around a human body such as in wireless body area networks WBANs [9–11]. WSNs' sensing and monitoring phenomena are as diverse as speed, moisture, temperature, and any particular location by means of optical motion, piezoelectric and thermostat detectors [12, 13]. For all of these applications, a WSN shares some of the common attributes. The sensor nodes are battery powered and have limited power; however, it is infeasible to recharge or replace the battery [14].

Figure 1

Data flow of WSNs from environment to end user.

In WSNs, a common medium is shared for communication. Therefore, simultaneous transmission of conflicting nodes results in a collision. Collisions degrade network performance because it wastes not only the bandwidth of the network but also the power resources of individual devices. After each data collision, packets are retransmitted which creates overhead in terms of extra control packets, energy consumption, and computational time; these are all anomalies that have direct influence on network lifetime. [8, 15, 16]. Moreover, the distributed environment of WSNs with little or no predetermined infrastructure, mobility, lack of bandwidth, and scalability are the issues that affect network performance. In the past, plenty of MAC algorithms were proposed to efficiently utilize system resources and most of them are either contention based or traditional schedule based [17–19]. Moreover, WSNs are distributive, self-configurable, and scalable with little or no predefined infrastructure [20]. WSNs are also highly correlated and may undergo topology changes due to node failures. Thus, traditional scheduling algorithms are not preferable approach in order to ensure fair bandwidth allocation and to handle topology changes in a distributive manner. Therefore, in widespread distributive WSNs, the single, most important challenge of energy-efficient protocols has remained a challenge for the last four decades [21, 22]. This study has investigated the requirement for an innovative medium access control (MAC) to utilize network resources in a more efficient and effective manner by the proliferation of advanced computing devices. It has been observed that the distributed interactions and self-organizing nature of WSNs bring about challenges in predicting the performance of current network technologies. Therefore, to design a large and scalable network, the scheduling algorithms should be computationally distributed as well as simple to resolve contention by providing collision-free scheduling.

In the past, one of the efficient and practical MAC algorithms is the distributed randomized scheduling algorithm (DRAND) [23]. DRAND is the extension of a graph coloring scheme where each node within a two-hop neighborhood is assigned a different color to avoid collisions. Although DRAND is a distributive algorithm, it comes at the cost of an unsuccessful cycle. After each unsuccessful cycle node has to go through many primitive states by exchanging control messages. Thus, the unsuccessful cycle results in extra message overhead, running time, number of rounds, and energy consumption. This research has addressed scheduling techniques and has provided adaptive topology independent and distributed MAC scheduling algorithms to resolve the challenging issues related to scheduling. In this paper novel and heuristic scheduling algorithms are presented which are simple, distributive, and performance optimal. According to the proposed scheduling algorithms each node reserves a conflict-free slot for its transmission in a heuristic manner that has not been reserved by any node in its two-hop neighborhood. The proposed algorithms also overcome some of anomalies such as communication overhead, energy consumption, and execution time that hampers prolonging the network lifetime.

The remainder of the paper is organized as follows. Related work is investigated in Section 2. The proposed system model and problem formulation are given in Section 3. The proposed scheduling algorithms are discussed in detail in Section 4, and simulation results are presented in Section 5. Finally, the paper is concluded in Section 6.

2. Related Work

The part of the overall network functionality known as the medium access control (MAC) protocol handles issues regarding efficiency, fairness, and reliable access to the medium that is simultaneously used by variety of devices [23]. The role of MAC layer protocols in wireless networks is of particular importance as these networks are quite different from their wired counterparts in many ways. MAC protocols for WSN are classified into two main broader categories: contention based and schedule based.

Variations of carrier sense multiple access (CSMA) techniques are utilized in contention-based protocols [25]. With CSMA, the basic characteristic is that the nodes listen to the shared transmission medium of the network before trying to transmit any packet. When a transmission in progress is detected the node will wait for the end of that transmission and only then attempt to transmit its packet [26, 27]. While on the other hand the schedule is based on time-division multiple access (TDMA) [28–31], they conserve energy by making use of both scheduling and reservations. In this way, collision-free communication is guaranteed without the contention-introduced overhead [32]. This is because slots are scheduled for each node. Idle listening is also decreased which results in considerable energy savings [33]. However, making use of a TDMA protocol necessitates that nodes create real communication clusters instead of the virtual ones normally present in CSMA protocols.

There were some drawbacks regarding contention-based and schedule-based techniques. In WSNs, a common medium is shared for communication. Therefore, in contention-based technique the simultaneous transmission of conflicting nodes results in a collision. Collisions degrade network performance because it wastes not only the bandwidth of the network but also the power resources of individual devices. After each data collision, packets are retransmitted which creates overhead in terms of extra control packets, energy consumption, and computational time; these are all anomalies that have a direct influence on network lifetime [8, 15, 16]. While in case of schedule-based technique it is not an easy job to manage intercluster communication and interference job, determining which slot is assigned to which node, determining the high initial overhead when setting up and distributing a schedule for throughout in the WSN, and determining accurate time synchronization that can prevent clock drifts in order to keep the time slots of the nodes from overlapping are some of the challenges when using the TDMA protocol. Furthermore, it is not easy for a TDMA-based protocol to change its schedule without resending overhead packets when the number of nodes in a cluster is altered. Therefore, scalability is better in contention-based protocols. Moreover, the distributed environment of WSNs with little or no predetermined infrastructure, mobility, lack of bandwidth, and scalability are the issues that affect network performance.

Distributed randomized (DRAND) scheduling algorithm is the most famous; it enhances bandwidth utilization by combining the strength of the time-division multiple access (TDMA) MAC and the carrier sense multiple access (CSMA) MAC protocols. It switches between TDMA and CSMA with correspondence to the contention-level in order to use the bandwidth more effectively. In DRAND scheme, nodes are initially in IDLE state and are interested to understudy the medium. The nodes will go through coin toss, with probability of 1/2 getting tails or heads. All the nodes that get heads will go through lottery phase. If a node could not make up in a lottery phase, it will reattempt after $T_{a}$ time to successfully pass through a lottery phase. As shown in Figure 2, node H winning in a lottery phase jumps for REQUEST. In REQUEST state, the node broadcasts REQUEST [26]. If the neighboring nodes of H are in IDLE state, the neighboring nodes will send back GRANT to node H. Actually, GRANT message contains the list of the slots reserved by 2-hop neighbors of H. To provide conflict-free scheduling, the node should be aware of the slots that have been reserved up to their 2-hop neighboring nodes. Thus, node H receives the record of the slots reserved by its 2-hop neighboring nodes through GRANT message. Through the GRANT message, node H will become aware of the slots that have been already reserved by 2-hop neighboring nodes. Finally, node H will reserve a conflict-free slot for itself and broadcast RELEASE message; the RELEASE message contains info about the slot that node H has reserved and gets back to IDLE state.

Figure 2

Successful scheduling cycle of DRAND.

Node H will only receive the GRANT if all the neighboring nodes of node H are in RELEASE or IDLE state [34]. As an example from Figure 3, before receiving a REQUEST from node H, if node F has already granted node I with a GRANT message, in this situation node H will be granted by REJECT message. Actually, the REJECT message means that at moment node F is not in a position to send a GRANT message because it has granted a GRANT message among any of its 2-hop neighboring nodes. When node H receives REJECT message, it has to convey a message to its 1-hop neighboring node that in this particular time it is not reserving any of the slots for itself, so node H broadcasts a FAIL message. After broadcasting a FAIL message node H goes to IDLE state and will later reattempt after $T_{a}$ time. During $T_{a}$ node I schedules its own slot and broadcasts RELEASE. Suppose, node A REQUEST to node F before node H after $T_{a}$ . Here, it states the unsuccessful case of DRAND algorithm because it is unfair with node H; the GRANT should have been granted to node H, which it has requested before node I. Node F will be in a GRANT state and node H will receive a REJECT message from node F. So, all the neighboring nodes of node H upon receiving REJECT message will broadcast FAIL message. Although DRAND algorithm provides solution for distributive scheduling each time after the unsuccessful cycles the nodes have to rebroadcast the extra messages like REQUEST, REJECT, and FAIL. These messages, after unsuccessful cycle, lead to extra message overhead and increase message overhead, latency, and energy consumption.

Figure 3

Unsuccessful scheduling cycle of DRAND.

3. System Model and Problem Formulation

This section consists of two subsections. In Section 3.1, the network model and notations are given for the proposed technique. The interference model is discussed in Section 3.2 for proposed algorithm.

3.1. Network Model and Common Notations

In this paper focus both single-hop and multi-hop in WSNs. N number of sensor nodes were randomly deployed in $A \times A m^{2}$ area and equipped with identical radio transceivers. All the nodes have the same transmission range ( $T R$ ), which helps the nodes to identify the set of nodes in its communication range. Typically, a multihop ( $M H$ ) WSN is represented by a graph $G = (V, E),$ whereas $V = \{v_{1}, v_{2}, v_{3}, v_{4}, \dots, v_{n}\}$ represents the set of nodes in a network and $E = \{e_{1}, e_{2}, e_{3}, e_{4}, \dots, e_{n}\}$ represents the distance (edges) between the links [35]. Nodes u and v are adjacent if both are within TR of each other and their distance is less than Euclidean distance, where $v = (u, v) E V$ and the edge $e = (u, v) E E$ . More generally, the set of links are defined in

\begin{matrix} E = \{(u, v) E V \cdot V | {d i s t}_{E U} (u, v) \leq T R\}, \end{matrix}

(1)

where

{d i s t}_{E U}

is the Euclidean distance.

Definition 1.

Nodes u and v are in a one-hop ( $H 1)$ neighborhood if both u and v are in TR of each other and there exists a link, $(u, v) E E$ . Consider

\begin{matrix} \forall (u, v) E H 1, there  exists  a  link, (u, v) E E . \end{matrix}

(2)

Nodes u and v are in a two-hop

(H 2)

neighborhood if there does not exist a direct link

(u, v) E E

but, alternatively, there exists a link,

(u, w)

(w, v) E E

. Consider

\begin{matrix} \forall (u, v) E H 2, there  exists  a  link, (u, w), (w, v) E E . \end{matrix}

(3)

Similarly, in this case nodes u and v are connected through node w, which plays the role of a bridge between nodes u and v.

For collision-free transmission in WSNs, none of the nodes from $N 2 (u)$ (two-hop neighborhood of node $(u$ )) can schedule the same time slot for itself that has been already reserved by any of the nodes from $N 2 (u)$ , where $N 2 (u) = H 1 (u) \cup H 2 (u)$ . $H 1 (u)$ and $H 2 (u)$ represent the set of nodes in one-hop and two-hop, respectively. $N 2 (u) \supseteq N 1 (u)$ , where $N 1 (u)$ is in the 1-hop neighborhood of node u. Correspondingly, k-hop neighbors of node v can be represented by $Δ_{k} (v)$ , which is a set of all of the sensor nodes whose distance to node v is at most k. Thus, the number of k-hop neighbors of node v is denoted by $δ_{k} (v)$ ; that is, $δ_{k} (v) = |Δ_{k} (v)|$ , and the maximum k-hop neighbors are given as $δ_{k} (v) = \max_{k} δ_{k} (v)$ .

3.2. Interference Model

In WSNs, several sensor nodes in a network are wirelessly linked and equipped with omnidirectional antennas. Due to the broadcast nature of the WSN, if two or more than two sensor nodes within the same transmission range (TR) broadcast simultaneously, this results in collisions. Therefore, each collision makes the node transmit its data again which uses up at least two times the amount of the energy for the same data to be transmitted. Collisions and interference hinder throughput of the network. Generally, there are two types of interference in WSNs: primary interference and secondary interference [28]. Typically, the primary interference occurs when a node in the same time slot is assigned multiple tasks (sending and receiving from multiple transmitters) to be carried out. Secondary interference takes place when parallel transmissions are going on at the same time and in the same collision domain (i.e., nodes are in the interference range) where each destination node is tuned to one particular source node.

In WSNs, each node has a fixed interference range ( $I R$ ) and TR. Conventionally, $I R > T R$ and the ratio between them is $γ = I R / T R$ . Practically, $2 \leq γ \leq 4$ and the transmission will be successful at time τ between $v_{i}$ and $v_{j}$ if none of the nodes $v_{k}$ within the same TR is transmitting at τ. More formally, it can be explained as

\begin{matrix} v_{i} (τ) = \{\begin{cases} 1 & if  none  of  the  nodes  from H 1 (v_{i}), H 2 (v_{i}) is  transmitting  at  time τ \\ 0 & if  any  of  the  nodes  from H 1 (v_{i}), H 2 (v_{i}) are  transmitting  at  time τ . \end{cases} \end{matrix}

(4)

Consequently, the two nodes u and v are adjacent and conflicting, that is, $v E N_{u}$ and $u E N_{v}$ , where $N_{v}$ and $N_{u}$ are neighboring nodes of u and v. The focus of the paper is to tackle the primary and secondary interference by scheduling distributive time slots.

4. The Proposed Scheduling Algorithms

This section consists of four subsections: overview of the proposed work is presented in Section 4.1, the proposed SSD-MAC and SD-MAC are presented in Sections 4.2 and 4.3, respectively, and the proposed slot assignment algorithm is presented in Section 4.4.

4.1. Overview of the Proposed Algorithms

In general, WSNs are distributive, self-configurable, and scalable with little or no predefined infrastructure [20]. WSNs are also highly correlated and may undergo topology changes due to node failures. Therefore, traditional scheduling algorithms are not preferable approach in order to ensure fair bandwidth allocation and to handle topology changes. The approaches adopted in the proposed algorithms are described in detail based on which this research has been carried out. Proposed scheduling algorithms consist of four phases: (1) neighbor discovery, (2) slot scheduling procedure, (3) update procedure, and (4) local framing. Figure 4 presents a sequence wise elucidation of these phases.

Figure 4

Sequence wise elucidation of the phases in the propose algorithms.

In the proposed scheduling algorithms, the nodes are allowed to distributively assign transmission schedules among themselves based on the network composition. Slots are reserved in the setup phase through exchanging the control messages in order to support unicast, multicast, and broadcast transmissions. Furthermore, with the change in a network's topology, the schedules adjust accordingly to maintain conflict-free transmission schedules. Both of the algorithms cope with network topology changes in a distributive and incremental manner. All the nodes in a network equally participate in the scheduling process. The scheduling process is simultaneously executed across the entire network. Each node tries to contend a medium in order to reserve a slot, and several nodes may contend for a medium to acquire a free medium and simultaneously reserve their transmission schedule. Overall, this reduces the network degradation parameters and enhances the robustness. Basically, each sensor node has to maintain its own transmission schedule. That is because, for conflict-free and collision-free transmission, a node can only reserve a slot which is not reserved within its one-hop and two-hop neighbors. If any node in a network suffers a slot confliction due to some topological change, through the attachment or detachment of nodes, the node learns this from the local information and reschedules its own slot to avoid a collision. Due to the local nature of the proposed algorithms, it is neither sensitive to the network size nor affected by the network partition. The proposed algorithms are suitable for large, distributive, and self-configurable WSNs. For the subsequent comparisons with existing DRAND scheduling algorithms, the following assumptions were considered which were similar to that of DRAND, such as (1)

all of the nodes in a network have a unique ID;

(2)

initially, all of the nodes are synchronised at slot 0;

(3)

the network is fully connected and each node is familiar with its $H 1 (u)$ and $H 2 (u)$ ;

(4)

multiple nodes in the same TR cannot communicate at the same time.

4.1.1. Design Consideration

The broadcast nature of WSNs is readily supported by the radio channel. Mostly, sensor nodes are equipped with omnidirectional antennas for broadcast communication, and the packet transmission will be successful if the packet is received by all of the nodes in the TR without any error. For successful transmission, the capture effect of the transmitter has to be observed. When the transmitter broadcasts, it should prohibit and block all of the other communication among its neighboring nodes except for the intended transmitter. The capture effect of the transmitter is complicated and has no information of the nodes beyond its one-hop neighbors (conflicting nodes) which gives rise to hidden terminal problems [24, 36]. Communication can be classified into different categories depending upon designated receivers: unicast, broadcast, and multicast. For the most general case the multicast or broadcast nature of a network can be viewed with an arbitrary subset of neighboring nodes up to a two-hop distance, whereas, in real WSNs, the communication is a combination of both the unicast and the broadcast. Therefore, the available bandwidth should be fairly and distributively shared among the nodes to control and manage all of the activities in a network in a precise manner without any conflict.

Generally, the transmission schedule in WSNs is equivalent to a graph coloring problem, where each time slot is represented by a unique color. The unicast transmission schedule can be represented by edge coloring, whereas the broadcast scheduling can be represented by the node coloring and the multicast scheduling can be represented by multiple edge coloring [37, 38]. The transmission schedule is the combination of edge coloring and node coloring. For optimal scheduling, the conflict-free transmission and coloring constraints must be considered. Optimal scheduling (optimal bandwidth efficiency is measured through the minimum TDMA slots used) is directly or incrementally NP-complete [39]. A force that completely tears down the existing transmission schedules is the change in a network topology because after a topology changes apparently the transmission schedule is regenerated. A new transmission schedule reflects the change in topology and is redundant and costly, when a small portion of a schedule has to be outdated from the existing topology. For schedules, regeneration is evolutionary, or an incremental approach will be a more feasible approach. These approaches are more economical as compared to completely regenerating schedules because only the outdated part is rescheduled, due to node failure or mobility. Due to the self-configuring and dynamic nature of WSNs, distributive scheduling techniques are more preferable to handle scalability and robustness in an efficient manner.

For optimal and rapid schedule updates or regeneration, the focus should be on the local information of the network rather than global information. The transmission of a node can be affected by all of the conflicting nodes up to its two-hop neighboring nodes. Hence, for conflict-free scheduling, it is significant for a node to have knowledge of the nodes up to two-hop neighboring nodes only. The local information is enough to design conflict-free schedules. Recently, hybrid MAC protocols have introduced some of the distributive scheduling algorithms for slot reservation [40–42]. Although the existing scheduling algorithms provide distributive scheduling techniques, the nodes have to repeatedly proceed through many primitive states and a lot of control messages are exchanged. Moreover, these techniques demand more scheduling time which will not be an efficient approach for a more sensitive and speedy network [43]. The anomalies and the drawbacks of the preceding techniques, which are not taken in account, are the motivation of this research with the intention of designing conflict-free scheduling algorithms but the proposed algorithms should also be optimal, scalable, dynamic, and fully distributed conflict-free.

4.1.2. Framework of Proposed Algorithms

The proposed conflict-free MAC scheduling algorithms follow the approach of the DRAND technique; where each time frame is divided into a fixed length depending upon a two-hop neighborhood size. As shown in Figure 5, each frame is further divided into small equal parts known as time slots. The time slot refers to the time required by the sensor node to transmit or receive a message. In the proposed approaches, there is no need for frame alignment at various nodes. In the Figure 5 u, v, and w refer to the nodes in a network with neighborhood size of 3, 8, and 16. Therefore, each node in a time frame reserves a time slot for itself for transmission and reuses that slot for its transmission in each frame. However, the frame size of the nodes may differ depending upon two-hop neighborhood size. Traditionally, most of the MAC scheduling protocols are frame aligned and are time synchronized.

Figure 5

Time frame based on a number of two-hop neighboring nodes for data transmission.

Node failure and movement affect the network topology; therefore, existing scheduling may cause collisions. In order to avoid a collision among all of the conflicting nodes, the proposed scheduling approaches schedule a time slot in such a way that none of the nodes within the two-hop neighborhood is assigned the same slot based on local information in an optimal way. To guarantee conflict-free slot reservation and dynamically adjust to workload more effectively, each node can recycle its time slot in its own frame. The network remains in a setup phase until all of the nodes in a network schedule their conflict-free time slot based on the local information up to a two-hop neighbor record.

In this research work, two distributive scheduling algorithms have been presented with minimal message passing, that is, exchanges of control messages between interfering neighbors. Both of the scheduling algorithms' skeletons have significant difference from each other but the center of attention is the same, where each node has to decide its own conflict-free slot based on local information. In this paper discrete time slots are considered; that is, each node decides its schedule based on local information and reserves a conflict-free time for its transmission time $τ \in Z +$ where τ represents time of any particular slot and Z refers to the time frame. All the conflicting nodes at least up to two-hop neighboring nodes are assigned time step $τ \in Z +$ , for a collision-free transmission. Each node assigns $τ = τ + 1$ based on their neighbors. Hence, to ensure a successful transmission, node i attempts to transmit in its reserved slot at time τ such that none of its neighbors attempt to transmit, simultaneously; that is,

\begin{array}{l} v_{i} (τ) = 1 when  only  node i transmits  at  time τ \\ v_{j} (τ) = 0 none  of  the  neighboring  nodes j \\ \in N (i) (neighbors  of i) is  transmitting  at  time τ . \end{array}

(5)

The appropriate skeleton of these techniques is described in detail in the following sections.

4.2. Self-Scheduled and Distributive MAC Algorithm

Self-scheduled and distributive MAC (SSD-MAC) algorithm is a new scheduling approach that allocates a transmission schedule in a collision-free manner. SSD-MAC provides a distributive scheduling technique as well as obviating the weaknesses of traditional algorithms. SSD-MAC not only resolves scheduling issues but also focuses on trimming down the network degradation parameters as much as possible. In the SSD-MAC, each sensor node collaborates with its $H 1$ and $H 2$ to generate its own transmission schedule. Scheduling through SSD-MAC is simple and based on local information because every node collaborates up to its two-hop neighboring nodes only. Each node directly interacts with its $H 1$ but the nodes apart from that up to $H 2$ cause interference. Nodes, for their transmission schedule in the SSD-MAC, are indirectly aware of the schedules of the nodes up to their $H 2$ and reserve a slot that is not reserved by any of the nodes in their $H 1$ and $H 2$ to avoid a collision. For example, three nodes $(u$ , v, and $w)$ have to schedule their time slot; where $(u, v)$ and $(v, w)$ are in $H 1$ of each other, similarly $(u, w)$ are in $H 2$ . If node u schedules $(S 0)$ for itself, then node v reserves $(S 0 + 1)$ . Similarly, node w reserves $(S 0 + 2)$ to avoid a collision. Nodes, after scheduling their own slot, broadcast this information and the nodes in $H 1$ update this information in their record and later on pass this information to $H 2$ to avoid future conflicts.

Scheduling is always carried out on the basis of existing topology. At the completion of scheduling, neighboring nodes are updated about the schedule. A schedule is modified when a network suffers a collision due to topology changes. Schedules for new nodes are carried out on the basis of local information in such a way that it should not conflict with any of the nodes within its $I R$ . This results in evolving scheduling with the changing topology over time.

4.2.1. Algorithm Description

The idea behind the SSD-MAC is to minimize the chances of unsuccessful cycles because each unsuccessful cycle results in additional computation. In the SSD-MAC, each node decides its own time slot based on the local information gathered by its two-hop neighboring nodes $(N 2)$ . The SSD-MAC algorithm runs in rounds where each node reserves a conflict-free slot in a heuristic manner. The SSD-MAC algorithm runs in parallel and consists of the following two policies: scheduling policy and update policy.

4.2.2. Scheduling Policy

During the scheduling policy, each node reserves a conflict-free time slot in a distributive manner. The SSD-MAC runs in rounds and derives heuristic time slots among all of the nodes in a simpler and more optimal way by avoiding any additional computation. In the SSD-MAC algorithm, at the beginning, all of the nodes are in the IDLE state and each node competes to schedule a conflict-free slot. Each node, for the first time, has to proceed through a coin toss and lottery phase as explained in the DRAND technique. If the node successfully passes the coin toss and lottery phase, then it reserves the minimum unassigned slots among its $H 1 (u)$ and $H 2 (u)$ . Figure 6(a), shows the slot assignment procedure of the SSD-MAC in which, initially, node I successfully proceeds through the coin toss and lottery phase to broadcast a REQUEST message to the entire $H 1 (I)$ . If all $H 1 (I)$ are in the IDLE or RELEASE state, they will reply with a GRANT message. After sending a GRANT message, $H 1 (I)$ waits for the RELEASE message of node I to reserve a slot. As shown in Figure 6(b), if at the same time node H and then node A come in with a REQUEST message, node F will not send a REJECT message to nodes H and A as in the DRAND case; instead of a REJECT message, it will reply with a WAIT message. Actually, the WAIT message is an indication for nodes H and A that node F is aware of their REQUEST and has maintained them in its QUEUE. So, there is no need to send a REQUEST message repeatedly as when node F receives a RELEASE message from node I, it will send a GRANT message to the nodes among the priority of its QUEUE. As shown in Figure 6(c), first node F will send a GRANT message to node H and then to node A.

Figure 6

Slot assignments procedure in SSD-MAC.

4.2.3. Update Policy

The update policy is executed in parallel along with the scheduling policy to minimize the additional computation. In the update policy, each node maintains a record of $S 1$ (where $S 1$ represents the slot reserved in $H 1$ ) through the RELEASE message. The RELEASE message has information of $S 1$ . In order to reserve a conflict-free time slot, each node must have information of $S 1$ and $S 2$ (where $S 2$ represents the slot reserved by $H 2$ ) where $S 2$ is achieved through the GRANT message. Node I, after getting heads and winning the lottery, broadcasts a REQUEST message to get the update about $S 2 (I)$ . In response, node $H 1 (I)$ will reply with a GRANT message which has the information of $S 2 (I)$ . Node I will go through $S 1 (I)$ and $S 2 (I)$ and finally reserve the minimum unassigned slots in $N 2 (I)$ ; if, at the same time, nodes H and A come on with a REQUEST message, node F will send a WAIT message to both of them and record their REQUEST in the WAIT queue. Each node is assigned a WAIT message and as soon as node F gets a RELEASE message from node I, it will send a GRANT message to nodes H and A based on the priority of the WAIT message.

4.3. Self-Distributive MAC Scheduling Algorithm

In self-distributive MAC scheduling (SD-MAC) algorithm, sensor nodes do not collaborate with their $H 1$ and $H 2$ for scheduling their schedule; each node instead maintains and generates its own transmission schedule based on its own record. The scheduling in the SD-MAC is trivial because each node maintains a record of its neighboring node schedule in the $H 1$ and $H 2$ queue. Finally, when a node schedules its own slot it has to look up to its own record rather than requesting its neighboring nodes and reserves or proposes the slot which is not reserved by any of the nodes in the $H 1$ and $H 2$ queue. Scheduling through the SD-MAC is based on local information because none of the nodes is aware of the entire network transmission schedule or size.

Scheduling in SD-MAC is also carried out on the basis of the existing topology. After the scheduling, the neighboring nodes are updated about the schedule. Whenever a network suffers topology in a network the schedule is regenerated in the affected part of the network. Schedules for new nodes are carried out on the basis of local information in such a way that it should not collide with any of the nodes within its $I R .$ This results in evolving scheduling with the changing topology over time. A description of the SD-MAC is illustrated in the next section.

4.3.1. Algorithm Specification

The main focus of SD-MAC is to overcome and tackle the disadvantages of DRAND. According to SD-MAC scheme each node decides its own schedule based on local information, rather depending on neighboring nodes to transmit a REQUEST message. Actually, the local information contains some valuable attributes of the nodes in 1-hop and 2-hop neighboring nodes such as their IDs, slots reserved, distance, and schedule. The SD-MAC runs and consists of the following procedures: slot scheduling procedure and update procedure.

4.3.2. Slot Scheduling Procedure

According to SD-MAC, all of the nodes at the beginning are in the IDLE state. All the nodes contend in order to schedule collision-free slot. Therefore, all the nodes are supposed to follow the coin toss and lottery phase as that of SSD-MAC. The node, which successfully wins the lottery, moves to PROPOSE state. In this state, the node reserves minimum unassigned slots for itself among its 2-hop neighboring record. In the SD-MAC algorithm, each node maintains its own record and reserves a slot based on it, instead of waiting for GRANT message upon each REQUEST message as in DRAND. In DRAND the REQUEST, GRANT, RELEASE, REJECT, and FAIL messages incur high energy consumption, latency, and less probability of reserving a particular slot. The DRAND drawbacks are the motivation of this research work. Lastly, in SD-MAC the neighboring nodes are updated about the record by update procedure.

4.3.3. Update Procedure

From Figure 7(a), it is shown that node H tries to schedule a slot for itself; here it goes to reserve slot (0); that is, $S (H) = \{0\}$ (S represents the slot). After reserving slot (0), node H broadcasts the “PROPOSE” message. The “PROPOSE” message contains the information of the node that any of the nodes in 1-hop has schedule slot; all the node in $H 1 (H)$ will update their record for 1-hop neighboring nodes; that is, $H 1 (F) = {H}$ and $S 1 (F) = (0)$ . After update record for 1-hop, node F will lead this information to 2-hop of node H through broadcasting the “ACCEPT” message. All the nodes receive the “ACCEPT” message, make sure that there is a node in their 2-hop that has reserved slot S2 (0). The scheduling through SD-MAC is very simple, because when any of the contends to schedule slot, it has to look up its own $H 1 (u)$ , $S 1 (u)$ , $H 2 (u)$ , and $S 2 (u)$ record. From Figure 7(b), it is shown that when node I tries to schedule its slot, it will simply look up to its $H 1 (I)$ , $S 1 (I)$ , $H 2 (I)$ , and $S 2 (I)$ and will schedule minimum unassigned slots which do not exist in its record. After scheduling its slot, the “PROPOSE” and “ACCEPT” messages will broadcast and update the record in $H 1$ and $H 2$ .

Figure 7

SD-MAC scheme.

4.4. Slot Assignment by Proposed Algorithms

According to the proposed algorithms, each node reserves its own slot within a frame based on its $H 2$ neighboring nodes. The proposed algorithms allow the network to adapt to the changes in topology by resizing the time frame based on the $H 2$ neighboring nodes. Figure 8 shows the slot assignment achieved for topology in Figure 9 through the proposed algorithms and it can be seen that none of the nodes have assigned the same slot as that of the nodes in $N 2$ . Here, the time frame in the proposed algorithms is based on local information rather than global information. The adaptation of proposed algorithms has been able to break down the whole frame into small portions and the nodes with less numbers of $H 2$ can reuse their slot $S_{i}$ (slot) in $L_{u}$ (frame length), that is, ${l * L}_{i} + S_{i}$ where $l = 1,2, 3, \dots, n$ . This reuse of slots in a frame reduces the delay and increases the concurrency in the channel usage.

Figure 8

Topology description of scheduling in SD-MAC and SSD-MAC.

Figure 9

Slot assignments through the SD-MAC and SSD-MAC algorithms.

5. Performance Metrics/Parameters and Evaluation of Results

The section presents comprehensive qualitative evaluation of existing and proposed algorithms. The main focus of this research is to indicate the network performance measured in a distributive manner. For better performance evaluation of the proposed and the exiting algorithms were simulated in network simulator (NS-2). Furthermore, the subsequent comparisons metrics followed by results give clear image of relative performance of the algorithms obtained through simulation based on the parameters introduced. Simulation scenario enables predicting the significant perspective concerning the validation of algorithms. Firstly, the performance of the proposed SSD-MAC scheduling algorithm was compared to DRAND in terms of all the important parameters at MAC layer. Secondly, the second proposed algorithm SD-MAC was compared to DRAND technique. Finally, for the subsequent comparisons all the three techniques were compared. The results are compared in terms of running time, message overhead, energy consumption, and number of rounds.

Scheduling is carried out during setup phase; therefore, the setup parameters are measured during setup phase until the network reaches steady state. The algorithms were tested by configuring various network topologies with increasing number of nodes in the network. For a simulation scenario, the network topology was varied by randomly deploying sensor nodes on a 1 $50 m \times 150 m$ surface area. Whereas the TR of all the nodes was kept constant at 40 m with a link capacity of 2 Mbps, the network density was increased by varying the number of nodes from 10 to 70. The results reported in next section were obtained after 10 repetitions of trials. Table 1 shows the current and power consumption rate of CC1101 radio transceiver [44] in each mode. Power consumption is achieved simply by multiplying current with battery voltage used. Further, energy consumption in each state can be computed by power consumed by a sensor node in that particular state to the proportions of time that node spends in that state. Therefore, the total power and energy consumption will be the sum of powers and energies consumed by the network in each mode of operation.

Table 1

Current and power consumption rates of CC1101 radio transceivers [24].

Node state	Current (I)	Power ( $P = V I$ )
Transmitting (at 0 dBm)	16.8 mA	50.40 mW
Receiving	18.3 mA	54.9 mW
Listening	1.8 mA	5.4 mw
Sleeping	0.0004 mA	0.0012 mW

Performance evaluation of SSD-MAC and SD-MAC has been conducted to show that the proposed algorithms are optimal, topology independent, and simple in terms of implementation. The parameters used for the simulations are listed in Table 2. In WSNs, beacon messages are periodically exchanged among the neighbors to establish link connectivity and select the best route to forward the data packet. Nodes, in WSNs, are battery powered and wireless linked; therefore the connectivity of links is too volatile because the low power radio of WSNs is vulnerable due to interference from other higher power radio [45, 46]. Additionally, mobility makes it far more difficult to maintain the link connectivity and estimate the best route [47]. Thus, to estimate the best neighbor information is of great significance. Therefore, in this work TwoRayGround is selected as propagation model because it gives the best neighboring information with minimum overhead and energy consumption [48, 49]. The power consumption reported in the table is acquired from the standard CC1101 radio transceiver [44]. The CC1101 provides functions for PHY layer and MAC layer, and its radio operates at low power, which results in reliable wireless communication. Besides this, the radio also supports multiple data rate, power consumption, and channels [50]. For a simulation scenario, the network topology was varied by randomly deploying sensor nodes on a 1 $50 m \times 150 m$ surface area. Whereas the TR of all the nodes was set at 40 m. Bandwidth and data rate are set to be the same that are equal to 250 kHz and 250 kbps, respectively. The data rate 250 kbps is the one rate offered by CC1101 radio transceiver. From the data rate and packets lengths transmission time can be easily computed which will be further used to compute the energy dissipation in each state of mode. The network density was increased by varying the number of nodes from 5 to 70. The simulation time is set to 700 s, and the initial energy of each node was set to 100 Joule. The simulations were repeated for 15 times and the results reported were obtained after 15 repetitions of trials.

Table 2

Simulation parameters.

Parameters	Values
PHY parameters
Number of nodes	05–70
Simulation area	150 m ∗ 150 m
Transmission range	40 m
Sensor node deployment	Random Deployment
Sensor node transmit power	1 mW
Propagation model	TwoRayGround
Packet size (REQUEST, GRANT, RELEASE)	50 byte
Bandwidth	250 kHz
Data rate	250 kbps
Packet reception-power threshold	−60 dBm

TwoRay propagation model
Tx and Rx antenna gain	1
Lambda	0.3279 m

Simulation parameters
Initial energy	100 J
Simulation time	700 sec

5.1. Results for SSD-MAC

The proposed SSD-MAC provided a distributive scheduling technique as well as obviating the weaknesses of traditional algorithms. In proportion to the slot assignment opportunities, the SSD-MAC also focused on trimming down the network degradation parameters as much as possible. SSD-MAC minimized the chances of unsuccessful cycles because each unsuccessful cycle would result in additional computation. In SSD-MAC, each node decided its own time slot based on the local information gathered by its $N 2$ neighboring nodes. The SSD-MAC algorithm ran in rounds where each node reserved a conflict-free slot in a heuristic manner. In the SSD-MAC simulation scenario, at the beginning, all the nodes were in the IDLE state and each node competes to schedule a conflict-free slot. If a node successfully passed the coin toss and lottery phase, then the whole cycle was successful. The nodes that passed through the coin toss and lottery phase got either a GRANT message immediately after the time of the REQUEST or were granted a WAIT message to ensure that the GRANT message would be given on the basis of priority and wait. Finally, the number of rounds, messages, execution time, and energy dissipated were incremented after each round.

Number of rounds refers to the cycles that a node utilizes to acquire its slot. The SSD-MAC and DRAND both run in rounds and each node decides its time slot during the rounds. Each node up to two-hop neighbor assigns a unique time slot for itself to carry out further operations within its own slot only. From Figure 10, it can be observed that SSD-MAC technique results in smaller number of rounds to achieve scheduling task as compared to DRAND. This advantage comes from the adaptation of an improved scheduling technique that results in less number of rounds to accomplish the scheduling task. The scheduling control packets are exchanged during slot reservation. In initialization or the setup phase, excessive numbers of control messages are exchanged by handshaking and scheduling among the neighbors. The control messages also consume network resources and most of the energy is consumed through unnecessary messages transmission. In order to conserve energy, the scheduling algorithm should have low communication overhead. Figure 11 shows the average number of messages exchanged in the SSD-MAC and DRAND techniques during the scheduling process. The proposed technique temporarily stores the information of the node that has REQUEST for the GRANT to a node whose state was not IDLE or RELEASE. Later on, GRANT message is sent to the node based on priority. It has been found that, for higher network sizes, the average number of message-transmissions of SSD-MAC is much lower than DRAND. This is achieved by avoiding unnecessary cycle, which results in retransmissions of extra control message. After each unsuccessful cycle, each node has to go through a number of primitive states and message exchange, which results in higher communication message overhead.

Figure 10

Number of rounds to acquire a time slot.

Figure 11

Messages exchanged during slot reservation.

Collision, idle listening, overhead, and overhearing are the major sources of energy wastage and have direct impact on network life time. Network energy resources are consumed during set-up and transmission phase. The energy consumption during transmission phase can be reduced by avoiding collision and idle listening among all the conflicting nodes which can be achieved during set-up phase. However, the ultimate goal of the proposed technique is to assign conflict-free slots among all the neighboring nodes while consuming minimum energy. In WSNs, most of the energy is consumed by radio transceivers rather than calculation or code execution as both the techniques, SSD-MAC and DRAND, run in rounds and have to pass through many primitive operations that is (idle listening, receiving, and transmitting). From Figure 12, it has been found that SSD-MAC has much lower energy consumption as compared to DRAND due to lower communication overhead by avoiding unsuccessful cycles. After every unsuccessful cycle each node repeatedly exchanges control messages with its neighbors to reserve a slot which results in extra energy consumption. Run time refers to the time that a node requires to schedule a collision-free time slot. Figure 13 shows the average run time utilized for acquiring a time slot with an increasing number of nodes. It can be observed that the scheduling duration of both SSD-MAC and DRAND is nearly the same up to 20 nodes in a network. As the network becomes much denser, the scheduling process becomes more complicated and the run time of SSD-MAC outperforms DRAND. Thus, this illustrates that SSD-MAC avoids unsuccessful cycles because after each unsuccessful cycle extra time is required to carry out scheduling task.

Figure 12

Average energy consumption per node during slot assignment.

Figure 13

Run time during slot assignment.

5.2. Results for SD-MAC

DRAND has overcome shortcomings of existing algorithms, but still there are some drawbacks in the DRAND scheduling technique because the unsuccessful cycle of DRAND leads to message overhead, energy consumption, and computational time. To overcome the drawbacks of DRAND, Self-distributed scheduling MAC algorithm has been introduced. SSD-MAC is a new and independent scheduling algorithm where each node is capable of scheduling its own slot. The SD-MAC is much more improved technique compared to DRAND and SSD-MAC. According to SD-MAC, all nodes in the network are initially in the IDLE state. Each node attempts to schedule a conflict-free slot. Therefore, all the nodes have to go through coin toss and lottery phase. If a node wins the lottery, it will move to the PROPOSE state. In the PROPOSE state, the node schedules the minimum numbered unassigned slot for itself based on its $H 1 (u)$ and $H 2 (u)$ neighboring record. In the SD-MAC algorithm, to schedule a slot, each node just looks up its 1-hop record instead of depending upon GRANT message. SD-MAC provides better scheduling technique and also has some prominent distinguished feature from traditional scheduling algorithms: the SD-MAC provides local transmission schedule and can easily cope with the topology changes (addition/removal of nodes) with minimum message overhead. In SD-MAC the transmissions schedule is executed dynamically; as a result, it may efficiently adjust to workload more as compared to traditional TDMA algorithms. The SD-MAC requires less memory resources and low message overhead, runtime, and energy consumption which makes it more suitable for resource constrained devices.

Figure 14 shows the relation among number of rounds required to schedule slots in a distributive manner with varying topology. From simulation results, it can be seen that the DRAND results in more numbers of rounds as compared to the SD-MAC. This is due to the cost of unsuccessful cycles in DRAND scheme. The unsuccessful cycle occurs at the following events upon unscheduled node: (1) none of the nodes win the coin toss; (2) none of the node successfully pass through the lottery phase; (3) if any node receives from 1-hop send back REJECT message. While in the SD-MAC there is no concept of unsuccessful cycle except for nodes unable to win a coin toss and a lottery phase. The advantage in SD-MAC comes from the adaptation of new distributive scheduling method that tackles the slot scheduling with minimum number of rounds and message. In the SD-MAC nodes are not dependent on REQUEST, GRANT, RELEASE, FAIL, and REJECT messages; instead each node is capable of scheduling its own slot based on local record. This results in fewer rounds. Actually, to schedule a slot control packets are exchanged. Control packets utilize network resources such as network bandwidth, energy, and time. Therefore control messages are considered as overhead. Figure 15 shows message overhead during the scheduling process. It results in smaller number of messages overhead as compared to DRAND. The SD-MAC provides local transmission schedule and can easily cope with the topology changes (addition/removal of nodes) with minimum message overhead. After each unsuccessful cycle, nodes have to go through a number of primitive states which results in excessive amount of message overhead.

Figure 14

Number of rounds to acquire a slot.

Figure 15

Messages exchanged during slot reservation.

Run time refers to the time that a node requires to schedule a collision-free time slot. Figure 16 shows the average run time utilized for acquiring a time slot with an increasing number of nodes. It can be observed that the scheduling duration of both SSD-MAC and DRAND is nearly the same up to a 20 neighborhood size. As the network becomes much denser, the scheduling process becomes more complicated and the run time of SSD-MAC outperforms DRAND. Thus, this illustrates that SSD-MAC avoids unsuccessful cycles because after each unsuccessful cycle extra time is required to carry out scheduling task. This section shows energy consumed by nodes during slot reservation. The SD-MAC runs in rounds like DRAND. All the nodes in the network have to go through the primitive operations such as: transmitting a byte, receiving a byte, idle listening, and sleeping mode. Therefore, the total energy consumed within the network by a node will be the sum of all these primitive operations. Figure 17 shows the energy consumed during slot scheduling process by varying network size. It is shown in the figure that the energy consumption in SD-MAC is lesser than DRAND; this is achieved through avoiding unnecessary message, because extra messages consumes energy and degrades networks resources. From the last figure it is found that the message overhead of DRAND is much higher than SD-MAC. Accordingly, in DRAND scheduling scheme each node has to go through extra number of primitive operations. Therefore, the extra number of messages that consumes extra energy is evident that DRAND algorithm consumes more energy than the SD-MAC.

Figure 16

Execution time during scheduling process.

Figure 17

Energy consumed during the scheduling process.

5.3. Comparative Analysis of Proposed and Current Algorithm

The results reported in Figure 18 were obtained after 15 repetitions of trials. From Figure 18(a), it can be observed that SSD-MAC and SD-MAC both result in smaller number of rounds to achieve scheduling task as compared to DRAND. This advantage comes from the adaptation of an improved scheduling technique that results in small number of rounds to accomplish the scheduling task. Figure 18(b) show the average number of messages exchanged in the SSD-MAC and SD-MAC as compared to DRAND techniques during the scheduling process. The SSD-MAC technique temporary stores the information of the node that has REQUEST for the GRANT to a node whose state was not IDLE or RELEASE. Later on GRANT message is sent to the node base on priority. While in case of SD-MAC there is no concept of REQUEST, GRANT, RELEASE, FAIL, and REJECT messages, in SD-MAC each node has to just exchange only two messages, the PROPOSE and ACCEPT messages, for their scheduling.

Figure 18

Control messages, number of rounds, run time, and energy of SSD-MAC and SD-MAC as compared to DRAND algorithm.

Figure 18(c) shows the average run time utilized for acquiring a time slot with an increasing number of nodes. It can be observed that as the network becomes much denser, the scheduling process becomes more complicated and the run time of SSD-MAC and SD-MAC outperforms DRAND. Thus, this illustrates that SSD-MAC and SD-MAC avoid unsuccessful cycles and also trim down the number of messages which require more time to accomplish scheduling task. Finally, Figure 18(d) shows the relation of energy consumed in SSD-MAC and SD-MAC technique as compared to DRAND during slot scheduling. It is found that the SSD-MAC and SD-MAC energy consumption is much less than DRAND; this is due to avoiding unnecessary message overhead, which consumes extra energy. It is clear from the cumulative results of three techniques from Figure 18 that both the proposed algorithms outperform DRAND.

6. Conclusion and Future Work

In this paper, two new distributive and interference-free scheduling algorithms for WSNs have been introduced. Both the SSD-MAC and the SD-MAC scheduling algorithms were designed and implemented to introduce new distributive scheduling TDMA techniques in distributive and self-organizing WSNs. The major contribution of this work is to resolve challenging issues related to scheduling in order to reduce the complexity and variety of scheduling problems. The SSD-MAC and SD-MAC both do not require any synchronization and can effectively adapt to dynamic topology changes without incurring global communication overhead. The SSD-MAC and SD-MAC techniques enhance DRAND through minimizing the chances of unsuccessful cycle. The entire network scheduling through the SSD-MAC and SD-MAC is simple and local because every node collaborates up to its two-hop neighboring nodes only. It is found that SD-MAC and SSD-MAC not only outperform the existing DRAND technique but also obviate its weakness by avoiding unsuccessful cycles. Moreover, it can be easily illustrated through simulation results and performance metrics that SD-MAC and SSD-MAC achieve better performance than DRAND in terms of number of rounds, message complexity, run time, and energy consumption. In addition, both are distributive techniques and are robust against any dynamic change without incurring extra message overhead. Finally, the proposed algorithms utilize minimal resources to provide optimal collision-free scheduling by reducing all the network degradation parameters.

Based on the work carried out in this paper, for future direction, an entire protocol can be introduce at network layer to accomplish energy efficiency during setup phase and communication phase.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This paper was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University, under Grant no. 611-797-D1435. The authors, therefore, acknowledge with thanks DSR technical and financial support.

References

Ahmed

A. A.

Shi

Shang

A survery on network protocols for wireless sensor networks

Proceedings of the International Conference on Information Technology: Research and Education (ITRE ′03)

August 2003

301 305

10.1109/itre.2003.1270626

2-s2.0-84893905141

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 105

10.1109/mcom.2002.1024422

2-s2.0-0036688074

Tahir

Aldabagh

Abbas

M. D.

Bakhsh

S. T.

Hybrid congestion sharing and route repairing protocol for bluetooth networks

Proceedings of the IEEE International Conference on Electronics, Signal Processing and Communication Systems

2013

33 39

Subhan

Hasbullah

Rozyyev

Bakhsh

S. T.

Indoor positioning in Bluetooth networks using fingerprinting and lateration approach

Proceedings of the International Conference on Information Science and Applications (ICISA ′11)

April 2011

IEEE

1 9

10.1109/icisa.2011.5772436

2-s2.0-79960260541

Sheikh

M. A.

Drieberg

Ali

N. B. Z.

Fair scheduling algorithm for wireless sensor networks

Proceedings of the National Postgraduate Conference (NPC ′11)

September 2011

1 5

10.1109/natpc.2011.6136436

2-s2.0-84857087298

Sheikh

M. A.

Drieberg

Ali

N. B. Z.

An improved distributed scheduling algorithm for wireless sensor networks

Proceedings of the 4th International Conference on Intelligent and Advanced Systems (ICIAS ′12)

June 2012

274 279

10.1109/icias.2012.6306201

2-s2.0-84867957610

Sharma

Mandal

P. S.

Reconstruction of aggregation tree in spite of faulty nodes in wireless sensor networks

Proceedings of the 6th International Conference Wireless Communication and Sensor Networks (WCSN ′10)

2010

1 5

Jianzhong

Making aggregation scheduling usable in wireless sensor networks: an opportunistic approach

Proceedings of the IEEE 8th International Conference Mobile Ad Hoc and Sensor Systems (MASS ′11)

October 2011

666 671

Brandl

Grabner

Kellner

Seifert

Nicolics

Grabner

A low-cost wireless sensor system and its application in dental retainers

IEEE Sensors Journal 2009 9 3 255 262

10.1109/jsen.2008.2012205

2-s2.0-67650305684

10.

Galluccio

Melodia

Palazzo

Santagati

G. E.

Challenges and implications of using ultrasonic communications in intra-body area networks

Proceedings of the 9th Annual Conference on Wireless On-Demand Network Systems and Services (WONS ′12)

January 2012

182 189

10.1109/wons.2012.6152227

2-s2.0-84857890442

11.

Xiang

Song

Chen

Wang

Huang

Gao

A wireless LAN-based indoor positioning technology

IBM Journal of Research and Development 2004 48 5-6 617 626

10.1147/rd.485.0617

2-s2.0-10644263665

12.

Medeiros

Park

Kak

A. C.

Distributed object tracking using a cluster-based Kalman filter in wireless camera networks

IEEE Journal on Selected Topics in Signal Processing 2008 2 4 448 463

10.1109/jstsp.2008.2001310

2-s2.0-54049136837

13.

Dong

Wejinya

U. C.

W. J.

An optical-tracking calibration method for MEMS-based digital writing instrument

IEEE Sensors Journal 2010 10 10 1543 1551

10.1109/JSEN.2010.2044995

2-s2.0-77955380254

14.

Mingdong

Leung

A joint fusion, power allocation and delay optimization approach for wireless sensor networks

IEEE Sensors Journal 2011 11 3 737 744

10.1109/jsen.2010.2066557

2-s2.0-79551563613

15.

Tay

Y. C.

Jamieson

Balakrishnan

Collision-minimizing CSMA and its applications to wireless sensor networks

IEEE Journal on Selected Areas in Communications 2004 22 6 1048 1057

10.1109/JSAC.2004.830898

2-s2.0-4344646722

16.

Keong

H. C.

Thotahewa

K. M. S.

Yuce

M. R.

Transmit-only Ultra Wide Band (UWB) body sensors and collision analysis

IEEE Sensors Journal 2013 13 5 1949 1958

10.1109/jsen.2013.2245562

2-s2.0-84876104283

17.

Han

Luo

Liu

Vasilakos

Algorithm design for data communications in duty-cycled wireless sensor networks: a survey

IEEE Communications Magazine 2013 51 7 107 113

10.1109/mcom.2013.6553686

2-s2.0-84880538357

18.

Xiao

Peng

Gibson

Xie

G. G.

D.-Z.

Vasilakos

A. V.

Tight performance bounds of multihop fair access for MAC protocols in wireless sensor networks and underwater sensor networks

IEEE Transactions on Mobile Computing 2012 11 10 1538 1554

10.1109/tmc.2011.190

2-s2.0-84865420766

19.

Vasilakos

A. V.

A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues

Proceedings of the IEEE 2013 101 12 2538 2557

10.1109/jproc.2013.2257631

2-s2.0-84889567969

20.

Al Ajarmeh

El-Zayyat

A hybrid routing protocol for mobile ad hoc and wireless sensor networks

Proceedings of the 4th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM ′08)

October 2008

Dalian, China

IEEE

1 5

10.1109/WiCom.2008.641

21.

Tian

Xin

Luo

Yang

Gong

Yang

A novel key management method for wireless sensor networks

Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology

October 2010

1106 1110

10.1109/icbnmt.2010.5705261

2-s2.0-79951753415

22.

Yao

Cao

Vasilakos

A. V.

EDAL: an energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks

IEEE/ACM Transactions on Networking 2015 23 3 810 823

10.1109/tnet.2014.2306592

2-s2.0-84895160458

23.

Xing

Zhou

Performance research and simulation analysis of the MAC layer protocols in wireless sensor networks

Proceedings of the 1st International Conference on Communications and Networking in China (ChinaCom ′06)

October 2006

1 3

10.1109/chinacom.2006.344798

2-s2.0-36048991740

24.

Nishide

Kubo

Shinkuma

Takahashi

Detecting hidden and exposed terminal problems in densely deployed wireless networks

IEEE Transactions on Wireless Communications 2012 11 11 3841 3849

10.1109/twc.2012.092712.100868

2-s2.0-84870563610

25.

Chowdhury

S. A.

Islam

M. T.

Jaigirdar

F. T.

Faruqui

M. R. U.

Noor

S. A.

Performance study and simulation analysis of CSMA and IEEE 802.11 in wireless sensor networks and limitations of IEEE 802.11

Proceedings of the 12th International Conference on Computers and Information Technology

October 2009

Xiamen, China

431 436

26.

Sun

Gurewitz

Johnson

D. B.

RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks

Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems (SenSys ′08)

November 2008

ACM

1 14

10.1145/1460412.1460414

2-s2.0-84866485309

27.

Tang

Sun

Gurewitz

Johnson

D. B.

PW-MAC: an energy-efficient predictive-wakeup MAC protocol for wireless sensor networks

Proceedings of the IEEE INFOCOM

April 2011

Shanghai, China

IEEE

1305 1313

10.1109/INFCOM.2011.5934913

28.

Lou

X.-Y.

Chen

Energy efficient TDMA sleep scheduling in wireless sensor networks

Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM ′09)

April 2009

630 638

10.1109/infcom.2009.5061970

2-s2.0-70349671119

29.

Rajendran

Obraczka

Garcia-Luna-Aceves

J. J.

Energy-efficient, collision-free medium access control for wireless sensor networks

Wireless Networks 2006 12 1 63 78

10.1007/s11276-006-6151-z

2-s2.0-32944474243

30.

Zibakalam

A new TDMA scheduling algorithm for data collection over tree-based routing in wireless sensor networks

ISRN Sensor Networks 2012 2012 7

864694

10.5402/2012/864694

31.

Zhang

A depth-based TDMA scheduling for clustering sensor networks

Proceedings of the 4th International Conference on Frontier of Computer Science and Technology (FCST ′09)

December 2009

Shanghai, China

IEEE

261 266

10.1109/FCST.2009.19

32.

X.-Y.

Liu

Lou

Energy-efficient wake-up scheduling for data collection and aggregation

IEEE Transactions on Parallel and Distributed Systems 2010 21 2 275 287

10.1109/tpds.2009.45

2-s2.0-75449119271

33.

You-Lin

Shiao-Li

Energy-efficient sleep-mode operations for broadband wireless access systems

Proceedings of the IEEE Vehicular Technology Conference

September 2006

Montréal, Canada

1 5

34.

Rhee

Warrier

Min

DRAND: distributed randomized TDMA scheduling for wireless ad hoc networks

IEEE Transactions on Mobile Computing 2009 8 10 1384 1396

10.1109/tmc.2009.59

2-s2.0-70349297218

35.

Gobriel

Mossé

Cleric

TDMA-ASAP: sensor network TDMA scheduling with adaptive slot-stealing and parallelism

Proceedings of the 29th IEEE International Conference on Distributed Computing Systems Workshops (ICDCS ′09)

June 2009

458 465

10.1109/icdcs.2009.80

2-s2.0-70350239866

36.

Tsertou

Laurenson

D. I.

Revisiting the hidden terminal problem in a CSMA/CA wireless network

IEEE Transactions on Mobile Computing 2008 7 7 817 831

10.1109/tmc.2007.70757

2-s2.0-44149094820

37.

Xizheng

Yaonan

New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network

Journal of Systems Engineering and Electronics 2009 20 1 185 191

2-s2.0-77956313727

38.

Gandham

Dawande

Prakash

Link scheduling in sensor networks: distributed edge coloring revisited

Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′05)

March 2005

IEEE

2492 2501

10.1109/INFCOM.2005.1498534

39.

Kabbani

Salonidis

Knightly

E. W.

Distributed low-complexity maximum-throughput scheduling for wireless Backhaul networks

Proceedings of the 26th IEEE International Conference on Computer Communications

May 2007

Anchorage, Alaska, USA

IEEE

2063 2071

10.1109/infcom.2007.239

2-s2.0-34548324691

40.

Zhou

X.-L.

Gong

Intra-cluster nodes scheduling algorithm satisfying expected coverage degree of application in distributed clustering WSNs

Proceedings of the International Conference on Computer Science and Software Engineering (CSSE ′08)

December 2008

332 335

10.1109/csse.2008.886

2-s2.0-79951503506

41.

Guo

Prasad

S. K.

An energy-efficient distributed algorithm for minimum-latency aggregation scheduling in wireless sensor networks

Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS ′10)

June 2010

827 836

10.1109/icdcs.2010.11

2-s2.0-77955879937

42.

Tian

Ekici

Özgüner

Energy-constrained task mapping and scheduling in wireless sensor networks

Proceedings of the 2nd IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2005

November 2005

211 218

10.1109/mahss.2005.1542802

2-s2.0-33750320382

43.

Gong

Vehicle scheduling problems of military logistics distribution based on improved Genetic Algorithm

Proceedings of the International Conference on Computer Application and System Modeling (ICCASM ′10)

October 2010

382 386

10.1109/iccasm.2010.5623185

2-s2.0-78649558646

44.

Aldabbagh

Bakhsh

S. T.

Akkari

Tahir

Tabrizi

Cioffi

QoS-aware tethering in a heterogeneous wireless network using LTE and TV white spaces

Computer Networks 2015 81 136 146

10.1016/j.comnet.2015.02.005

45.

Srinivasan

P. D. K.

Tavakoli

Levis

Understanding the causes of packet delivery success and failure in dense wireless sensor networks

2006 SING-06-00

Stanford, Calif, USA

Stanford University

46.

Lee

Cerpa

Levis

Improving wireless simulation through noise modeling

Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN ′07)

April 2007

21 30

10.1145/1236360.1236364

2-s2.0-35348910727

47.

Ranveer Chanadra

C. F.

Karin

Adaptive topology discovery in hybrid wireless networks

Proceedings of the Informatics, 1st International Conference on Ad Hoc Networks and Wireless

2002

Toronto, Canada

1 16, 20–22

48.

Booranawong

Teerapabkajorndet

Impact of radio propagation on the performance of directed diffusion routing in mobile wireless sensor networks

Proceedings of the International Conference on Embedded Systems and Intelligent Technology (ICESIT ′09)

2009

49.

Lee

Kwon

Improving Estimation of the Nearest Neighbor in Mobile Wireless Sensor Networks

2009

50.

Song

W.-Z.

Cao

TelosW: enabling ultra-low power wake-on sensor network

Proceedings of the 7th International Conference on Networked Sensing Systems (INSS ′10)

June 2010

211 218

10.1109/inss.2010.5573125

2-s2.0-78149257919

Self-Schedule and Self-Distributive MAC Scheduling Algorithms for Next-Generation Sensor Networks

Abstract

1. Introduction

2. Related Work

3. System Model and Problem Formulation

3.1. Network Model and Common Notations

Definition 1.

3.2. Interference Model

4. The Proposed Scheduling Algorithms

4.1. Overview of the Proposed Algorithms

4.1.1. Design Consideration

4.1.2. Framework of Proposed Algorithms

4.2. Self-Scheduled and Distributive MAC Algorithm

4.2.1. Algorithm Description

4.2.2. Scheduling Policy

4.2.3. Update Policy

4.3. Self-Distributive MAC Scheduling Algorithm

4.3.1. Algorithm Specification

4.3.2. Slot Scheduling Procedure

4.3.3. Update Procedure

4.4. Slot Assignment by Proposed Algorithms

5. Performance Metrics/Parameters and Evaluation of Results

5.1. Results for SSD-MAC

5.2. Results for SD-MAC

5.3. Comparative Analysis of Proposed and Current Algorithm

6. Conclusion and Future Work

Footnotes

Conflict of Interests

Acknowledgment

References