# A Distributed TDMA Slot Scheduling Algorithm for Spatially Correlated Contention in WSNs

Authors: Ashutosh Bhatia; R. C. Hansdah
Journal: Mobile Information Systems
 (2015)

---

## Abstract

In WSNs the communication traffic is often time and space correlated, where multiple nodes in a proximity start transmitting simultaneously. Such a situation is known asspatially correlated contention. The random access method to resolve such contention suffers from high collision rate, whereas the traditional distributed TDMA scheduling techniques primarily try to improve the network capacity by reducing the schedule length. Usually, the situation ofspatially correlated contentionpersists only for a short duration, and therefore generating an optimal or suboptimal schedule is not very useful. Additionally, if an algorithm takes very long time to schedule, it will not only introduce additional delay in the data transfer but also consume more energy. In this paper, we present a distributed TDMA slot scheduling (DTSS) algorithm, which considerably reduces the time required to perform scheduling, while restricting the schedule length to the maximum degree of interference graph. The DTSS algorithm supports unicast, multicast, and broadcast scheduling, simultaneously without any modification in the protocol. We have analyzed the protocol for average case performance and also simulated it using Castalia simulator to evaluate its runtime performance. Both analytical and simulation results show that our protocol is able to considerably reduce the time required for scheduling.


---

## Body

## 1. Introduction

A wireless sensor network (WSN) is a collection of sensor nodes distributed over a geographical region to monitor events of interest in the region. To effectively exchange data among multiple sensor nodes, WSNs employ the medium access control (MAC) protocol to coordinate the transmission over the shared wireless radio channel. Many times in WSNs, communication traffic is space and time correlated; that is, all the nodes in the same proximity transmit at the same time. Such a situation is known asspatially correlated contention. There exist many applications and protocols in WSNs, where the situations ofspatially correlated contention can occur. Some of them are as follows.(i)
Event Detection: whenever an event occurs, all the nodes that sense the event will start transmitting the details of the event to the base station. Typical examples of such situations are the detection of earthquake and wildfire in WSNs for disaster recovery, fall-and-posture detection in healthcare WSNs [1], and intrusion detection [2] in WSNs for military applications, in which sensor nodes only have data to send when a specific event occurs. As multiple nodes that detect the event are quite possibly in close proximity of each other, they would share the same transmission medium. Eventually, if all the nodes report the event at the same time, the situation would lead tospatially correlated contention.
(ii)
Multicast Communication: in WSNs, the applications should be configured and updated in the sensor nodes multiple times during the lifetime of the network. An update by transmitting the content to each individual sensor node separately would be very inefficient and would consume a lot of resources such as bandwidth and energy. In this situation, multicasting provides an efficient configuration and update of applications running over sensor nodes by reducing the number of transmitted packets. Another example of multicast communication in WSN is on-demand data collection, where the base station (sink node) sends a data query to a prespecified group of nodes asking them to send their sensory data. The WSN is usually multihop in nature, and therefore direct transmission of multicast messages from the sink is not possible. To achieve this, the sensor nodes also work as routers and forward the received multicast packet to their one-hop neighbors. This simultaneous forwarding of the same packet in a proximity by multiple routers leads tospatially correlated contention. A detailed discussion on multicast in WSN can be found in [3].
(iii)
Routing Protocols: the on-demand routing protocols, for example, Ad Hoc On-Demand Distance Vector Routing (AODV) [4], try to find the appropriate path from source to destination only when the data transfer is required. This process is called route discovery and it is typically achieved by broadcasting a route request message in the network and consequently leads to the collision of request message due to its simultaneous forwarding by the neighboring nodes.
(iv)
Clock Synchronization: clock synchronization protocols, for example [5], typically use message passing mechanism to share their local time information with other neighboring nodes. Since, initially, there is no coordination between the nodes, they may transmit the protocol message simultaneously with high probability, and therefore the transmitted messages might collide. This can considerably delay the process of synchronization.
(v)
Tree Based Convergecasting: convergecast, that is, gathering of information towards a central node, is important communication paradigms across all application domains in WSN. This is mainly accomplished by constructing an efficient tree in terms of delay, energy, and bandwidth. The algorithm for construction of such a tree typically involves simultaneous transmission of protocol messages by the sensor nodes and hence causesspecially correlated contention.Thus the above discussion suggests that the MAC protocols for WSNs should effectively handle the correlated contention. MAC protocols for WSNs can be mainly classified into two major categories, namely, random access based and schedule access based. Random access methods do not use any topology or clock information and resolve contention among neighboring nodes for every data transmission. Thus, it is highly robust to any change in the network. But its performance under high contention suffers because of high overhead in resolving contention and collisions [6]. Contention causes message collisions, which are very likely to occur when traffic isspatially correlated. This, in turn, degrades the data transmission reliability and wastes the energy of sensor nodes.A MAC protocol is contention-free if it does not allow any collisions. Assuming that the clocks of sensor nodes are synchronized, data transmissions by the nodes are scheduled in such a way that no two interfering nodes transmit at the same time. Early works [7–9] on scheduling are centralized in nature and normally need complete topology information, and therefore, they are not scalable. To overcome the difficulty of obtaining global topology information in large size networks, many distributed slot assignment schemes [10–14] have been proposed. The primary objective of traditional distributed TDMA scheduling techniques is to improve the network capacity by reducing the schedule length. It is effective for the kind of applications where a fixed schedule can be used for a sufficiently longer time. All the scenarios forcorrelated contention discussed previously occur in form of sessions and the nodes require a time slot to transmit a sequence of data, only during these sessions. Moreover, the same schedule cannot be reused for multiple future sessions, because at that time the network topology might have changed, due to dynamic channel conditions and occasional sleeping of sensor nodes to conserve their energy. For example, in [15], a different set of nodes are selected as routers (to equally distribute the consumption of energy among sensor nodes) every time the algorithm for construction of data collection tree is executed, and therefore this changes the network topology. This suggests that the scheduling has to be performed for every instance ofcorrelated contention, and therefore the effective benefit of reducing schedule length vanishes. If an algorithm takes too long to perform scheduling, as compared to the duration ofcorrelated contention, it will not only degrade the QoS (e.g., delay in detection of event at the base station) but will also lead to poor bandwidth utilization and higher energy consumption. The preceding discussion emphasizes that in order to effectively handle thecorrelated contention, the TDMA scheduling algorithms should take very less time to perform scheduling.In this paper, we propose a distributed TDMA slot scheduling (DTSS) algorithm for WSNs. The primary objective of DTSS algorithm is to reduce the time required to perform scheduling while restricting the schedule length to maximum degree of interference graph. The proposed algorithm is unified in the sense that the same algorithm can be used to schedule slots for different modes of communication, namely, unicast, multicast, and broadcast. In addition, the DTSS algorithm also supports heterogeneous mode of communication, where simultaneously a few nodes can take a slot for unicast, while other nodes can take it for multicast or broadcast purpose. In DTSS algorithm, a node is required to know only the IDs of its intended receivers, instead of all its two-hop neighbors. Also, in DTSS algorithm, the nodes in a neighborhood can take different slots simultaneously, if the resultant schedule is feasible. This is unlike the class of greedy algorithms where ordering between the nodes puts a constraint on the distributed algorithm to run sequentially and restricts the parallel implementation of the algorithm. The DTSS algorithm does not make use of any ordering among the nodes.The rest of the paper is organized as follows. Section2 discusses the related work. Section 3 gives the assumptions we make in the design of our algorithm, introduces some definitions, and explains the basic idea of our algorithm. In Section 4, we present a detailed description of the DTSS algorithm. Section 5 gives the proof of correctness of the DTSS algorithm. Section 6 presents the average case complexity analysis of the DTSS algorithm. Section 7 discusses the simulation results and performance comparison of DTSS algorithm with existing work. Section 8 concludes the paper with suggestions for future work.


## 2. Related Work

The broadcast scheduling problem to find optimal solution is NP-complete [16]. A different, but related, problem to TDMA node slot assignment is the problem of TDMA edge slot assignment, in which radio links (or edges) are assigned time slots, instead of nodes. Finding the minimum number of time slots for a conflict-free edge slot assignment is also an NP-complete problem [17]. In [18], another specific scheduling problem for wireless sensor network converge-cast transmission is considered in which the scheduling problem is to find a minimum length frame during which all nodes can send their packets to access point (AP), and it is shown to be NP-complete. Previous work [7–9, 19] on scheduling algorithms primarily focuses on decreasing the length of schedules. They are centralized in nature and normally need complete topology information and are, therefore, not scalable.Cluster based TDMA protocols in [20, 21] prove to be having good scalability. The common feature of these protocols is to partition the network into some clusters, in which cluster heads are responsible for scheduling their members. However, cluster based TDMA protocols introduce intercluster transmission interference because clusters created by distributed clustering algorithms are often overlapped and several cluster heads may cover the same nodes.Moscibroda and Wattenhofer [11] have proposed a distributed graph coloring scheme with a time complexity of O
(
ρ
log
⁡
n
), where ρ is the maximum node degree and n is the number of nodes, in the network. The scheme performs distance-1 coloring such that adjacent nodes have different colors. Note that this does not prevent nodes within two hops of each other from being assigned the same color potentially causing hidden terminal collisions between such nodes. The NAMA protocol in [10] has proposed a distributed scheduling scheme based on hash function to determine the priority among contending neighbors. A major limitation of this hashing based technique is that even though a node gets a higher priority in one neighborhood, it may still have a lower priority in other neighborhoods. Thus the maximum slot number could be of O
(
n
). Secondly, since each node calculates the priority of all of its two-hop neighbors for every slot, it leads to O
(
n
2
) computational complexity, and hence, the scheme is not scalable for large network with resource constraint nodes. SEEDEX [22] uses a similar hashing scheme as NAMA based on a random seed exchanged in a two-hop neighborhood. In SEEDEX, at the beginning of each slot, if a node has a packet ready for transmission, it draws a “lottery” with probability p. If it wins, it becomes eligible to transmit. A node knows the seeds of the random number generators of its two-hop neighbors, and hence it also knows the number of nodes (including itself) n, within two hops which are also eligible to transmit. It then transmits with probability 1
/
n. This technique is also called topology independent scheduling. In this case, collisions may still occur if two nodes select the same slot and decide to transmit.Another distributed TDMA scheduling scheme, called DRAND [12], proposes a distributed randomized time slot scheduling algorithm based on centralized scheduling scheme RAND [9]. DRAND is also used within a MAC protocol, called Zebra-MAC [23], to improve performance in sensor networks by combining the strength of scheduled access during high loads and random access during low loads. The runtime complexity of DRAND is O
(
δ
), where δ is the maximum size of a two-hop neighborhood in a wireless network. The simulation results presented by the author show that the runtime actually becomes O
(
δ
2
) due to unbounded message delays. FPRP [14], Five-Phase Reservation Protocol, is a distributed heuristic TDMA slot assignment algorithm. FPRP is designed for dynamic slot assignment, in which the real time is divided into a series of pairs of reservation and data transmission phases. For each time slot of the data transmission phase, FPRP runs a five-phase protocol for a number of times (cycles) to pick a winner of each slot. In another distributed slot scheduling algorithm, DD-TDMA [13], a node i decides slot j as its own slot if all the nodes with ID less than the ID of node i have already decided their slot, where j is the minimum available slot. The scheduled node i broadcasts its slot assignment to one-hop neighbors. Then the one-hop neighbors of node i broadcast this information to update two-hop neighbors. This process is repeated in every frame until all nodes are scheduled.The protocol in [24] proposes a contention-free MAC for correlated contention, which does not assume global time reference. The protocol is based on local frame approach where each node divides time into equal sized frames. Each frame is further divided into equal sized time slots; a time slot corresponds to the time duration of sending one message. The basic idea is that each node selects a slot in its own frame such that selected slots of any two-hop neighbor nodes must not overlap. The protocol assumes that a node can detect a collision if two or more nodes (including itself) within its transmission radius attempt to transmit, which has its own practical limitations with wireless transceivers. These scheduling algorithms [12–14] commonly have the following issues.(i)
All algorithms use greedy approach for graph colouring which is inherently sequential in nature and put a constraint on distributed algorithm to run sequentially. This restricts the parallel implementation of the algorithm. Because of large runtime of these protocols, they are more suitable for wireless networks where interference relationship or network topology does not change for a long period of time.
(ii)
They perform two-hop neighbor discovery, which adds considerable additional cost to runtime to perform scheduling. Additionally, the two-hop neighbors are calculated based on transmission range instead of interference range, which is normally higher than the transmission range.
(iii)
They perform either broadcast (node) scheduling or unicast (link) scheduling but not both and also do not consider multicast scheduling separately.Finally, a classification of different scheduling algorithms based on problem setting, problem goal, type of inputs, and solution techniques can be found in [25].


## 3. Our Approach to TDMA Scheduling in WSNs

In many applications such as weather monitoring, intrusion detection, sensor nodes are usually static. In this work also, we assume them to be static. Also, it is assumed that, for any task in an application, every node knows its receivers. Before a task begins its execution, the DTSS algorithm is executed to generate a TDMA schedule. After the task is finished, the TDMA schedule is discarded. We assume that each node in the WSN has a unique identifier. All the nodes in a WSN have some processing capability along with a radio to enable communication among them. Each node uses the same radio frequency. The communication capability is bidirectional and symmetric. The mode of communication between any two neighboring nodes is half-duplex; that is, only one node at a time can transmit. The transmission is omnidirectional; that is, each message sent by a nodei is inherently received at all the nodes determined by its transmission range.Timeline is divided into fixed size frames and each frame is further divided into fixed number of time slots, called schedule length. The nodes are assumed to be synchronized with respect to slot 0 and are aware of the slot size and the schedule length. The time of slot 0 is defined by the node which starts the scheduling process. To better understand the proposed algorithm, we introduce the following definitions.Definition 1.
The interference setN
i of a node i is defined as the set of nodes which are within the interference range of node i. That is, we say that a node k
∈
N
i if it cannot successfully receive any message transmitted by any other node, at the same time when node i is also transmitting. Moreover, if only node i has transmitted in a slot, then a node in N
i may or may not receive the message successfully.Note that the interference setN
i is different from the set of one-hop neighbors which depends upon the transmission range of node i. Usually, the interference range is higher than the transmission range.Definition 2.
The receiver setR
i of a node i is defined as the set of intended receivers of node i.The size of the setR
i, |
R
i
| depends upon the type of communication, namely, unicast, multicast, or broadcast transmission. Note that R
i
⊆
N
i. The DTSS algorithm assumes that only the subset R
i is known to the node i instead of all its two-hop neighbors.Definition 3.
The sender setS
i of a node i is defined as the set of nodes j such that i
∈
R
j.A node need not know the setS
i before the start of the algorithm. It can be populated when the node receives protocol messages with destination ID as its own ID.Definition 4.
The interference graphG
=
(
V
,
E
) of a WSN is defined as follows. V is the set of nodes in the WSN, and E is the set of edges, where edge e
=
(
i
,
j
) exists if and only if N
i
∩
R
j
≠
ϕ
∨
N
j
∩
R
i
≠
ϕ. The number of edges with which a node is connected to the other nodes is called the degree of the node.Note thati
∈
R
j or j
∈
R
i is also possible. We say that node i and node j conflict and are adjacent to each other, if there exists an edge between them. An edge e
=
(
i
,
j
) exists if and only if node i and node j cannot take the same slot. Two nodes cannot take the same slot, if the transmission of one node interferes at one of the receivers of the other node. The conflict between nodes depends not only upon their respective positions and transmission power but also on the type of communication, namely, unicast, multicast, or broadcast. Two nodes within the interference range of each other (i
∈
N
j
∨
j
∈
N
i) can even take the same slot, if their transmissions do not interfere at each other’s receivers (Figure 1). Therefore, our definition of interference graph is free from well known exposed-node problem. This fact is usually ignored by most of the existing algorithms. On the other hand, two nodes which are not in the interference range of each other (i
∉
N
j
∧
j
∉
N
i) cannot transmit simultaneously, if their transmissions interfere at each other’s receivers. In this manner, our definition of interference graph is also free from the hidden-node problem.Figure 1
Example of nodesi and j that do not conflict even if they are in the interference range of each other.A sensor node requires a slot to transmit data packets such that data can be received successfully at all of its receivers without any interference.The following two types of conflict relations can exist, between a pair of nodes.Strong-Conflict Relation. Two nodes i and j have strong-conflict relation if N
i
∩
R
j
≠
ϕ
∧
N
j
∩
R
i
≠
ϕ.Weak-Conflict Relation. Two nodes i and j have weak-conflict relation if either N
i
∩
R
j
≠
ϕ or N
j
∩
R
i
≠
ϕ, but not both.Figures2(a) and 2(b) depict the situation when node i and node j have strong-conflict and weak-conflict relations, respectively. In case of weak-conflict relation, if N
j
∩
R
i
≠
ϕ but N
i
∩
R
j
=
ϕ, we say that node j is stronger than node i and denote it by j
→
i.Conflict relationship between nodes.
(a)
Strong-conflict relation
(b)
Weak-conflict relationDefinition 5.
The interference degreeΔ of a WSN is defined as the maximum of all degrees of nodes in the interference graph G of the WSN.The DTSS algorithm runs inO
(
Δ
) time. In case of broadcast transmission; Δ and δ are roughly the same, where δ is the size of two-hop neighborhood set. But for unicast or multicast transmission Δ
≤
δ.The TDMA slot scheduling problem can be formally defined as the problem of assignment of a time slot to each node, such that if any two nodes are in conflict (strong or weak), they do not take the same time slot. Such an assignment is called a feasible TDMA schedule. A feasible TDMA schedule which takes minimum number of slots is called an optimal TDMA schedule. Our goal in this paper is to develop an algorithm which can find a feasible but not necessarily optimal TDMA schedule and to minimize the time required to perform scheduling.The basic idea of the DTSS algorithm is as follows. For each slots in a frame, each node i checks whether it can take the slot s, by sending a request message to the first receiver in R
i with slot probability P
(
s
), which depends upon the remaining number of free slots in the frame (slots which are not taken by others) known at node i at the current time. If node i receives response message from the first receiver, then it blocks the slot and tries to get the responses from the remaining receivers in R
i using the same slot in subsequent frames. After receiving the response from all the receivers, it assigns the time slot s to itself; otherwise, it unblocks the slot, as soon as the response from one of the receivers is not received, and repeats the above process all over again. In case of unicast communication, node i can directly assign the slot to itself as soon as it receives the response message from its receiver j instead of blocking the slot. This is because receiving a response message from node j tells that no other node k adjacent to i in G has also blocked the same slot; otherwise, the REQ message transmissions of nodes i and k would have collided at node j. An adjacent node of a node i in a graph is a node that is connected to i by an edge.Once a slot is assigned to a nodei, it continuously transmits at the same slot in subsequent frames. This would ensure that a conflicting node j in G cannot assign the same slot to itself, because of the collision between the transmission of node i and node j at one of the receivers in R
i. Furthermore, the nodes in R
i also propagate this information to next hop through their own transmissions. Note that the receivers of messages transmitted by the nodes in R
i are adjacent to i in G.When a nodej hears, from one of the receivers of node i, that slot s is blocked by node i, it leaves the slot temporarily and avoids further collisions to increase the chance of getting the slot by node i. Similarly, when node j hears, from one of the receivers of node i, that slot s is assigned to node i, it leaves the slot permanently and increases its slot probability for other free slots.


## 4. The DTSS Algorithm

In this section, we describe the proposed DTSS algorithm for TDMA slot scheduling problem as defined in Section2. The number of slots, N, in a frame is taken to be at least Δ. The slots are numbered from 1 to N. Table 1 summarizes the set of data structures and variables maintained by a node i, to implement the algorithm. The DTSS algorithm uses two protocol messages, namely, request (REQ) and response (RES), for signaling purpose. The RES message is sent by a node, whenever its ID is the same as the destination ID in the received REQ message. The REQ/RES messages contain four fields, namely, source ID, destination ID, L
2, and state. The value of field L
2 in both REQ and RES messages is the copy of corresponding local variable. The value of field state in REQ message is the same as the value of the local variable n
r while its value in RES message contains the value of field state as received in the corresponding REQ message. The field L
2 in REQ/RES message is used to inform a node j about the slots which are already taken by other nodes conflicting with node j, whereas the field state helps the nodes to know the status of the node from where the REQ message has been transmitted. The higher level description of the DTSS algorithm is shown in the pseudocode given in Algorithm 1. The pseudocode describes the DTSS algorithm as executed on each node i at the current slot s.Table 1
The set of data structures and variables maintained by a nodei.
Notation
Description
R
i
A list of receivers of nodei, maintained as circular linked list.
S
i
A list of transmitters of nodei, constructed dynamically on receipt of REQ messages.
L1
A list of slots which are already taken by the nodes adjacent toi in G.
L2
A list of slots which are already taken by the nodes inS
i. Note that L
2
⊆
L
1.
L3
A list of slots which are currently blocked by the nodes adjacent toi in G.
N
Number of slots in a frame.
i.slot
Slot assigned to nodei.
i.b_slot
Slot blocked by nodei.
rx_ID
Current receiver node inR
i.
nr
Remaining number of receivers from where responses are required to be obtained by nodei.
P
(
s
)
Probability of transmitting a request message in slots by node i, while contending for the slot.Algorithm 1:DTSS algorithm.
if   i.slot = i.b_slot = null and  s
∉ (L3 or L1)  then
With probability, P
(
s
)  do
send REQ(i, rx_ID, L2, |
R
i
|)
rx_ID =R
i
→
n
e
x
t
End do
end if
if i.slot = s  or i.b_slot = s  then
send REQ(i, rx_ID, L2, nr)
rx_ID =R
i
→
n
e
x
t
end if
//perform channel listening
if  i receives a REQ(j, dest_ID, L2, state) then
if REQ.dest_ID = i  then
add REQ.j in S
i,
send RES(i, j, L2, REQ.state)
end if
if  j
∈
R
i and REQ.state = 0 then
slots has been taken by node j, add s to L1
if  j
∈
S
i add s to L2
end if
end if
if  j
∈
S
i or j
∈
R
i and REQ.state ≠ 0 then
slots is blocked, add s to L3
end if
end if
if  i receives a RES(j, dest_ID, L2, state)
if RES.dest_ID = i  then
if nr = |
R
i
|  then i.b_slot = s
end if
nr = nr − 1
if nr = 0 then i.slot = s
end if
else
if RES.state = 0 then
slot is taken by RES.dest_ID, add s toL1
if RES.dest_ID ∈
S
i add s to L2
end if
else
slots is blocked, add s to L3
end if
end if
end if
if i.slot = null and not received the RES for transmitted REQ message then
i.b_slot = null, nr =|
R
i
|
end if
if  s
∈
L3
Removes from L3 if blocked duration has expired
end ifEach nodei, contending for a time slot, passes through several states. Figure 3 shows the finite state transition diagram for a node i. Initially, node i enterscontention state (CS), where it sends a REQ message in the current time slot s, with probability P
(
s
). We call this probability as slot probability and it is equal to 1
/
(
N
-
|
L
1
|
). On receipt of a REQ message at a node j from node i, it sends a RES message immediately in the current slot s and also adds the node i to S
j if its ID is the same as the destination ID in the received REQ message. The duration of slot is kept sufficiently large to carry out the transmission of a pair of REQ and RES messages. The destination ID j of REQ message transmitted by node i in CS state can be any node from the set R
i. If a node i receives a RES message at time slot s in response to the REQ message sent by it and |
R
i
|
>
1, then it blocks the time slot s and enters theverification state (VS). However, if |
R
i
|
=
1, it assigns the slot to itself and enters the scheduled state (SS) directly. In VS state, it sends REQ messages one by one to the remaining nodes in R
i at the same time slot s in subsequent frames, by setting the pointer r
x
_
ID to the next node in the list R
i. Furthermore, it does not transmit in slots other than s, while it is in VS state. If the node i successfully receives the RES messages from all of its receivers in R
i, it assigns the slot to itself and enters thescheduled state (SS); otherwise, it goes back to the CS state and starts the process all over again. In SS state, the node i always transmits REQ message in slot s so that no other node can take the same slot and also it does not transmit at slots other than s. The destination of REQ message in SS state is selected in a round robin fashion among the nodes in R
i. Moreover, it does not progress to the next receiver until it receives a RES message from the current receiver. If a node i does not receive RES message consecutively Δ times from the same receiver node, then it goes back to the CS state.Figure 3
State transition diagram of a nodei.If a nodei in CS state receives a REQ message from node j at slot s with state
>
0 and j
∈
S
i or j
∈
R
i, then it adds the slot s in the list L
3. If a node i in CS state receives a REQ message from node j at slot s with state
=
0 and j
∈
R
i it adds the slot s in the list L
1 and also updates the slot probability of other slots not in L
1 as 1
/
(
N
-
|
L
1
|
). Additionally, if j
∈
S
i, then it also adds the slot s in the list L
2.If a nodei in CS state receives a RES message in response to REQ message from itself and n
r
=
|
R
i
|, then it blocks the slot. Then it decreases n
r by 1, and if n
r becomes zero, it assigns the slot to itself. If a node i in CS state receives a RES message from node j in response to REQ message from node k at slot s with state
>
0, then it adds the slot s in the list L
3. A node does not transmit its own REQ messages in the slots belonging to L
3 for the number of subsequent frames specified in the state field of the received RES message. This allows node k in VS state to successfully transmit its remaining REQ messages and subsequently move to SS state. If a node i in CS state receives a RES message from node j in response to REQ message from node k at slot s with state
=
0, it adds the slot s in the list L
1 and also updates the slot probability of other slots not in L
1 as 1
/
(
N
-
|
L
1
|
). Node i permanently leaves the slots in L
1 and does not transmit any further REQ messages in these slots. Additionally, if k
∈
S
i, then it adds the slot s in the list L
2.It could be possible that a nodej does not receive the transmission of a REQ message from node i or RES message in response to the REQ message from node i in slot s because REQ/RES messages could get lost. In this situation, node j would not come to know that the slot s is either blocked or taken by node i until the transmissions of REQ/RES message at the same slot in the next frame. To avoid this delay, the nodes in R
i convey the same information through the field L
2 of their own REQ messages transmitted in slots other than s. In this case, while a node is trying to take a slot, it is helping others to know the slots which are already taken by other conflicting nodes.Finally, a nodej, with j
→
i, can enter into state SS, while node i is already in state SS. This is because the transmission of REQ messages from node i in slot s cannot interfere at any of the nodes in R
j, and therefore, node j will receive the RES messages from all of its receivers and move to state SS. On the other hand, the REQ messages sent by node i in SS state will collide at one or more receivers in R
i due to transmission from node j and therefore node i will not receive the corresponding RES messages. The above situation is shown in Figure 2(b). However, this can only happen if node j is not aware that the slot is already taken by node i. To avoid this, if the RES is not received by node i for consecutive Δ times, it leaves the slot by adding it to the list L
1 and comes back to the CS state. If node j is not in SS state, it cannot collide with the transmission of node i in the same slot consecutively Δ times. This ensures that node i will only leave the slot s, if j
→
i and j is in SS state.


## 5. Correctness of the DTSS Algorithm

In this section, we prove that the schedule created by the DTSS algorithm is a feasible TDMA schedule. In a feasible schedule, two conflicting nodes will not transmit in the same time slot. That is, two conflicting nodes will not be assigned the same time slot by the DTSS algorithm. This happens because after the execution of the DTSS algorithm is completed, only one node (among the conflicting nodes) will remain in the SS state for a particular time slot. In the following, we prove this fact as Theorems6 and 7 for strong-conflict and weak-conflict relationship, respectively.Theorem 6.
If two nodesi and j have strong-conflict relationship, then they cannot be in SS state for the same time slot, at any time during the execution of DTSS algorithm.Proof.
Letfram
e
i
VS and fram
e
i
SS be the frame indexes when node i enters VS and SS state, respectively, for a time slot k. It is possible that fram
e
i
VS
=
fram
e
i
SS if |
R
i
|
=
1. Furthermore, let fram
e
j
VS and fram
e
j
SS be the corresponding frame indexes for node j for the same time slot k. We can assume that once a node enters VS state from CS state, it remains in VS state until it enters SS state. If it is not so, then it goes back to CS state, and the argument can be repeated. It is to be noted that both cannot enter SS state at the same frame index without at least one of them going into VS state first. Now the following three cases arise.
Case
1 (
f
r
a
m
e
i
V
S
<
f
r
a
m
e
j
V
S
). In this case, only node i can enter SS state provided it has got response from all nodes k
∈
N
j
∩
R
i prior to fram
e
j
VS. There is no way node j can enter SS state since node i will be continuously transmitting REQ messages from frame index fram
e
i
VS, and node j cannot get response from any node in N
i
∩
R
j (Figure 4). Hence, in this case only node i will be able to enter SS state.
Case
2 (
f
r
a
m
e
i
V
S
=
f
r
a
m
e
j
V
S
). In this case, both node i and node j will be transmitting REQ messages from frame index fram
e
i
VS onwards. Therefore, node i will not be able to get response from any node in N
j
∩
R
i. Similarly, node j will not get response from any node in N
i
∩
R
j. So, the node which does not receive the response first will go back to CS state. As a result neither node i nor node j will be able to enter SS state as Case 2.
Case
3 (
f
r
a
m
e
i
V
S
>
f
r
a
m
e
j
V
S
). This case is similar to Case 1 except that now node j can enter SS state provided it satisfies the corresponding condition.
From the above argument, it is clear that only one of nodesi or j will be in SS state for the same time slot during the execution of the DTSS algorithm. Hence, the theorem is proved.Figure 4
Nodej cannot enter SS state since node i is continuously transmitting REQ messages from frame index fram
e
i
VS.In case of weak-conflict relationship, it could be possible that while a nodei is already in SS state, another node j (stronger than node i) can enter SS state for the same time slot, during the execution of DTSS algorithm. Therefore, Theorem 6 does not sufficiently prove the correctness of DTSS algorithm when weak-conflict relationship also exists between the nodes.Theorem 7.
If two nodesi and j have weak-conflict relationship, then eventually only one of nodes i and j will remain in SS state for the same time slot after the execution of the DTSS algorithm is completed.Proof.
Letfram
e
i
VS, fram
e
i
SS, fram
e
j
VS, and fram
e
j
SS be frames indexes of nodes i and j as in Theorem 6. Also, without loss of generality assume that N
i
∩
R
j
≠
ϕ and N
j
∩
R
i
=
ϕ. That is, node i is stronger than node j. As in Theorem 6, we also assume that, after entering VS state, both remain there until they enter SS state. It is to be noted that both cannot enter SS state at the same frame index directly from CS state, without at least one of them going into VS state first. In this case also, the following three cases arise.
Case
1 (
f
r
a
m
e
i
V
S
<
f
r
a
m
e
j
V
S
). This case is similar to Case 1 of Theorem 6, and only node i will be able to enter SS state, and node j will not be able to enter SS state.
Case
2 (
f
r
a
m
e
i
V
S
=
f
r
a
m
e
j
V
S
). In this case also, only node i will be able to enter SS state, and node j will not be able to enter SS state.
Case
3 (
f
r
a
m
e
i
V
S
>
f
r
a
m
e
j
V
S
). In this case, node i can enter SS state anyway. However node j can also enter SS state provided it has got response from all the nodes in N
i
∩
R
j before frame index fram
e
i
VS. Let us assume that node j satisfies this condition. Now nodes i and j can enter SS state in any order. Assume that both nodes i and j are in SS state; then node j would not be able to get response continuously Δ times from a node in N
i
∩
R
j. As a result, node j would move back to CS state, and it would not be able to enter SS state again.


## 6. Complexity Analysis of DTSS Algorithm

In this section, we evaluate the expected runtime of DTSS algorithm, that is, the time when all nodes in the network reach SS state. Table2 summarizes the set of notations used in this section. First, we consider the situation, when all nodes in the network interfere with each other’s transmission; that is, the interference graph G is complete. This situation mainly occurs in single-hop WSNs. In this case, only a single transmission of REQ message in a slot can be successful, and therefore, nodes can enter SS state one at a time in each slot, as shown in Figure 5. Furthermore, we assume that |
R
i
|
=
1, for each node i. In this case nodes directly enter SS state without entering the VS state. The analysis can be further extended for the case when |
R
i
|
>
1. Initially, every node transmits REQ message with probability 1
/
N in every slot.Table 2
The set of notations used in Section6.
Notation
Description
X
i
The time slot at whichith node enters SS state.
Y
i
Number of time slots between timesX
i and X
i
-
1
P
succ
The probability that only one node transmits a REQ message in a slot after and the message is received successfully.
q
i
The probability of a nodei entering SS state, in a round (frame).
q
The probability of a node with ID 1 entering SS state, in a round (the subscript 1 omitted from sake of clarity).
q
min
⁡
Minimum value ofq.
q
(
k
)
The probability of node with ID 1 entering SS state at slotk in a round.
q
sum
∑
k
=
1
N
‍
q
(
k
).
β
i
The number of 1’s in rowi of matrix B.
α
j
The number of 1’s in columnj of matrix B, excluding first row.
π
i
,
j
The transition probability from statei to state j of DTMC, presented in Section 6.
τ
i
The number of rounds required to reach state “n” in DTMC, starting from state “i.”Figure 5
Sequence of slot assignment in a single-hop WSN. The nodes cannot enter state simultaneously in a slot.Let the time slot at whichith node enters SS state be X
i. Note that X
i is a random variable. Clearly, X
n is the time slot when last node enters SS state, which is exactly the desired runtime of DTSS algorithm. Let Y
i
=
X
i
-
X
i
-
1. In this case,
(1)
X
i
=
X
i
-
1
+
Y
i
,
E
X
i
=
E
X
i
-
1
+
E
Y
i
=
∑
j
=
1
i
‍
E
Y
j
.Theorem 8.
E
X
n is O
(
n
) for single-hop WSNs.Proof.
At time slotX
i
-
1, exactly i
-
1 nodes are in SS state and for the remaining n
-
i
+
1 nodes which are not in SS state, set their slot probability to 1
/
(
n
-
i
+
1
), for unoccupied slots. Let P
succ be the probability that only one node transmits a REQ message in a slot after time slot X
i
-
1 and the message is received successfully at the intended receiver. Note that the REQ message could be lost not only due to collisions but also because of channel impairment. Therefore, a successful packet transmission also depends upon packer error rate (PER). Y
i is a geometric random variable with success probability P
succ and expectation 1
/
P
succ. The upper bound of E
Y
n (runtime) can be calculated as follows:
(2)
P
succ
=
n
-
i
+
1
1
*
1
n
-
i
+
1
*
n
-
i
n
-
i
+
1
n
-
i
*
1
-
PER
=
n
-
i
n
-
i
+
1
n
-
i
*
1
-
PER
,
E
Y
i
=
1
P
succ
=
n
-
i
+
1
n
-
i
n
-
i
*
1
1
-
PER
=
1
+
1
n
-
i
n
-
i
*
1
1
-
PER
,
E
Y
i
≤
e
(
1
-
PER
)
,
∵
1
+
1
n
-
i
n
-
i
,
is
monotonically
increasing
and
converges
to
e
E
X
n
=
∑
j
=
1
n
‍
E
Y
j
≤
1
1
-
PER
∑
j
=
1
n
‍
e
=
n
e
1
-
PER
=
O
n
.Now, we will consider a more generalized situation when not all nodes in the network interfere with each other’s transmission; that is, the interference graphG is not necessarily complete. Again we assume that |
R
i
|
=
1. The above situation mainly occurs in multihop WSNs. Further, we assume that the graph G is regular with degree N
-
1. Note that N is always taken to be greater than Δ, the maximum degree of interference graph. Therefore, assuming the graph to be regular with degree N
-
1 will give the worst case analysis; that is, the expected runtime of DTSS algorithm for a nonregular interference graph with Δ
=
N
-
1 will always be less than or equal to the expected runtime for a regular interference graph of degree N
-
1.We will first find out for an arbitrary nodei what the minimum value is that q
i can take, irrespective of the slot probabilities of other nodes in the network. This will help us to set an upper bound on the expected time, required by any node, to reach SS state.Let us rearrange the IDs of the nodes in the following manner.(i)
The ID of nodei is changed to 1.
(ii)
The IDs of nodes adjacent to nodei in G would be changed from 2 to N. The ordering among these nodes could be arbitrary.
(iii)
The IDs of all other nodes would becomeN
+
1 to n. The ordering among these nodes could be arbitrary. Note that, the above rearrangement will not change the probability of node i entering SS state in a round. Our task is to find out q
1 instead of q
i. Further, we can also omit the subscript 1 from q
1 for sake of clarity.Let the probability of node with ID 1 (after rearrangement) entering SS state at slotk in a round be q
(
k
). The value of q
(
k
) depends upon the transmission probability of node 1 in slot k and the transmission probabilities of its adjacent nodes in the same slot. Consider
(3)
q
k
=
p
1
k
*
∏
j
=
2
N
‍
1
-
p
j
k
.
The probability that node 1 can enter SS state in a round is equal to the probability that it can enter SS state in at least one slot of the round. Therefore, q can be written in terms of q
(
k
) as
(4)
q
=
1
-
∏
k
=
1
N
‍
1
-
q
k
.In order to find the minimum value ofq, we define another term q
sum as a function of q
(
k
)’s as follows:
(5)
q
sum
=
∑
k
=
1
N
‍
q
k
.We know that, for a constant sum, the product can be maximized when the sum is partitioned equally [26]. Therefore, for a constant value of q
sum, q can achieve its minimum value q
min
⁡, if q
(
l
)
=
q
(
m
), 1
≤
l,  m
≤
N. Obviously, q
min
⁡ is a function of q
sum.Theorem 9.
Letq
min
⁡
=
F
(
q
s
u
m
). Then F is a monotonically increasing function.Proof.
Letx and y be the two values of q
sum, such that x > y. We know that q
min
⁡ is achieved when q
(
l
)
=
q
(
m
), 1
≤
l, m
≤
N. Let c
1 and c
2 be the corresponding values of q
(
k
), for all k with respect to x and y. In this case, the value of F
(
x
) and F
(
y
) would be 1
-
(
1
-
c
1
)
N and 1
-
(
1
-
c
2
)
N, respectively (4). Therefore,
(6)
x
>
y
⟹
N
c
1
>
N
c
2
⟹
c
1
>
c
2
⟹
(
1
-
c
1
)
<
(
1
-
c
2
)
⟹
1
-
c
1
N
<
1
-
c
2
N
⟹
1
-
1
-
c
1
N
>
1
-
(
1
-
c
2
)
N
⟹
F
x
>
F
y
.It is clear from Theorem9 that, to find q
min
⁡, we need to first minimize the q
sum. Let us define a binary square matrix, B, of size N, in the following manner:
(7)
b
i
,
j
=
1
,
if
p
i
(
j
)
>
0
0
,
otherwise
.The matricesP and B show an example of probability matrix and its corresponding binary transformation for N
=
3. Consider
(8)
P
=
1
3
1
3
1
3
1
2
1
2
0
1
2
0
1
2
,
B
=
1
1
1
1
1
0
1
0
1
.Letβ
i
=
∑
j
=
1
N
‍
b
i
,
j (number of 1’s in row i of matrix B) and α
j
=
∑
i
=
2
N
‍
b
i
,
j (number of 1’s in column j of matrix B, excluding first row). The q
(
k
) can be rewritten in terms of b
j
,
k and β
j, 1
≤
j
≤
N, as follows:
(9)
q
k
=
b
1
,
k
β
1
∏
j
=
2
N
‍
1
-
b
j
,
k
β
j
.LetB
min
⁡ be the matrix for which the value of q
sum is minimum. To find out the properties of B
min
⁡, we start with the hypothesis that q would be minimum, if none of the nodes adjacent to node 1 is in SS state. This implies that node 1 is still transmitting in all the slots with probability 1
/
N; that is, b
1
,
k
=
1, for all k, 1
≤
k
≤
N. Now, we will present two lemmas based on the above hypothesis; this hypothesis will be used to find out the properties of B
min
⁡ in Theorem 12, where we also explain the need for it.Lemma 10.
For a given instance of matrixB, let b
1
,
k
=
1, for all k, 1
≤
k
≤
N, and for a slot j, q
(
j
)
≤
q
(
k
), for all k
≠
j. Then, for any row i, q
s
u
m reduces or remains the same, if b
i
,
j is changed from 1 to 0.Proof.
Letq
sum
old and q
sum
new be the respective sums before and after the conversion of b
i
,
j
=
1 to 0. We need to show that q
sum
old
≥
q
sum
new. Similarly, q
old
(
j
) and q
new
(
j
) can be defined. Since b
1
,
k
=
1, for all k, 1
≤
k
≤
N, the q
old
(
j
) can be written as
(10)
q
old
j
=
1
N
∏
k
=
2
N
‍
1
-
b
k
,
j
β
k
=
1
N
∏
k
=
2
,
k
≠
i
N
‍
1
-
b
k
,
j
β
k
*
1
-
1
β
i
and since b
i
,
j becomes 0, after the conversion, q
new
(
j
) would be
(11)
q
new
j
=
1
N
∏
k
=
2
,
k
≠
i
N
‍
1
-
b
k
,
j
β
k
.
Therefore, from (10) and (11), we get
(12)
q
new
j
-
q
old
j
=
q
old
j
β
i
-
1
.
Similarly, for all other slots k
≠
j and b
i
,
k
=
1,
(13)
q
new
k
-
q
old
k
=
-
q
old
k
β
i
-
1
2
.
To show that q
sum
old
≥
q
sum
new, we calculate q
sum
new
-
q
sum
old as follows:
(14)
q
sum
new
-
q
sum
old
=
∑
k
=
1
N
‍
q
new
(
k
)
-
∑
k
=
1
N
‍
q
old
(
k
)
=
∑
k
=
1
N
‍
q
new
(
k
)
-
q
old
(
k
)
=
∑
k
≠
j
,
b
i
,
k
=
1
‍
q
new
k
-
q
old
k
+
q
new
(
j
)
-
q
old
(
j
)
=
∑
k
≠
j
,
b
i
,
k
=
1
‍
-
q
old
(
k
)
β
i
-
1
2
+
q
old
(
j
)
β
i
-
1
=
∑
k
≠
j
,
b
i
,
k
=
1
‍
-
q
old
j
+
q
old
j
-
q
old
k
β
i
-
1
2
+
q
old
(
j
)
β
i
-
1
=
∑
k
≠
j
,
b
i
,
k
=
1
‍
-
q
old
(
j
)
β
i
-
1
2
+
∑
k
≠
j
,
b
i
,
k
=
1
‍
q
old
j
-
q
old
k
β
i
-
1
2
+
q
old
j
β
i
-
1
.
Since the number of 1’s in rowi is β
i, the number of terms in the first summation of above equation would be exactly β
i
-
1. Therefore,
(15)
q
sum
new
-
q
sum
old
=
∑
k
≠
j
,
b
i
,
k
=
1
‍
q
old
j
-
q
old
k
β
i
-
1
2
≤
0
,
∵
q
(
j
)
≤
q
(
k
)
,
∀
k
≠
j
.Lemma 11.
For a given instance of matrixB, let b
1
,
k
=
1, for all k, 1
≤
k
≤
N, and β
i
=
2, for all i, 2
≤
i
≤
N. Then the following holds. For any two columns j and k and, for any row i, such that α
j
>
α
k, b
i
,
j
=
1 and b
i
,
k
=
0, q
s
u
m either reduces or remains the same if the values of b
i
,
j and b
i
,
k are interchanged.Proof.
Considerq
sum
old, q
sum
new, q
old
(
j
), and q
new
(
j
) as defined in Lemma 10. We need to show that q
sum
old
≥
q
sum
new. Here, q
old
(
j
)
=
(
1
/
N
)
*
1
/
2
α
j, q
old
(
k
)
=
(
1
/
N
)
*
1
/
2
α
k, q
new
(
j
)
=
(
1
/
N
)
*
1
/
2
α
j
-
1, and q
new
(
k
)
=
(
1
/
N
)
*
1
/
2
α
k
+
1. Therefore,
(16)
q
sum
new
-
q
sum
old
=
q
new
j
+
q
new
k
-
q
old
j
+
q
old
k
=
q
new
j
-
q
old
j
+
q
new
k
+
q
old
k
=
1
2
α
j
-
1
-
1
2
α
j
+
1
2
α
k
+
1
-
1
2
α
k
=
1
2
α
j
-
1
2
α
k
+
1
≤
0
∵
α
j
>
α
k
.Now we will try to prove thatB
min
⁡ should satisfy a few constraints, in terms of α
i and β
i, 1
≤
i
≤
N, with the help of Lemmas 10 and 11.Theorem 12.
B
min
⁡ has the following properties:(1)
β
i
=
2, for all i, 2
≤
i
≤
N;
(2)
for exactly two columnsj
1 and j
2, α
j
1
=
α
j
2
=
1 and for all other columns k
≠
j
1
,
j
2, α
k
=
2.Proof.
We prove both the properties for two different cases:β
1
=
N and β
1
≠
N.
Case
1 (
β
1
=
N
). The property (
1
) can be proved by contradiction. First, we show that β
i
≥
2, 2
≤
i
≤
N. If β
i
=
1 with b
i
,
j
=
1, for some row i, then node i is in SS state. Therefore, node 1 should have stopped transmitting in slot j, that is, b
1
,
k
=
0, which contradicts our assumption that β
1
=
N. Now, we show that β
i
≤
2, 2
≤
i
≤
N. Let ∃
i
:
β
i
>
2 and A the set of column indexes k for which b
i
,
k
=
1; then ∃
j
∈
A, such that q
(
j
)
≤
q
(
k
), for all k
∈
A, j
≠
k. Therefore, by the virtue of Lemma 10, q
sum reduces or remains the same, if b
i
,
k is changed from 1 to 0. The same process can be repeated till β
i
=
2.
The property(
2
) can also be proved by contradiction. We know that β
1
=
N and β
i
=
2, 2
≤
i
≤
N. Therefore, ∑
j
=
1
N
‍
α
j
=
2
(
N
-
1
). First, we show that α
j
≤
2, 1
≤
j
≤
N. For a column j, α
j
>
2
⇒
∃
k
:
α
k
<
2; otherwise ∑
j
=
1
N
‍
α
j would become less than 2
(
N
-
1
). In this case, for any row i, such that b
{
i
,
j
}
=
1 and b
{
i
,
k
}
=
0, the value of b
{
i
,
j
} and b
{
i
,
k
} can be interchanged by virtue of Lemma 11. This proves that α
j could be either 0, 1 or 2, 1 ≤
j
≤
N. Since, any column can have at most two 1’s, this implies that at most one column of type α
i
=
0 can exist and that also can be increased to 1 by virtue of Lemma 11. Furthermore, the number of columns of type α
i
=
1 cannot be one, since 2
(
N
-
1
) is even. Finally, we can say that number of columns of type α
i
=
1 is exactly 2; otherwise, the total sum will be less than 2
(
N
-
1
).
Case
2 (
β
1
≠
N
). Let q
sum
case
1 and q
sum
case
2 be the corresponding summation for Cases 1 and 2, respectively. The value of q
sum
case
1 would be (
N
+
2
)
/
4
N. We will prove that q
sum
case
1
<
q
sum
case
2 by showing that any perturbation in the matrix corresponding to Case 1 will increase the value of q
sum. We have already proved, in Case 1, that any modification in any of the rows from 2 to row N and leaving row 1 unchanged will increase q
sum. Now, let us change a single entry b
1
,
k
= 1 to 0; that is, node 1 has decided not to transmit in slot k. This only happens when at least one adjacent node i in G has gone to SS state for slot k, which implies that b
i
,
k
=
1 and b
i
,
j
=
0, for all j
≠
k. Let us interchange the row i with row N and column k with column N. In this case, b
1
,
N
=
0, b
1
,
j
=
1, for all j
≠
N, and b
N
,
N
=
1 and b
N
,
j
=
0, for all j
≠
N. Consider the submatrix of size N
-
1 times N
-
1. The minimum value of q
sum which can be achieved by this submatrix would be (
N
+
1
)
/
4
(
N
-
1
). Moreover, q
(
N
)
=
0, because b
1
,
N
=
0. Therefore, q
sum
case
2
=
(
N
+
1
)
/
4
(
N
-
1
)
>
(
N
+
2
)
/
4
N
=
q
sum
case
1.From Theorem9, we know that the q
min
⁡ can be achieved when q
sum is minimum and B
min
⁡ should satisfy the properties as given in Theorem 12. Therefore,
(17)
q
min
⁡
=
1
-
4
*
N
-
1
4
*
N
(
N
-
2
)
*
2
*
N
-
1
2
*
N
2
.The following matrix shows one of suchB
min
⁡ matrix for N
=
4:
(18)
B
min
⁡
=
1
1
1
1
0
0
1
1
0
1
1
0
1
1
0
0
.To calculate the expected runtime of DTSS algorithm, we model the behavior of the system using a discrete time Markov chain (DTMC), with the number of nodes in SS state,X
t, at the beginning of round t, as a random variable. The transition probabilities, π
i
,
j, are defined as follows:
(19)
π
i
,
j
=
n
-
i
j
-
i
q
min
⁡
j
-
i
1
-
q
min
⁡
n
-
j
,
j
≥
i
1
,
i
=
j
=
n
0
,
otherwise
.In this DTMC (see Figure6), all states are transient except state “n” which is an absorbing state. The probability of leaving a transient state “i” is always greater than 0; that is, 1
-
∑
j
>
i
‍
π
i
,
j
>
0. A transient state cannot be visited again, once it is left. This shows that the DTSS algorithm converges in a finite time. Let τ
i be the number of rounds required to reach state “n” starting from state “i.” Our goal is to find E
[
τ
0
], which can be calculated using the following recurrence relation:
(20)
E
[
τ
i
]
=
1
+
∑
j
=
0
n
‍
π
i
,
j
E
[
τ
j
]
,
1
≤
i
≤
n
-
1
0
,
i
=
n
.Figure 6
Discrete time Markov chain (DTMC) with number of nodes in SS state as random variable, assuming the probability of entering SS state, asq
min
⁡, for each node in the network.Note that the above DTMC is the approximation of actual stochastic process, where the transition probabilities not only depend upon the number of nodes in SS state, but also depend on exact nodes belonging to SS state.We show that the value ofE
[
τ
i
] is greater than actual expected time required to reach state “n” starting from state “i” in DTMC, by proving that the transition probability of moving from i nodes in SS state to j nodes in SS state, in an actual stochastic process, is always greater than π
i
,
j. We know that the probability of each node moving from CS state to SS state in a round is always greater than q
min
⁡(17) and therefore the probability that, out of n
-
i nodes in CS state, exactly j
-
i nodes enter into the SS state is greater than (n
-
i
j
-
i)(
q
min
⁡
)
j
-
i
(
1
-
q
min
⁡
)
n
-
j
=
π
i
,
j.Figure7 shows the graph for E
[
τ
0
] along with function log
⁡
n
/
q
min
⁡. The graph shows that E
[
τ
0
] is upper bounded by log
⁡
n
/
q
min
⁡, and therefore, for a fixed frame size, E
[
τ
n
] is O
(
log
⁡
n
). We know from (17) that q
min
⁡ depends only upon N, which is a measure of two-hop network density (δ).Figure 7
Runtime performance of DTSS algorithm in terms of number of rounds (frames) with respect to number of nodes in the network and its comparison with the function,log
⁡
n
/
q
min
⁡.Another method to analyze the expected runtime of DTSS algorithm is to calculate the expectation of maximum of allX
i’s, where X
i is the time taken by node i to reach SS state. Consider
(21)
E
X
max
⁡
=
E
max
⁡
X
1
,
X
2
,
X
3
,
…
,
X
n
.
The X
is can be assumed as i.i.d (independent and identically distributed) geometric random variable with parameter q
min
⁡. In this case the E
[
X
i
] would be higher than the actual expected time to enter SS state, by node i. The value of E
[
X
max
⁡
] can be calculated as
(22)
E
X
max
⁡
=
∑
k
≥
0
‍
P
X
max
⁡
>
k
=
∑
k
≥
0
‍
1
-
P
X
max
⁡
≤
k
=
∑
k
≥
0
‍
1
-
P
X
i
≤
k
n
=
∑
k
≥
0
‍
1
-
1
-
1
-
q
min
⁡
¯
k
n
,
where q
min
⁡
¯
=
1
-
q
min
⁡. By considering the above infinite sum as right and left hand Riemann sum approximations [29] of the corresponding integral, we obtain
(23)
∫
0
∞
‍
1
-
1
-
q
min
⁡
¯
k
n
≤
E
[
X
max
⁡
]
≤
1
+
∫
0
∞
‍
1
-
1
-
q
min
⁡
¯
k
n
.With the change of variableu
=
1
-
q
min
⁡
¯
k, we have
(24)
E
X
max
⁡
≤
1
+
1
log
⁡
q
min
⁡
¯
∫
0
1
‍
1
-
u
n
1
-
u
d
u
=
1
+
1
log
⁡
q
min
⁡
¯
∫
0
1
‍
(
1
+
u
+
⋯
+
u
n
-
1
)
d
u
=
1
+
1
log
⁡
q
min
⁡
¯
1
+
1
2
+
⋯
+
1
n
≈
1
+
log
⁡
n
log
⁡
q
min
⁡
¯
.From (24), we can conclude that E
[
X
max
⁡
] is the O
(
log
⁡
n
), for a fixed neighborhood density, δ. We know from (17) that q
min
⁡ depends only upon N, which is a measure of δ. A more rigorous analysis on expectation of the maximum of IID geometric random variables can be found in [30].


## 7. Simulation Results

We have used Castalia simulator [27] to study the performance of DTSS algorithm. A multihop network, based on TelosB node hardware platform that uses CC2420 transceiver [28] for communication, is used in the simulation. The transceivers run at 250 kbps data rate and  dbm transmission power which approximately gives 40 m of transmission range in the absence of interference. All nodes are distributed randomly within 250 m × 250 m area. Note that, at 250 kbps, it takes about 0.5 ms to transmit a packet of size 128 bits (80 bits for the MAC header, and 48 bits for L
2 and state payload). Hence, we set TDMA time slots to a period of 1 ms, which is sufficiently long for the transmission of REQ/RES messages. The performance of protocol has been averaged over 100 simulation runs. The neighborhood size of the network is changed by varying the number of nodes from 50 to 300. This setup produces topologies with different neighborhood density, δ, values varying between 5 and 50.Figure8 shows the average number of slots taken by all the nodes to decide their slot in case of broadcast scheduling for frame sizes δ and 1.3
δ, respectively. The error bars denote 95% confidence intervals. Figure 8 shows that runtime increases linearly with neighborhood density, δ. Given slot size as 1 ms, the total runtime for very high density network with δ
=
N
=
50 is approximately 7 s. Furthermore, if we take more slots per frame, then runtime decreases and also confidence interval improves.Figure 8
Runtime performance of DTSS algorithm with respect to network network density,δ, and the effect of taking the number of slots more than δ.Figure9 shows the average of the number of slots taken by all the nodes to decide their slot in case of broadcast scheduling for varying N values starting from δ. Figure 9 shows that the runtime reduces rapidly with small increase in N and further increase in Δ does not have much impact on runtime. This fact can be utilized as a tradeoff between runtime and frame length.Figure 9
Runtime performance of DTSS algorithm with respect to number of slots in frame,N.Figure10 shows the average of the number of slots taken by all the nodes to decide their slot for varying the number of receivers (unicast to broadcast) with δ
=
N
=
40. Figure 10 suggests that unicast or link scheduling can be performed in less than one second for a network with fairly high network density.Figure 10
Runtime statistics of DTSS algorithm to show the performance with respect to unicast (R
i
=
1), multicast, and broadcast (R
i
>
1) mode of transmissions.We now compare DTSS with DRAND [12] and DD-TDMA [13]. Figure 11 shows the performance results of DTSS along with DRAND and DD-TDMA with respect to runtime of each algorithm. The comparison is based on broadcast transmission because both DRAND and DD-TDMA only implement this mode of transmission. The primary reason of getting less runtime is because the DTSS generates a feasible schedule when the number of available slots is already fixed, whereas other algorithms try to generate a suboptimal schedule by using greedy approach, which is inherently sequential. In case of unicast and multicast scheduling, the DTSS even takes lesser time to compute the schedule as compared to broadcast transmission. The number of slots taken by DTSS is always δ as shown in Figure 12, whereas the number of time slots taken by DRAND and DD-TDMA can be less than δ.Figure 11
The runtime performance comparison of DTSS algorithm against DRAND and DD-TDMA, with respect to network density,δ.Figure 12
A comparison on frame size of DTSS algorithm against DRAND and DD-TDMA, with respect to network density,δ.


## 8. Conclusions and Future Work

For many applications in WSNs, efficiently handling the spatially correlated contention is an important requirement. The DTSS takes very less time to perform the scheduling as compared to other existing distributed scheduling algorithms. We have shown that the runtime of DTSS algorithm isO
(
n
) and O
(
log
⁡
(
n
)
) for single-hop and multihop WSNs, respectively, and therefore it is scalable for WSNs with large number of nodes. The interference model used by DTSS is more realistic than conventional protocol interference model. Additionally, the DTSS has a unique feature of unified scheduling in which simultaneously a few nodes can take a slot for unicast, while other nodes can take it for multicast or broadcast purpose. Although the number of slots taken by DTSS is bounded by Δ, further efforts can be applied to reduce the number of slots. In future, we plan to work on the variation of DTSS algorithm, for the situation, when nodes are not assumed to be synchronized before performing the slot scheduling.



---

*Source: 234143-2015-02-28.xml*