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

Authors: Sheikh Tahir Bakhsh; Muhammad Aman Sheikh; Rayed AlGhamdi
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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).


---

## Body

## 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 Section2. 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 afterTa 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.
(a)
(b)
(c)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 Ta time. During Ta node I schedules its own slot and broadcasts RELEASE. Suppose, node A REQUEST to node F before node H after Ta. 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.
(a)
(b)
(c)


## 3. System Model and Problem Formulation

This section consists of two subsections. In Section3.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×Am2 area and equipped with identical radio transceivers. All the nodes have the same transmission range (TR), which helps the nodes to identify the set of nodes in its communication range. Typically, a multihop (MH) WSN is represented by a graph G=V,E, whereas V=v1,v2,v3,v4,…,vn represents the set of nodes in a network and E=e1,e2,e3,e4,…,en 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,vEV and the edge e=u,vEE. More generally, the set of links are defined in(1)E=u,vEV·V∣distEUu,v≤TR,where distEU is the Euclidean distance.Definition 1.
Nodesu and v are in a one-hop (H1) neighborhood if both u and v are in TR of each other and there exists a link, u,vEE. Consider(2)∀u,vEH1,there  exists  a  link,u,vEE.Nodes u and v are in a two-hop (H2) neighborhood if there does not exist a direct link u,vEE but, alternatively, there exists a link, u,w, w,vEE. Consider(3)∀u,vEH2,there  exists  a  link,u,w,w,vEE.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 fromN2u (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 N2u, where N2u=H1u∪H2u. H1u and H2u represent the set of nodes in one-hop and two-hop, respectively. N2u⊇N1u, where N1u is in the 1-hop neighborhood of node u. Correspondingly, k-hop neighbors of node v can be represented by Δkv, 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 δkv; that is, δkv=Δkv, and the maximum k-hop neighbors are given as δkv=max⁡kδkv.


### 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 (IR) and TR. Conventionally, IR>TR and the ratio between them is γ=IR/TR. Practically, 2≤γ≤4 and the transmission will be successful at time τ between vi and vj if none of the nodes vk within the same TR is transmitting at τ. More formally, it can be explained as(4)viτ=1if  none  of  the  nodes  fromH1vi,H2viis  transmitting  at  timeτ0if  any  of  the  nodes  fromH1vi,H2viare  transmitting  at  timeτ.Consequently, the two nodesu and v are adjacent and conflicting, that is, vENu and uENv, where Nv and Nu 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.


## 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×Am2 area and equipped with identical radio transceivers. All the nodes have the same transmission range (TR), which helps the nodes to identify the set of nodes in its communication range. Typically, a multihop (MH) WSN is represented by a graph G=V,E, whereas V=v1,v2,v3,v4,…,vn represents the set of nodes in a network and E=e1,e2,e3,e4,…,en 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,vEV and the edge e=u,vEE. More generally, the set of links are defined in(1)E=u,vEV·V∣distEUu,v≤TR,where distEU is the Euclidean distance.Definition 1.
Nodesu and v are in a one-hop (H1) neighborhood if both u and v are in TR of each other and there exists a link, u,vEE. Consider(2)∀u,vEH1,there  exists  a  link,u,vEE.Nodes u and v are in a two-hop (H2) neighborhood if there does not exist a direct link u,vEE but, alternatively, there exists a link, u,w, w,vEE. Consider(3)∀u,vEH2,there  exists  a  link,u,w,w,vEE.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 fromN2u (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 N2u, where N2u=H1u∪H2u. H1u and H2u represent the set of nodes in one-hop and two-hop, respectively. N2u⊇N1u, where N1u is in the 1-hop neighborhood of node u. Correspondingly, k-hop neighbors of node v can be represented by Δkv, 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 δkv; that is, δkv=Δkv, and the maximum k-hop neighbors are given as δkv=max⁡kδkv.


## 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 (IR) and TR. Conventionally, IR>TR and the ratio between them is γ=IR/TR. Practically, 2≤γ≤4 and the transmission will be successful at time τ between vi and vj if none of the nodes vk within the same TR is transmitting at τ. More formally, it can be explained as(4)viτ=1if  none  of  the  nodes  fromH1vi,H2viis  transmitting  at  timeτ0if  any  of  the  nodes  fromH1vi,H2viare  transmitting  at  timeτ.Consequently, the two nodesu and v are adjacent and conflicting, that is, vENu and uENv, where Nv and Nu 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 Section4.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 itsH1u and H2u;(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 Figure5, 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τ∈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 τ∈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,(5)viτ=1when  only  nodeitransmits  at  timeτvjτ=0none  of  the  neighboring  nodesj∈Nineighbors  ofiis  transmitting  at  timeτ.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 itsH1 and H2 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 H1 but the nodes apart from that up to H2 cause interference. Nodes, for their transmission schedule in the SSD-MAC, are indirectly aware of the schedules of the nodes up to their H2 and reserve a slot that is not reserved by any of the nodes in their H1 and H2 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 H1 of each other, similarly (u,w) are in H2. If node u schedules (S0) for itself, then node v reserves (S0+1). Similarly, node w reserves (S0+2) to avoid a collision. Nodes, after scheduling their own slot, broadcast this information and the nodes in H1 update this information in their record and later on pass this information to H2 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 itsIR. 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(N2). 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 itsH1u and H2u. 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 H1I. If all H1I are in the IDLE or RELEASE state, they will reply with a GRANT message. After sending a GRANT message, H1I 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.
(a)
(b)
(c)


#### 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 ofS1 (where S1 represents the slot reserved in H1) through the RELEASE message. The RELEASE message has information of S1. In order to reserve a conflict-free time slot, each node must have information of S1 and S2 (where S2 represents the slot reserved by H2) where S2 is achieved through the GRANT message. Node I, after getting heads and winning the lottery, broadcasts a REQUEST message to get the update about S2(I). In response, node H1(I) will reply with a GRANT message which has the information of S2(I). Node I will go through S1I and S2I and finally reserve the minimum unassigned slots in N2(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 theirH1 and H2 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 H1 and H2 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 H1 and H2 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 itsIR. 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 Figure7(a), it is shown that node H tries to schedule a slot for itself; here it goes to reserve slot (0); that is, SH=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 H1H will update their record for 1-hop neighboring nodes; that is, H1F={H} and S1F=(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 H1u, S1u, H2u, and S2u record. From Figure 7(b), it is shown that when node I tries to schedule its slot, it will simply look up to its H1I, S1I, H2I, and S2I 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 H1 and H2.Figure 7
SD-MAC scheme.
(a)
(b)


### 4.4. Slot Assignment by Proposed Algorithms

According to the proposed algorithms, each node reserves its own slot within a frame based on itsH2 neighboring nodes. The proposed algorithms allow the network to adapt to the changes in topology by resizing the time frame based on the H2 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 N2. 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 H2 can reuse their slot Si (slot) in Lu (frame length), that is, l∗Li+Si where l=1,2,3,…,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.


## 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 itsH1u and H2u;(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 Figure5, 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τ∈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 τ∈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,(5)viτ=1when  only  nodeitransmits  at  timeτvjτ=0none  of  the  neighboring  nodesj∈Nineighbors  ofiis  transmitting  at  timeτ.The appropriate skeleton of these techniques is described in detail in the following sections.


## 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 Figure5, 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τ∈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 τ∈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,(5)viτ=1when  only  nodeitransmits  at  timeτvjτ=0none  of  the  neighboring  nodesj∈Nineighbors  ofiis  transmitting  at  timeτ.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 itsH1 and H2 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 H1 but the nodes apart from that up to H2 cause interference. Nodes, for their transmission schedule in the SSD-MAC, are indirectly aware of the schedules of the nodes up to their H2 and reserve a slot that is not reserved by any of the nodes in their H1 and H2 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 H1 of each other, similarly (u,w) are in H2. If node u schedules (S0) for itself, then node v reserves (S0+1). Similarly, node w reserves (S0+2) to avoid a collision. Nodes, after scheduling their own slot, broadcast this information and the nodes in H1 update this information in their record and later on pass this information to H2 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 itsIR. 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(N2). 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 itsH1u and H2u. 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 H1I. If all H1I are in the IDLE or RELEASE state, they will reply with a GRANT message. After sending a GRANT message, H1I 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.
(a)
(b)
(c)


### 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 ofS1 (where S1 represents the slot reserved in H1) through the RELEASE message. The RELEASE message has information of S1. In order to reserve a conflict-free time slot, each node must have information of S1 and S2 (where S2 represents the slot reserved by H2) where S2 is achieved through the GRANT message. Node I, after getting heads and winning the lottery, broadcasts a REQUEST message to get the update about S2(I). In response, node H1(I) will reply with a GRANT message which has the information of S2(I). Node I will go through S1I and S2I and finally reserve the minimum unassigned slots in N2(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.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(N2). 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 itsH1u and H2u. 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 H1I. If all H1I are in the IDLE or RELEASE state, they will reply with a GRANT message. After sending a GRANT message, H1I 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.
(a)
(b)
(c)


## 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 ofS1 (where S1 represents the slot reserved in H1) through the RELEASE message. The RELEASE message has information of S1. In order to reserve a conflict-free time slot, each node must have information of S1 and S2 (where S2 represents the slot reserved by H2) where S2 is achieved through the GRANT message. Node I, after getting heads and winning the lottery, broadcasts a REQUEST message to get the update about S2(I). In response, node H1(I) will reply with a GRANT message which has the information of S2(I). Node I will go through S1I and S2I and finally reserve the minimum unassigned slots in N2(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 theirH1 and H2 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 H1 and H2 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 H1 and H2 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 itsIR. 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 Figure7(a), it is shown that node H tries to schedule a slot for itself; here it goes to reserve slot (0); that is, SH=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 H1H will update their record for 1-hop neighboring nodes; that is, H1F={H} and S1F=(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 H1u, S1u, H2u, and S2u record. From Figure 7(b), it is shown that when node I tries to schedule its slot, it will simply look up to its H1I, S1I, H2I, and S2I 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 H1 and H2.Figure 7
SD-MAC scheme.
(a)
(b)


## 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 Figure7(a), it is shown that node H tries to schedule a slot for itself; here it goes to reserve slot (0); that is, SH=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 H1H will update their record for 1-hop neighboring nodes; that is, H1F={H} and S1F=(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 H1u, S1u, H2u, and S2u record. From Figure 7(b), it is shown that when node I tries to schedule its slot, it will simply look up to its H1I, S1I, H2I, and S2I 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 H1 and H2.Figure 7
SD-MAC scheme.
(a)
(b)


## 4.4. Slot Assignment by Proposed Algorithms

According to the proposed algorithms, each node reserves its own slot within a frame based on itsH2 neighboring nodes. The proposed algorithms allow the network to adapt to the changes in topology by resizing the time frame based on the H2 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 N2. 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 H2 can reuse their slot Si (slot) in Lu (frame length), that is, l∗Li+Si where l=1,2,3,…,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 150m×150m 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=VI)
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 mWPerformance 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 Table2. 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 150m×150m 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 itsN2 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 Figure10, 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 Figure12, 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 itsH1u and H2u 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.Figure14 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. Figure16 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 Figure18 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.
(a)
(b)
(c)
(d)Figure18(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.


## 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 itsN2 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 Figure10, 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 Figure12, 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 itsH1u and H2u 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.Figure14 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. Figure16 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 Figure18 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.
(a)
(b)
(c)
(d)Figure18(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.



---

*Source: 746216-2015-10-25.xml*