# Optimal Multi-TDMA Scheduling in Ring Topology Networks

Authors: Gergely Vakulya; Zsolt Tuza; Gyula Simon
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A scheduling algorithm will be proposed for wireless ring topology networks, utilizing time division multiple access (TDMA) with possible simultaneous operation of nodes. The proposed algorithm finds the optimal schedule to minimize the turnaround time for messages in the network. The properties of the algorithm are mathematically analyzed and proven, and practical test results are also provided.


---

## Body

## 1. Introduction

Sensor networks consist of sensor nodes which can measure various parameters of their environment, make computations, and communicate with each other. Sensor nodes are resource constrained devices, but despite the simplicity of a single device the whole network can solve various tasks efficiently, where the use of other kind of systems is inefficient or impossible [1].Data dissemination is a common service in wireless sensor networks. Communication patterns may differ greatly in networks depending on the application. The most common tasks are as follows:(i)
convergecast, where information from network nodes is directed to a sink node; this is a typical task in data collection applications;(ii)
broadcast, where information from a source node is transmitted to all network nodes, used mainly to send commands into the network;(iii)
peer-to-peer, where any node can send information to any other node; used in distributed computing, where local communication is required.A special kind of broadcast is when any node can serve as source; thus the communication pattern is any-to-all. This pattern was used for example in decentralized security systems, when all nodes were able to make decisions, based upon all the available information in the network. A possible solution is the ring topology, where information flows along a circle in the network [2]. This paper focuses on this communication pattern.Communication networks use either contention based or contention free channel access mechanisms. The advantage of contention based protocols is their dynamism and simplicity. Nodes can compete for channel access when communication is required; thus channel bandwidth is allocated on demand. However, when channel demand is high, frequent collisions may severely decrease network efficiency [3]. Due to the inherently asynchronous nature of contention based communication, in many implementations nodes are continuously switched on, which has a negative impact on power efficiency. To decrease the effect of idle listening, many sophisticated MAC protocols have been developed, for example, RAW [4], S-MAC [5], and μ-MAC [6].Contention free or schedule based protocols use preallocation schemes (e.g., time division multiple access, TDMA); thus the communication can be performed in the preallocated slots, avoiding collisions. However, systems with fixed assignments may be inefficient, when the preassigned slots are poorly utilized. This problem can be handled by on-demand assignment at the price of network overhead [7].Efficient TDMA schedules provide optimal performance, where optimality may be defined by various design objectives, depending on the application requirements. Design objectives can be short schedule length, minimal latency, or minimal power consumption, just to name few (see [8] for a comprehensive list). To achieve the desired design objectives, time slices may be used by multiple nodes to transmit messages, if these transmissions do not interfere with each other. Such reuse of time slots will be referred to as multi-TDMA schedule, which is an NP-complete problem in general [9]. Various heuristics were proposed to calculate multi-TDMA schedules, most of them providing solutions, which are suboptimal, but still acceptable in practice. A review on TDMA protocols in wireless sensor networks can be found in [9]. The most widely studied topology is tree topology [8], but other topologies (e.g., line and star) were also examined [10]. TDMA scheduling in ring topology, to our best knowledge, was not specifically studied.TDMA scheduling in ring networks, when only one node can transmit in a time slot, is a trivial task in itself. In this case consecutive nodes in the network are assigned to consecutive time slots in the schedule. We will refer to this simple case as linear scheduling. The problem, however, becomes much more complicated, when network characteristics allow multi-TDMA schedule. In this paper, we provide algorithms that are able to efficiently solve the multi-TDMA scheduling problem in ring topology, with minimal worst-case message turnaround time, as design objective.Note that message turnaround time, in our approach, includes not only the time the message spends in the network (usually used as design objective) but also the delay from the appearance of the information (e.g., measurement by a sensor) to the injection of the message into the network. We call this approach Minimum Worst Case Turnaround Time(MWCTT)problem. Since both delay components in worst case depend on the parameters of TDMA schedule, the schedule may be optimized to include both components, providing more realistic objective for time-critical systems.The novelties of the paper are the following.(i)
The Minimum Worst Case Turnaround Time problem is defined.(ii)
A novel scheduling algorithm will be proposed which supports multi-TDMA scheduling in ring topology networks. The proposed algorithm guarantees optimal scheduling for the MWCTT problem and still has polynomial computational complexity. The correctness, complexity, and performance of the proposed algorithm will be mathematically analyzed and proven.(iii)
An accelerated version of the optimal scheduling algorithm will also be introduced. The accelerated version also provides optimal solution but requires much shorter computational time in most practical cases.(iv)
The performances of the proposed algorithms are compared to a reference naive breadth first search algorithm.(v)
The properties of the generated optimal schedules are also analyzed in terms of speed and power consumption.(vi)
The performance of the generated schedules are compared, using the proposed algorithm and a reference method.In Section2 related work is reviewed. In Section 3 a mathematical formalization will be given, including the definition of the MWCTT problem, followed by the definition of the new scheduling algorithms for multi-TDMA rings, and finally the properties of the algorithms (optimality and complexity) will be proven. In Section 4 further analytical properties (delivery time and power consumption) will be discussed, along with a performance comparison. Section 5 provides test results, and the performance of the proposed algorithms is analyzed using real implementation. Section 6 concludes the paper.


## 2. Related Work

Most TDMA scheduling algorithms use the high level protocol model, where a connectivity graph represents the network, the vertices, and edges corresponding to nodes and communication links, respectively. In this model the goal is to create a schedule where two constraints are satisfied: (C1) a node cannot receive and transmit at the same time slot, and (C2) two transmissions are not allowed to interfere with each other; that is, if more transmitters are scheduled in the same time slot, no link can be present from a transmitter to the receiver of another transmitter [11]. Some algorithms use the physical model, where the communication links and potential collisions are more accurately modelled by the signal-to-interference-plus-noise-ratio, resulting in potentially more accurate, but usually more complicated, models. In general, protocol-based models provide more pessimistic results, where as much as 30 percent of the network capacity may be lost, compared to accurate physical model-based scheduling [12].Depending on the application requirements, TDMA design objectives may be very different. In applications, where message latency is important, TDMA schedulers use latency-related metrics, for example, schedule length, or average message latency [9, 10, 13]. In networks, where large amount of data must be delivered, throughput capacity [14] and fairness [15] may be maximized. In many applications energy utilization and thus network lifetime is a key design factor; in these cases energy efficiency is the main design objective [16, 17]. Some solutions address multiobjective scheduling [8, 13, 18].The most widely studied network topology is tree topology (e.g., [8, 19]), but also line [10] and arbitrary topologies [11] were investigated. Scheduling algorithms also consider various data models. Most networks are designed to primarily perform data collection (convergecast) or data dissemination (broadcast) tasks [10], but other objectives, for example, small round trip delays, were addressed as well [20]. Some algorithms take into consideration varying data intensity as well [10, 21].The TDMA scheduling problem is known to be NP-complete, since it is equivalent to the graph coloring problem [8, 9]. Since the problem is hard to solve in general, several approximate solutions were proposed to provide computable schedules, even if they are suboptimal. The scheduling problem in most cases may be transformed to coloring of the conflict graph, the nodes of which are edges of the connectivity graph, and its edges represent conflicting links, according to constraints C1 and C2 [11]. Since the coloring problem is NP-complete in general, various heuristics were proposed. For tree topologies, in [9] two heuristics were proposed, the effectiveness of which was shown to depend on packet generation density in the network. In [22] the conflict graph was expanded to represent the size of the subtree, connected to a parent node, and the coloring was done on the expanded conflict graph, using an approximate coloring algorithm.In [19] the Minimum Information Gathering Time Problem was solved, providing shortest time schedule for data collection applications, where each node sends one message in every period towards a sink node. The optimal solution was provided for line and tree topologies, for general networks heuristics were proposed. A similar problem was solved in [21], using Integer Linear Programming formulation.A unified approach was proposed in [11] for a wide class of channel assignment problems, including TDMA. In this framework the search for the solution is aided by a heuristic labelling step, which is followed by the graph coloring step, where the order of the coloring is determined by the labels. The scheduler is simple and fast but the optimum is not guaranteed.Ring topology networks are special type of a broadcast networks, where every node can send information to every other node (all to all) [23]. A ring is selected from the communication graph (Hamiltonian cycle), along which is a linear TDMA schedule is generated.Creating a ring in an ad hoc wireless network is not a trivial problem; it is equivalent to finding a Hamiltonian cycle in the connectivity graph of the network, which is not only NP-hard in general, but not constant approximable even in special cases like cubic Hamiltonian graphs [24]. Based on Pósa’s seminal rotational algorithm [25], several heuristics have been proposed to enhance the efficiency of the search method, for example, by applying precheck mechanisms to increase the probability of the right choices during the search [26], or by avoiding backtracking [27]. Fiedler vectors can be used to find pseudo-Hamiltonian cycles [28]. A semiautomatic heuristic approach, especially the one designed for connectivity graphs of sensor networks, was proposed in [29].TDMA in ring topology was addressed in [30], where the clocks of the nodes were automatically and evenly distributed to create a stable TDMA ring network. Extended ring topologies were used in [23] to represent network hierarchy. A heuristic TDMA scheduling algorithm for such extended ring topologies was proposed in [31]. The heuristic approaches provide in most cases practically acceptable results, but they cannot guarantee optimal scheduling.In this paper multi-TDMA scheduling in ring topology networks is addressed, where multiple nodes are allowed to transmit in the same time slot, if network topology allows collision-free communication. The goal is to find optimal schedule with shortest turnaround time, as design objective. We will prove that optimal multi-TDMA scheduling is possible in polynomial time, and two scheduling algorithms will be proposed and analyzed.


## 3. Linear and Multi-TDMA Scheduling

### 3.1. Basic Principles

The TDMA approach uses dedicated time slices for the transmitter nodes to avoid collisions. The linear round-robin TDMA operates with a predefined periodic schedule. The periods are divided into time slices and each time slice is assigned to one transmitter-receiver pair. The nodes are arranged in a cycle. In the first time slice the first transmitter node transmits a packet to its neighbor, and in every later time slice the node that has just received the message in the previous time slice transmits a packet to its neighbor. In the last time slice the last node will transmit to the first one and this period is repeated, as shown in the example with 16 nodes in Figure1. The figure indicates time instants when nodes are transmitting. In linear round-robin TDMA the number of time slices in a period is equal to the number of nodes.Figure 1
Timing diagram of a linear TDMA schedule for 16 nodes. Each node uses exclusively one time slice for transmission. Two periods are shown, each requiring 16 time slices.Multi-TDMA allows more nodes to transmit at the same time, provided the transmitters do not disturb the messages of each other. Figures2 and 3 show two possible multi-TDMA schedules for 16 nodes. In Figure 2 the length of the period is 6 and the period must be repeated 3 times in order that a message reaches all nodes in the network and arrives back to node 1. In Figure 3 the period length is 7 and 4 periods are required to deliver a message to all of the nodes and return it back to node 1. In both examples maximum 3 nodes transmit at the same time. (Naturally nodes scheduled for the same time slices must not interfere with each other.)Figure 2
Timing diagram of a multi-TDMA schedule for 16 nodes. Independent transmissions are scheduled for the same time slice. A period requiresc=6 time slices. In this example k=3 periods are required to deliver a message from any node to all other nodes.Figure 3
Timing diagram of a multi-TDMA schedule for 16 nodes. Independent transmissions are scheduled for the same time slice. A period requiresc=7 time slices. In this example k=4 periods are necessary for a message to turn around.Utilization of multi-TDMA networks can be advantageous if short message delay is required. Suppose that a node detects an event and sends a message about it to the network. For the linear TDMA schedule in Figure1, the worst case turnaround time from the detection until all nodes receive the message and it gets back to the source node is 32 time slots; the source node must wait at most 16 time slots from the detection until its scheduled transmission time slot and then 16 time slots are required to propagate the message to all other nodes and get it back. In Figure 2, where multi-TDMA schedule is used, the worst case turnaround time is only 24 time slots (6 time slices to start the transmission and 3·6 to propagate the message). Note that inappropriate multi-TDMA schedules may give larger propagation delay than the linear schedule, as in the example of Figure 3, where the worst case delay is 35 (7+4·7) time slots.


### 3.2. Design Objective

The multi-TDMA scheduling to be proposed implements a data dissemination service, where the information, originating at any node, is disseminated to every other node in the network, along the path defined by the ring topology.The design objective is to minimize the worst case turnaround time, introducing the Minimum Worst Case Turnaround Time (MWCTT) problem. The MWCTT is measured from the time point when the information (e.g., measurement or alert) to be disseminated appears asynchronously in the initiator node, to the time point when messages in the ring topology network reach the initiator node again. This scenario models the real-life situation when a node sends an alert to the network and waits for the reactions of other nodes.As shown in Section3.1, MWCTT consists of two components. First the initiator node has to wait for its transmission time slice, which requires c time slices in worst case, where c is the lenght of a period, for example, in Figure 2, c=6, while in Figure 3, c=7. Note that the worst case scenario is when the information to be disseminated appears at the initiator node just after it has begun its transmission. After the initiator node transmitted the message into the network, the message must reach all the other nodes and arrive back to the initiator node, which requires k·c time slices, where k is the necessary number of the repetitions of the periods (e.g., in Figure 2, k=3, while in Figure 3, k=4). Thus the worst case dissemination time is equal to WCTT=c+c·k=c·(k+1) time slices. The goal of the scheduling is to minimize WCTT.


### 3.3. Mathematical Formalization

The network is represented by a connectivity graphC=(N,L), where N denotes the set of vertices corresponding to the sensor nodes and L denotes the set of edges representing the links between nodes. The cardinality of N is denoted by n.Thelq:L→0,1link quality function shows the quality of the links according to a predefined metric. Only the links with link quality greater than a threshold z should be used for communication. LC denotes the set of possible communication links:
(1)LC={p∈L∣lq(p)>z},
and the CCcommunication graph is defined as follows:
(2)CC=(N,LC).Note that the weaker links also have to be considered in multi-TDMA scheduling, because even weaker signal strength levels may cause collisions when a receiver hears multiple transmitters at the same time.Figure4 shows a 16-node example, where continuous lines denote good links (with lq>z), while dashed lines denote weaker links (with 0<lq≤z).Figure 4
A possible connectivity graph (continuous and dashed lines) and communication graph (continuous lines only).In the discussed communication model each node transmits to the next node; therefore, a Hamiltonian cycle must exist inCC. Without loss of generality it can be assumed that N={N1,…,Nn} and the edges of the Hamiltonian cycle are (N1,N2),(N2,N3),…,(Nn-1,Nn),(Nn,N1), as shown in Figure 4 for n=16.


### 3.4. Definitions

Definition 1.
Each nodeNi transmits to itsreceiver node, denoted by r(Ni):
(3)r(Ni)=N(imod⁡n)+1.Definition 2.
TheGI=(N,I)transmission-interference graph (or constraint graph) represents transmitter interferences. There is an edge between two nodes if they should not transmit in the same time slice, because of C1 and C2; that is,
(4)p,q∈Iifp,rq∈Lorq,rp∈Lorq=rporp=rq.Definition 3.
A set of nodes inGI ispolite if all nodes in the set can transmit in the same time slice without collision. POL is the set of the polite transmitter-sets; that is,
(5)POL=T⊆N∀p,q∈T,p≠q:p,q∉I.Definition 4.
Aschedule is a sequence of node-sets S=(S1,…,Sl), where Si⊆N and l is the length of the schedule, such that Si contains the transmitting nodes for the ith time slice of the schedule. Each node transmits exactly once in the sequence to its receiver node; that is,
(6)1≤i<j≤l:Si∩Sj=∅,∀i,j,⋃1≤i≤l‍Si=N.
Figure5 shows the schedule shown in Figure 3, where S1={N1,N11}, S2={N2,N5,N12}, S3={N3,N6,N14}, S4={N4,N7,N13}, S5={N8}, S6={N9,N15}, and S7={N10,N16}.
Note that the schedule describes the operation of the network for exactly one period; such periods are repeated periodically and in each period the nodes are operated according to the schedule.Figure 5
The schedule connection graph for the example shown in Figure3. The schedule itself is represented by S1,S2,…,S7. Its width is 4, as shown by the 4 monochromatic paths.Definition 5.
To a given scheduleS, aschedule connection graphJ(S)=(N,Y) is defined, where
(7)p,q∈Yif∃i,j:i<j,p∈Si,q∈Sj,q=r(p).
The meaning of edge(p,q) is that node q can retransmit the message received from node p, in a subsequent time slicein the same period. Figure 5 shows the schedule connection graph as well, for the schedule shown in Figure 3. There is an edge between node 2 and node 3, because the message received from node 2 in time slice 2 can be retransmitted by node 3 to node 4 in time slice 3, in the same period. Similarly, node 4 can transmit to node 5 in the same period; therefore, there is an edge between node 3 and node 4. But node 5 cannot retransmit the message, received from node 4, in the same period: node 5 can transmit only in time slice 2 of the next period. Therefore, there is no edge between node 4 and node 5.Definition 6.
Thewidth of scheduleS is the number of independent components in the schedule connection graph J(S).In Figure5 the width of the schedule is 4. Note that the width has an important practical meaning. If the width of the schedule is k then the schedule must be repeated k times in order to deliver a packet from any node to all other nodes.Definition 7.
Assuming that the Hamiltonian cycle has been partitioned into connected parts (i.e., subpaths), asegment is the node-set of any of those parts.Note that the independent paths in the schedule connection graph are (independent) segments. In Figure5 red, blue, green, and brown paths correspond to independent segments. Thus the following definition naturally follows.Definition 8.
For anyk-wide schedule asegmentationR=(R1,…,Rk) can be defined on the Hamiltonian cycle, where Ri=(Ri,1,…,Ri,li) is a segment such that (R1,1,…,R1,l1,…,Rk,1,…,Rk,lk)=(N1,…Nn), where the length of the ith segment is li and the vertices of Ri are denoted with Ri,1,…,Ri,li.
Note that ak-wide schedule contains k independent segments, such that the union of the segments is N.
In Figure6 the segmentation for the schedule of Figure 5 is shown.Figure 6
Segmentation of the Hamiltonian cycle.Definition 9.
Given a segmentationR, thestateP=R1,i1,R2,i2,…,Rk,ik is a list of nodes where node Rj,ij, 0≤ij≤lj is the node which transmitted for the last time in segment j. If in segment j there was no transmission yet then notation Rj,0=⊗ is used. The state representing that no transmission has occurred yet is denoted by ⊗,⊗,…,⊗=(⊗)k. The ith element of state P, corresponding to segment Ri, is denoted by P[i].For the construction of ak-wide schedule the directed graph AR=(G,D) is used. The vertices in AR denote the states of the schedule. The edges of the graph define possible sequences of states representing valid schedules.Notice that state transition(P,Q)∈D means that the set of actual transmitters is
(8)⋃i=1k‍{Q[i]}∖{P[i]}.The highlighted part of Figure7 shows the states and state transitions corresponding to the schedule in Figure 5. The state graph starts from state (⊗)4=⊗,⊗,⊗,⊗. After the time slice corresponding to S1, nodes 1 and 11 are the nodes which transmitted for the last time from their segments (from the other two segments no transmission has happened yet); thus the corresponding state is N1,⊗,N11,⊗. After the time slice of S2 nodes 2, 5, and 12 were the last transmitters in their segments, resulting state N2,N5,N12,⊗. After the time slice of S3 nodes 3, 6, 12, and 14 are the last transmitters, with the corresponding state of N3,N6,N12,N14. Note that no node transmitted from the segment of node 12 (along the green path in Figure 5) in the actual time slice; therefore, in this case node 12 remains in the state.Figure 7
A subgraph of the state graph. The highlighted path leads to an optimal schedule.The formal definition ofAR is as the follows.Definition 10.
For a segmentationR=(R1,…,Rk), AR=(G,D) is called thestate graph of segmentation R. The nodes in the node set G of AR represent the states which may occur in a schedule compatible with R. The edges of the state graph are defined as follows.
(
P
,
Q
)
∈
D if(TR1)
∀i:Q[i]≠⊗∧P[i]=⊗⇒Q[i]=Ri,1; that is, in any segment Ri the first node (Ri,1) will transmit for the first time;(TR2)
∀i:P[i]≠⊗⇒Q[i]≠⊗. It expresses the trivial requirement that if once a node has transmitted in a segment, any later time there is one node in that segment, which transmitted for the last time;(TR3)
∀i:P[i]≠⊗⇒V∨W, where V=(Q[i]=P[i]), W=(P[i]=Ri,j∧Q[i]=Ri,j+1∧j<li); that is, after a node transmits in the segment, its receiver node will transmit either in the next time slice (condition W), or in a later time slice, in which case the currently latest transmitter node remains unchanged (condition V);(TR4)
⋃i=1k{Q[i]}∖{P[i]}∈POL; that is, only a polite transmitter-set is allowed to transmit in one time slice.
Rules (TR1)–(TR4) are thetracing rules.


### 3.5. The FSS Algorithm

In this section first the fixed-segmentation-scheduler (FSS) then the optimal-multi-TDMA-scheduler (OMTS) algorithm will be introduced.The pseudocode of the FSS algorithm is shown in Pseudocode1. Notes on notations are the following.(i)
dequeue(L) removes the first element of list L, while enqueue(L,X) adds X to the end of list L, see lines (16), (21), and (27).(ii)
reverse(L) returns reverse of list L.(iii)
parent(Q) represents the state from which state Q was traced; see lines (22) and (26).Pseudocode 1:The pseudocode of the FSS algorithm.
FIXED-SEGMENTATION-SCHEDULER(FSS)
(1)input
(2)C=(N,L): connectivity graph
(3)CC=(N,LC): communication graph
(4)R={R1,…,Rk}: set of segments
(5)variables
(6)G^: set of traced nodes in A
(7)O: list of open nodes in A
(8)P: the currently traced node
(9)T: a possible combination of transmitting segments
(10)Q: set of possible nodes with directed arc from node T
(11)parent: mapping from nodes to nodes
(12)begin
(13)G^={(⊗)k}
(14)O=((⊗)k)
(15)while  ER∉O
(16)P←dequeue(O)
(17)foreach  T  in  P(R)∖∅
(18)Q={Ri,1:Ri∩P=∅,Ri∈T}∪{r(Ri,j):Ri∩P={Ri,j},Ri∈T}
(19)if  (P,Q) satisfies the tracing rules  and  Q∉G^:
(20)G^←G^∪Q
(21)enqueue(O,Q)
(22)parent(Q)←P
(23)Q=ER
(24)S=()
(25)while  Q≠(⊗)k
(26)P=parent(Q)
(27)enqueue(S,⋃i=1k{Q[i]}∖{P[i]})
(28)Q=P
(29)return  reverse(S)
(30)endThe input of the algorithm consists of the connectivity graphC, the communication graph CC, and the segmentation R=(R1,…,Rk). The algorithm builds a graph A^R=(G^,D^), where G^⊆G, D^⊆D, and D^ is represented by the parent() mapping; see lines (17)–(22) of the FSS algorithm.During the iterationsG contains states which are reached by breadth-first search (traced nodes), and O contains states, already in G, from which breadth-first search was not continued yet (open nodes).In the beginning the listO of open nodes contains only the empty set (line (14)) and in each iteration the algorithm traces all possible combinations of transmitting nodes (line (18)) that satisfy the tracing rules (lines (19)–(21)). The schedule is reconstructed from the series of states in A^R from endstate ER to start-state (⊗)k in a backwards manner (lines (23)–(28)).Note that the FSS algorithm calculates the optimum schedule for a given segmentation. The OMTS algorithm enumerates all the possible segmentations and calls the FSS algorithm for each segmentation.The pseudocode of the OMTS algorithm is shown in Pseudocode2. Lines without asterisks give the basic OMTS algorithm. With all lines, including those with asterisk, an accelerated version is given with early cuts (OMTS-A).Pseudocode 2:The pseudocode of the OMTS and the OMTS-A algorithms.
OPTIMAL-MULTI-TDMA-SCHEDULER
(OMTS AND OMTS-A*)
(1)input
(2)C=(N,L): connectivity graph
(3)CC=(N,LC): communication graph
(4)kmax⁡: maximum width of the schedule
(5)variables
(6)minSchLen: the length of the shortest known schedule
(4)k: the actually considered width
(5)startNodes: list of starting k-tuples of the traced segmentations
(6)maxSegLength: length of the longest segment in a segmentation
(7)B: a starting k-tuple of a segmentation
(8)R: a segmentation
(9)SR: an optimal schedule for R
(10)S: an optimal schedule
(11)begin
(12)minSchedLen=∞
(13)for  k=kmax⁡  downto  1
(14)startNodes=()
(15)foreach  B  in  {B:B⊆N∧|D|=k}
(16)startNodes=enqueue(startNodes,B)
(17)*   maxSegLength(B)=
(18)*    max⁡((j-i+n)mod⁡n),i≠j,Ni,Nj∈B
(19)*  sort  startNodes  by  maxSegLengths  increasing  order
(20)foreach  B  in  startNodes
(21)*   if  maxSegLength(B)⋅(k+1)<minSchedLen
(22)R=(R1,…,Rk):Ri,1∈B,1≤i≤k
(23)SR=  FSS(C,CC,R)
(24)if  length(SR)⋅(k+1)<minSchedLen
(25)S=SR
(26)minSchedLen=length(SR)⋅(k+1)
(27)*   else
(28)*    break  (foreach)
(29)return  S
(30)endThe input of the algorithm consists of the connectivity graphC, communication graph CC, and maximal width kmax⁡. Variable len stores the length of the shortest known schedule; it is set to ∞ at the beginning (line (12)). The basic algorithm iterates on widths k from kmax⁡ down to 1 (line (13)); every possible k-tuple is generated as a starting node for the segmentations (line (15)). List startNodes stores the starting points of the segments (line (16)), while mapping maxSegLength stores the length of the longest segment for the corresponding k-tuples (lines (17)-(18)). The algorithm iterates on the list startNodes (line (20)) and generates the actual segmentations (line (22)). For each segmentation the FSS algorithm is executed (line (23)) which returns the shortest schedule SR for the given segmentation.While the OMTS algorithm evaluates all possible segmentations, the OMTS-A algorithm does not call FSS for those cases which trivially results in longer schedules than the current best schedule; since the length of the longest segment is a lower bound for the length of any schedule, during the iterations those segmentations are considered, for whichmaxSegLength<maxSchedLen (see lines (21), (27), and (28)). To increase the efficiency of the early cuts, the segmentations are sorted by maxSegLength before the iterations (lines (17)–(19)).


### 3.6. Algorithm Properties

Lemma 11.
For a given(R1,…,Rk)=((R1,1,…,R1,l1),…,(Rk,1,…,Rk,lk)) segmentation, endstate ER=R1,l1,R2,l2,…,Rk,lk gives the last state of all possible schedules, that is, the last node in all possible paths in the state graph corresponding to the given segmentation.Proof.
Each node has to transmit exactly once in the schedule; therefore, from each segment each node has to be present in at least one state. If a node from a segment is present in stateP, and (P,Q) is an edge of the state graph, then Q will also contain a node from that segment. From each segment nodes appear in increasing order in states belonging to a schedule. Therefore, the last state belonging to a schedule will contain the last nodes from each segment.Lemma 12.
The shortest schedule for a given segmentationR=((R1,1,…,R1,l1),…,(Rk,1,…,Rk,lk)) corresponds to states on a shortest path in graph AR from (⊗)k to the endstate ER.Proof.
For a given segmentation each transition of the state graph describes a time slice of a possible schedule. Thus the length of the schedule is equal to the length of a path in the state graph from(⊗)k to the endstate ER, and any shortest path from (⊗)k to the endstate ER corresponds to one of the shortest schedules.The next lemma guarantees the existence of at least one valid schedule.Lemma 13.
For everyP≠ER there exists a state Q=R1,j1,R2,j2,…,Rk,jk where (P,Q) satisfies the tracing rules.Proof.
SinceP≠ER, there exists i such that Ri,ji≠Ri,li. Let Q[i]=Ri,ji+1 and Q[k]=Rk,jk, k≠i. In this case (P,Q) satisfies the tracing rules since only one node (Ri,ji+1) is transmitting.Definition 14.
For a given stateP=R1,i1,R2,i2,…,Rk,ik and endstate ER=R1,l1,R2,l2,…,Rk,lk the distance between P and ER is defined as D(P)=∑k=1klk-ik. Note that D(P)=0 if and only if P=ER.Lemma 15.
For every two statesP=R1,i1,R2,i2,…,Rk,ik and Q=R1,j1,R2,j2,…,Rk,jk, where (P,Q) satisfies the tracing rules, ΔD<0, where ΔD=D(Q)-D(P).Proof.
ConsiderΔD=D(Q)-D(P)=∑m=1k(lm-jm)-∑m=1k(lm-im)=∑m=1k(lm-jm)-(lm-im)=∑m=1k(im-jm).
According to (TR3) eitherjm-im=0 (case V) or jm-im=1 (case W), for all m. Since at least one value of the state changes (case W), ΔD<0.Lemma 16.
The FSS algorithm stops; that is, eventuallyER∈O and also ER∈G^.Proof.
Let us defineDmin⁡(O)=min⁡D(O[i]) and imin⁡=argmini⁡D(O[i]), 1≤i≤|O|, in each iteration.
Since the algorithm traces elements of queueO after each other (see lines (15)–(23)), in each iteration it is true that the actual state O[imin⁡] will be traced after imin⁡ iterations. Thus according to Lemmas 13 and 15, after imin⁡ iterations Dmin⁡ will decrease.
Repeating this process results in decreasing series ofDmin⁡(O) integer values, thus Dmin⁡(O) eventually reaches 0, where necessarily ER∈O (and also ER∈G^; see lines (21)-(22)). The iteration stops in line (15) and the algorithm terminates after executing lines (23)–(30).Theorem 17.
The list of states, generated by algorithm FSS corresponds to a shortest schedule for the given segmentation.Proof.
LetA^R=(G^,D) be the schedule connection graph generated by the FSS algorithm. (Note that edges in D are implicitly represented by the parent mapping.)
The algorithm starts with the node⊗k (see line (13)); therefore, A^R contains the start-state ⊗k. According to Lemma 16, A^R also contains the endstate ER.
The search mechanism of the algorithm (breadth-first search) provides the shortest path from the start-state to the endstate. Since the algorithm applies the tracing rules (see line(19)), therefore, A^R⊆AR; thus the A^R component of AR, built by the algorithm, contains the shortest path in AR from ⊗k to ER. According to Lemma 12 this path corresponds to one of the shortest paths for the given segmentation.Theorem 18.
The OMTS and OMTS-A algorithms find an optimal schedule for the MWCTT for a given node set, link set, communication link set triplet(N,L,LC), and a maximum width k.Proof.
The OMTS algorithm tries every possible segmentation for the given communication graph. According to Theorem17 the FSS algorithm finds the shortest schedule for each given segmentation. Therefore, OMTS finds the global optimum.
The OMTS-A algorithm also enumerates every possible segmentations but skips the cases where the result would trivially be worse than the current best. Thus OMTS-A also finds an optimal solution.Theorem 19.
If the number of nodes in the communication graph isn then the computational complexity of the OMTS algorithm is a polynomial function of n for a given maximum width kmax.Proof.
The FSS algorithm traces each state in lines(15)–(22). The dequeue operation can run in constant time. The cardinality of P(R)∖∅ is constant for a given k; thus the number of iterations in the loop of lines (17)–(22) is also constant. The set operations, checking of tracing rules, queue, and map updates in the body of the loop in lines (18)–(22) have at most O(n) complexity for a given k. Therefore, the complexity of tracing any state is O(n).
Let the number of states traced by the FSS algorithm (i.e., the number of iterations performed by the loop in lines(15)–(22)) be denoted by IFSS. IFSS clearly cannot be more than the number of all possible states. Let us consider a k-wide segmentation R with segment lengths of l1,l2,…,lk. Then the ith element of a state can be either Ri,1, or Ri,2,…,orRi,li or ⊗ (li+1 possibilities). Therefore the IFSS number of possible states for segmentation R is
(9)IFSS,R=l1+1·l2+1,…,(lk+1).
Using the inequality of arithmetic and geometric means
(10)IFSS,R≤l1+l2+⋯+lk+kkk=n+kkk,
which has the complexity of O(nk). Taking into consideration the complexity of tracing one state (O(n)), the complexity of the FSS algorithm is
(11)CFSS(n)=O(nk·n)=O(nk+1).
TheIOMTS number of iterations when FSS is called in the OMTS algorithm is equal to the sum of the numbers of m-wide segmentations, where m=1,2,…,k:
(12)IOMTSn=nk+nk-1+⋯+n1<nk+nk-1+⋯+n1<k·nk.
Therefore,
(13)IOMTS(n)=O(nk),
and the complexity of the OMTS algorithm can be computed from IOMTS and CFSS as
(14)COMTSn=Onk·nk+1=On2k+1.


## 3.1. Basic Principles

The TDMA approach uses dedicated time slices for the transmitter nodes to avoid collisions. The linear round-robin TDMA operates with a predefined periodic schedule. The periods are divided into time slices and each time slice is assigned to one transmitter-receiver pair. The nodes are arranged in a cycle. In the first time slice the first transmitter node transmits a packet to its neighbor, and in every later time slice the node that has just received the message in the previous time slice transmits a packet to its neighbor. In the last time slice the last node will transmit to the first one and this period is repeated, as shown in the example with 16 nodes in Figure1. The figure indicates time instants when nodes are transmitting. In linear round-robin TDMA the number of time slices in a period is equal to the number of nodes.Figure 1
Timing diagram of a linear TDMA schedule for 16 nodes. Each node uses exclusively one time slice for transmission. Two periods are shown, each requiring 16 time slices.Multi-TDMA allows more nodes to transmit at the same time, provided the transmitters do not disturb the messages of each other. Figures2 and 3 show two possible multi-TDMA schedules for 16 nodes. In Figure 2 the length of the period is 6 and the period must be repeated 3 times in order that a message reaches all nodes in the network and arrives back to node 1. In Figure 3 the period length is 7 and 4 periods are required to deliver a message to all of the nodes and return it back to node 1. In both examples maximum 3 nodes transmit at the same time. (Naturally nodes scheduled for the same time slices must not interfere with each other.)Figure 2
Timing diagram of a multi-TDMA schedule for 16 nodes. Independent transmissions are scheduled for the same time slice. A period requiresc=6 time slices. In this example k=3 periods are required to deliver a message from any node to all other nodes.Figure 3
Timing diagram of a multi-TDMA schedule for 16 nodes. Independent transmissions are scheduled for the same time slice. A period requiresc=7 time slices. In this example k=4 periods are necessary for a message to turn around.Utilization of multi-TDMA networks can be advantageous if short message delay is required. Suppose that a node detects an event and sends a message about it to the network. For the linear TDMA schedule in Figure1, the worst case turnaround time from the detection until all nodes receive the message and it gets back to the source node is 32 time slots; the source node must wait at most 16 time slots from the detection until its scheduled transmission time slot and then 16 time slots are required to propagate the message to all other nodes and get it back. In Figure 2, where multi-TDMA schedule is used, the worst case turnaround time is only 24 time slots (6 time slices to start the transmission and 3·6 to propagate the message). Note that inappropriate multi-TDMA schedules may give larger propagation delay than the linear schedule, as in the example of Figure 3, where the worst case delay is 35 (7+4·7) time slots.


## 3.2. Design Objective

The multi-TDMA scheduling to be proposed implements a data dissemination service, where the information, originating at any node, is disseminated to every other node in the network, along the path defined by the ring topology.The design objective is to minimize the worst case turnaround time, introducing the Minimum Worst Case Turnaround Time (MWCTT) problem. The MWCTT is measured from the time point when the information (e.g., measurement or alert) to be disseminated appears asynchronously in the initiator node, to the time point when messages in the ring topology network reach the initiator node again. This scenario models the real-life situation when a node sends an alert to the network and waits for the reactions of other nodes.As shown in Section3.1, MWCTT consists of two components. First the initiator node has to wait for its transmission time slice, which requires c time slices in worst case, where c is the lenght of a period, for example, in Figure 2, c=6, while in Figure 3, c=7. Note that the worst case scenario is when the information to be disseminated appears at the initiator node just after it has begun its transmission. After the initiator node transmitted the message into the network, the message must reach all the other nodes and arrive back to the initiator node, which requires k·c time slices, where k is the necessary number of the repetitions of the periods (e.g., in Figure 2, k=3, while in Figure 3, k=4). Thus the worst case dissemination time is equal to WCTT=c+c·k=c·(k+1) time slices. The goal of the scheduling is to minimize WCTT.


## 3.3. Mathematical Formalization

The network is represented by a connectivity graphC=(N,L), where N denotes the set of vertices corresponding to the sensor nodes and L denotes the set of edges representing the links between nodes. The cardinality of N is denoted by n.Thelq:L→0,1link quality function shows the quality of the links according to a predefined metric. Only the links with link quality greater than a threshold z should be used for communication. LC denotes the set of possible communication links:
(1)LC={p∈L∣lq(p)>z},
and the CCcommunication graph is defined as follows:
(2)CC=(N,LC).Note that the weaker links also have to be considered in multi-TDMA scheduling, because even weaker signal strength levels may cause collisions when a receiver hears multiple transmitters at the same time.Figure4 shows a 16-node example, where continuous lines denote good links (with lq>z), while dashed lines denote weaker links (with 0<lq≤z).Figure 4
A possible connectivity graph (continuous and dashed lines) and communication graph (continuous lines only).In the discussed communication model each node transmits to the next node; therefore, a Hamiltonian cycle must exist inCC. Without loss of generality it can be assumed that N={N1,…,Nn} and the edges of the Hamiltonian cycle are (N1,N2),(N2,N3),…,(Nn-1,Nn),(Nn,N1), as shown in Figure 4 for n=16.


## 3.4. Definitions

Definition 1.
Each nodeNi transmits to itsreceiver node, denoted by r(Ni):
(3)r(Ni)=N(imod⁡n)+1.Definition 2.
TheGI=(N,I)transmission-interference graph (or constraint graph) represents transmitter interferences. There is an edge between two nodes if they should not transmit in the same time slice, because of C1 and C2; that is,
(4)p,q∈Iifp,rq∈Lorq,rp∈Lorq=rporp=rq.Definition 3.
A set of nodes inGI ispolite if all nodes in the set can transmit in the same time slice without collision. POL is the set of the polite transmitter-sets; that is,
(5)POL=T⊆N∀p,q∈T,p≠q:p,q∉I.Definition 4.
Aschedule is a sequence of node-sets S=(S1,…,Sl), where Si⊆N and l is the length of the schedule, such that Si contains the transmitting nodes for the ith time slice of the schedule. Each node transmits exactly once in the sequence to its receiver node; that is,
(6)1≤i<j≤l:Si∩Sj=∅,∀i,j,⋃1≤i≤l‍Si=N.
Figure5 shows the schedule shown in Figure 3, where S1={N1,N11}, S2={N2,N5,N12}, S3={N3,N6,N14}, S4={N4,N7,N13}, S5={N8}, S6={N9,N15}, and S7={N10,N16}.
Note that the schedule describes the operation of the network for exactly one period; such periods are repeated periodically and in each period the nodes are operated according to the schedule.Figure 5
The schedule connection graph for the example shown in Figure3. The schedule itself is represented by S1,S2,…,S7. Its width is 4, as shown by the 4 monochromatic paths.Definition 5.
To a given scheduleS, aschedule connection graphJ(S)=(N,Y) is defined, where
(7)p,q∈Yif∃i,j:i<j,p∈Si,q∈Sj,q=r(p).
The meaning of edge(p,q) is that node q can retransmit the message received from node p, in a subsequent time slicein the same period. Figure 5 shows the schedule connection graph as well, for the schedule shown in Figure 3. There is an edge between node 2 and node 3, because the message received from node 2 in time slice 2 can be retransmitted by node 3 to node 4 in time slice 3, in the same period. Similarly, node 4 can transmit to node 5 in the same period; therefore, there is an edge between node 3 and node 4. But node 5 cannot retransmit the message, received from node 4, in the same period: node 5 can transmit only in time slice 2 of the next period. Therefore, there is no edge between node 4 and node 5.Definition 6.
Thewidth of scheduleS is the number of independent components in the schedule connection graph J(S).In Figure5 the width of the schedule is 4. Note that the width has an important practical meaning. If the width of the schedule is k then the schedule must be repeated k times in order to deliver a packet from any node to all other nodes.Definition 7.
Assuming that the Hamiltonian cycle has been partitioned into connected parts (i.e., subpaths), asegment is the node-set of any of those parts.Note that the independent paths in the schedule connection graph are (independent) segments. In Figure5 red, blue, green, and brown paths correspond to independent segments. Thus the following definition naturally follows.Definition 8.
For anyk-wide schedule asegmentationR=(R1,…,Rk) can be defined on the Hamiltonian cycle, where Ri=(Ri,1,…,Ri,li) is a segment such that (R1,1,…,R1,l1,…,Rk,1,…,Rk,lk)=(N1,…Nn), where the length of the ith segment is li and the vertices of Ri are denoted with Ri,1,…,Ri,li.
Note that ak-wide schedule contains k independent segments, such that the union of the segments is N.
In Figure6 the segmentation for the schedule of Figure 5 is shown.Figure 6
Segmentation of the Hamiltonian cycle.Definition 9.
Given a segmentationR, thestateP=R1,i1,R2,i2,…,Rk,ik is a list of nodes where node Rj,ij, 0≤ij≤lj is the node which transmitted for the last time in segment j. If in segment j there was no transmission yet then notation Rj,0=⊗ is used. The state representing that no transmission has occurred yet is denoted by ⊗,⊗,…,⊗=(⊗)k. The ith element of state P, corresponding to segment Ri, is denoted by P[i].For the construction of ak-wide schedule the directed graph AR=(G,D) is used. The vertices in AR denote the states of the schedule. The edges of the graph define possible sequences of states representing valid schedules.Notice that state transition(P,Q)∈D means that the set of actual transmitters is
(8)⋃i=1k‍{Q[i]}∖{P[i]}.The highlighted part of Figure7 shows the states and state transitions corresponding to the schedule in Figure 5. The state graph starts from state (⊗)4=⊗,⊗,⊗,⊗. After the time slice corresponding to S1, nodes 1 and 11 are the nodes which transmitted for the last time from their segments (from the other two segments no transmission has happened yet); thus the corresponding state is N1,⊗,N11,⊗. After the time slice of S2 nodes 2, 5, and 12 were the last transmitters in their segments, resulting state N2,N5,N12,⊗. After the time slice of S3 nodes 3, 6, 12, and 14 are the last transmitters, with the corresponding state of N3,N6,N12,N14. Note that no node transmitted from the segment of node 12 (along the green path in Figure 5) in the actual time slice; therefore, in this case node 12 remains in the state.Figure 7
A subgraph of the state graph. The highlighted path leads to an optimal schedule.The formal definition ofAR is as the follows.Definition 10.
For a segmentationR=(R1,…,Rk), AR=(G,D) is called thestate graph of segmentation R. The nodes in the node set G of AR represent the states which may occur in a schedule compatible with R. The edges of the state graph are defined as follows.
(
P
,
Q
)
∈
D if(TR1)
∀i:Q[i]≠⊗∧P[i]=⊗⇒Q[i]=Ri,1; that is, in any segment Ri the first node (Ri,1) will transmit for the first time;(TR2)
∀i:P[i]≠⊗⇒Q[i]≠⊗. It expresses the trivial requirement that if once a node has transmitted in a segment, any later time there is one node in that segment, which transmitted for the last time;(TR3)
∀i:P[i]≠⊗⇒V∨W, where V=(Q[i]=P[i]), W=(P[i]=Ri,j∧Q[i]=Ri,j+1∧j<li); that is, after a node transmits in the segment, its receiver node will transmit either in the next time slice (condition W), or in a later time slice, in which case the currently latest transmitter node remains unchanged (condition V);(TR4)
⋃i=1k{Q[i]}∖{P[i]}∈POL; that is, only a polite transmitter-set is allowed to transmit in one time slice.
Rules (TR1)–(TR4) are thetracing rules.


## 3.5. The FSS Algorithm

In this section first the fixed-segmentation-scheduler (FSS) then the optimal-multi-TDMA-scheduler (OMTS) algorithm will be introduced.The pseudocode of the FSS algorithm is shown in Pseudocode1. Notes on notations are the following.(i)
dequeue(L) removes the first element of list L, while enqueue(L,X) adds X to the end of list L, see lines (16), (21), and (27).(ii)
reverse(L) returns reverse of list L.(iii)
parent(Q) represents the state from which state Q was traced; see lines (22) and (26).Pseudocode 1:The pseudocode of the FSS algorithm.
FIXED-SEGMENTATION-SCHEDULER(FSS)
(1)input
(2)C=(N,L): connectivity graph
(3)CC=(N,LC): communication graph
(4)R={R1,…,Rk}: set of segments
(5)variables
(6)G^: set of traced nodes in A
(7)O: list of open nodes in A
(8)P: the currently traced node
(9)T: a possible combination of transmitting segments
(10)Q: set of possible nodes with directed arc from node T
(11)parent: mapping from nodes to nodes
(12)begin
(13)G^={(⊗)k}
(14)O=((⊗)k)
(15)while  ER∉O
(16)P←dequeue(O)
(17)foreach  T  in  P(R)∖∅
(18)Q={Ri,1:Ri∩P=∅,Ri∈T}∪{r(Ri,j):Ri∩P={Ri,j},Ri∈T}
(19)if  (P,Q) satisfies the tracing rules  and  Q∉G^:
(20)G^←G^∪Q
(21)enqueue(O,Q)
(22)parent(Q)←P
(23)Q=ER
(24)S=()
(25)while  Q≠(⊗)k
(26)P=parent(Q)
(27)enqueue(S,⋃i=1k{Q[i]}∖{P[i]})
(28)Q=P
(29)return  reverse(S)
(30)endThe input of the algorithm consists of the connectivity graphC, the communication graph CC, and the segmentation R=(R1,…,Rk). The algorithm builds a graph A^R=(G^,D^), where G^⊆G, D^⊆D, and D^ is represented by the parent() mapping; see lines (17)–(22) of the FSS algorithm.During the iterationsG contains states which are reached by breadth-first search (traced nodes), and O contains states, already in G, from which breadth-first search was not continued yet (open nodes).In the beginning the listO of open nodes contains only the empty set (line (14)) and in each iteration the algorithm traces all possible combinations of transmitting nodes (line (18)) that satisfy the tracing rules (lines (19)–(21)). The schedule is reconstructed from the series of states in A^R from endstate ER to start-state (⊗)k in a backwards manner (lines (23)–(28)).Note that the FSS algorithm calculates the optimum schedule for a given segmentation. The OMTS algorithm enumerates all the possible segmentations and calls the FSS algorithm for each segmentation.The pseudocode of the OMTS algorithm is shown in Pseudocode2. Lines without asterisks give the basic OMTS algorithm. With all lines, including those with asterisk, an accelerated version is given with early cuts (OMTS-A).Pseudocode 2:The pseudocode of the OMTS and the OMTS-A algorithms.
OPTIMAL-MULTI-TDMA-SCHEDULER
(OMTS AND OMTS-A*)
(1)input
(2)C=(N,L): connectivity graph
(3)CC=(N,LC): communication graph
(4)kmax⁡: maximum width of the schedule
(5)variables
(6)minSchLen: the length of the shortest known schedule
(4)k: the actually considered width
(5)startNodes: list of starting k-tuples of the traced segmentations
(6)maxSegLength: length of the longest segment in a segmentation
(7)B: a starting k-tuple of a segmentation
(8)R: a segmentation
(9)SR: an optimal schedule for R
(10)S: an optimal schedule
(11)begin
(12)minSchedLen=∞
(13)for  k=kmax⁡  downto  1
(14)startNodes=()
(15)foreach  B  in  {B:B⊆N∧|D|=k}
(16)startNodes=enqueue(startNodes,B)
(17)*   maxSegLength(B)=
(18)*    max⁡((j-i+n)mod⁡n),i≠j,Ni,Nj∈B
(19)*  sort  startNodes  by  maxSegLengths  increasing  order
(20)foreach  B  in  startNodes
(21)*   if  maxSegLength(B)⋅(k+1)<minSchedLen
(22)R=(R1,…,Rk):Ri,1∈B,1≤i≤k
(23)SR=  FSS(C,CC,R)
(24)if  length(SR)⋅(k+1)<minSchedLen
(25)S=SR
(26)minSchedLen=length(SR)⋅(k+1)
(27)*   else
(28)*    break  (foreach)
(29)return  S
(30)endThe input of the algorithm consists of the connectivity graphC, communication graph CC, and maximal width kmax⁡. Variable len stores the length of the shortest known schedule; it is set to ∞ at the beginning (line (12)). The basic algorithm iterates on widths k from kmax⁡ down to 1 (line (13)); every possible k-tuple is generated as a starting node for the segmentations (line (15)). List startNodes stores the starting points of the segments (line (16)), while mapping maxSegLength stores the length of the longest segment for the corresponding k-tuples (lines (17)-(18)). The algorithm iterates on the list startNodes (line (20)) and generates the actual segmentations (line (22)). For each segmentation the FSS algorithm is executed (line (23)) which returns the shortest schedule SR for the given segmentation.While the OMTS algorithm evaluates all possible segmentations, the OMTS-A algorithm does not call FSS for those cases which trivially results in longer schedules than the current best schedule; since the length of the longest segment is a lower bound for the length of any schedule, during the iterations those segmentations are considered, for whichmaxSegLength<maxSchedLen (see lines (21), (27), and (28)). To increase the efficiency of the early cuts, the segmentations are sorted by maxSegLength before the iterations (lines (17)–(19)).


## 3.6. Algorithm Properties

Lemma 11.
For a given(R1,…,Rk)=((R1,1,…,R1,l1),…,(Rk,1,…,Rk,lk)) segmentation, endstate ER=R1,l1,R2,l2,…,Rk,lk gives the last state of all possible schedules, that is, the last node in all possible paths in the state graph corresponding to the given segmentation.Proof.
Each node has to transmit exactly once in the schedule; therefore, from each segment each node has to be present in at least one state. If a node from a segment is present in stateP, and (P,Q) is an edge of the state graph, then Q will also contain a node from that segment. From each segment nodes appear in increasing order in states belonging to a schedule. Therefore, the last state belonging to a schedule will contain the last nodes from each segment.Lemma 12.
The shortest schedule for a given segmentationR=((R1,1,…,R1,l1),…,(Rk,1,…,Rk,lk)) corresponds to states on a shortest path in graph AR from (⊗)k to the endstate ER.Proof.
For a given segmentation each transition of the state graph describes a time slice of a possible schedule. Thus the length of the schedule is equal to the length of a path in the state graph from(⊗)k to the endstate ER, and any shortest path from (⊗)k to the endstate ER corresponds to one of the shortest schedules.The next lemma guarantees the existence of at least one valid schedule.Lemma 13.
For everyP≠ER there exists a state Q=R1,j1,R2,j2,…,Rk,jk where (P,Q) satisfies the tracing rules.Proof.
SinceP≠ER, there exists i such that Ri,ji≠Ri,li. Let Q[i]=Ri,ji+1 and Q[k]=Rk,jk, k≠i. In this case (P,Q) satisfies the tracing rules since only one node (Ri,ji+1) is transmitting.Definition 14.
For a given stateP=R1,i1,R2,i2,…,Rk,ik and endstate ER=R1,l1,R2,l2,…,Rk,lk the distance between P and ER is defined as D(P)=∑k=1klk-ik. Note that D(P)=0 if and only if P=ER.Lemma 15.
For every two statesP=R1,i1,R2,i2,…,Rk,ik and Q=R1,j1,R2,j2,…,Rk,jk, where (P,Q) satisfies the tracing rules, ΔD<0, where ΔD=D(Q)-D(P).Proof.
ConsiderΔD=D(Q)-D(P)=∑m=1k(lm-jm)-∑m=1k(lm-im)=∑m=1k(lm-jm)-(lm-im)=∑m=1k(im-jm).
According to (TR3) eitherjm-im=0 (case V) or jm-im=1 (case W), for all m. Since at least one value of the state changes (case W), ΔD<0.Lemma 16.
The FSS algorithm stops; that is, eventuallyER∈O and also ER∈G^.Proof.
Let us defineDmin⁡(O)=min⁡D(O[i]) and imin⁡=argmini⁡D(O[i]), 1≤i≤|O|, in each iteration.
Since the algorithm traces elements of queueO after each other (see lines (15)–(23)), in each iteration it is true that the actual state O[imin⁡] will be traced after imin⁡ iterations. Thus according to Lemmas 13 and 15, after imin⁡ iterations Dmin⁡ will decrease.
Repeating this process results in decreasing series ofDmin⁡(O) integer values, thus Dmin⁡(O) eventually reaches 0, where necessarily ER∈O (and also ER∈G^; see lines (21)-(22)). The iteration stops in line (15) and the algorithm terminates after executing lines (23)–(30).Theorem 17.
The list of states, generated by algorithm FSS corresponds to a shortest schedule for the given segmentation.Proof.
LetA^R=(G^,D) be the schedule connection graph generated by the FSS algorithm. (Note that edges in D are implicitly represented by the parent mapping.)
The algorithm starts with the node⊗k (see line (13)); therefore, A^R contains the start-state ⊗k. According to Lemma 16, A^R also contains the endstate ER.
The search mechanism of the algorithm (breadth-first search) provides the shortest path from the start-state to the endstate. Since the algorithm applies the tracing rules (see line(19)), therefore, A^R⊆AR; thus the A^R component of AR, built by the algorithm, contains the shortest path in AR from ⊗k to ER. According to Lemma 12 this path corresponds to one of the shortest paths for the given segmentation.Theorem 18.
The OMTS and OMTS-A algorithms find an optimal schedule for the MWCTT for a given node set, link set, communication link set triplet(N,L,LC), and a maximum width k.Proof.
The OMTS algorithm tries every possible segmentation for the given communication graph. According to Theorem17 the FSS algorithm finds the shortest schedule for each given segmentation. Therefore, OMTS finds the global optimum.
The OMTS-A algorithm also enumerates every possible segmentations but skips the cases where the result would trivially be worse than the current best. Thus OMTS-A also finds an optimal solution.Theorem 19.
If the number of nodes in the communication graph isn then the computational complexity of the OMTS algorithm is a polynomial function of n for a given maximum width kmax.Proof.
The FSS algorithm traces each state in lines(15)–(22). The dequeue operation can run in constant time. The cardinality of P(R)∖∅ is constant for a given k; thus the number of iterations in the loop of lines (17)–(22) is also constant. The set operations, checking of tracing rules, queue, and map updates in the body of the loop in lines (18)–(22) have at most O(n) complexity for a given k. Therefore, the complexity of tracing any state is O(n).
Let the number of states traced by the FSS algorithm (i.e., the number of iterations performed by the loop in lines(15)–(22)) be denoted by IFSS. IFSS clearly cannot be more than the number of all possible states. Let us consider a k-wide segmentation R with segment lengths of l1,l2,…,lk. Then the ith element of a state can be either Ri,1, or Ri,2,…,orRi,li or ⊗ (li+1 possibilities). Therefore the IFSS number of possible states for segmentation R is
(9)IFSS,R=l1+1·l2+1,…,(lk+1).
Using the inequality of arithmetic and geometric means
(10)IFSS,R≤l1+l2+⋯+lk+kkk=n+kkk,
which has the complexity of O(nk). Taking into consideration the complexity of tracing one state (O(n)), the complexity of the FSS algorithm is
(11)CFSS(n)=O(nk·n)=O(nk+1).
TheIOMTS number of iterations when FSS is called in the OMTS algorithm is equal to the sum of the numbers of m-wide segmentations, where m=1,2,…,k:
(12)IOMTSn=nk+nk-1+⋯+n1<nk+nk-1+⋯+n1<k·nk.
Therefore,
(13)IOMTS(n)=O(nk),
and the complexity of the OMTS algorithm can be computed from IOMTS and CFSS as
(14)COMTSn=Onk·nk+1=On2k+1.


## 4. Analytical Results

To compare the scheduling methods, measurement metrics are defined.


### 4.1. Turnaround Time

Turnaround time, denoted withTT is the time required to deliver a packet from a node to all other nodes and get it back to the source node.In linear TDMA scheduling the worst case delivery time can easily be calculated for ann-node network, as follows. In the network asynchronous events occur (e.g., measurements), for which events the network reacts by sending messages (e.g., alerts). After this event, the node first has to wait for its transmission time slice. The worst case is when the node transmitted just before the measurement event, thus it has to wait a full period (n time slices) for the next transmission time. Second, at most n time slices are required for the message to turn around. Therefore, in the worst case the delivery time is
(15)TT,linear=2n.For ak-wide multi-TDMA schedule a lower bound can be calculated. Let c be the length of the period. In the worst case a node has to wait for c time slices to transmit and k·c time slices are required for the message to turn around; thus
(16)TT,multi=c+k·c=(c+1)·c.
The length of the period must be at least the size of the largest segment in the segmentation; therefore, the following lower bound can be given for c:
(17)c≥nk.
Therefore,
(18)TT,multi≥k+1kn>n=TD,linear2.Note that the maximal gain in delivery time is approximately 2, compared to linear TDMA scheduling. The lower bound is a good approximation, when(i)
the segmentation contains segments with equal size,(ii)
in all time slices one node transmits from each segment,(iii)
k is large.


### 4.2.  Power Consumption

Power consumption can be considered in two different ways. The energy, which is necessary to deliver a packet from a node to all other nodes is denoted byEpacket,linear for the linear TDMA and Epacket,multi for the multi-TDMA scheduling. The average energy consumed in a time slice is denoted by Eavg,linear and Eavg,multi for linear and multi-TDMA, respectively.In our model energyEtx is necessary to transmit and Erx to receive a packet, regardless of other parameters (e.g., link quality).In both linear and multi-TDMA scheduling each measurement is transmitted by each node exactly once. In each time sliceEtx is required for the transmission and Erx is required for the reception of the message containing the measurement. Thus the energy required to broadcast a measurement can be calculated with the following equation for both the linear and the multi-TDMA scheduling:
(19)Epacket,linear=Epacket,multi=n·(Etx+Erx).In linear TDMA scheduling in each time slice exactly one node transmits and one node receives the message; thus the average energy consumption is(20)Eavg,linear=Etx+Erx.In multi-TDMA scheduling each node will receive and transmit once in a period; therefore, the multi-TDMA requires the same energy amount in a period with lengthc as the linear TDMA for a longer period with length n. Thus the average energy consumption for the multi-TDMA scheduling can be calculated with the following equation:
(21)Eavg,multi=nc·(Etx+Erx)=nc·Eavg,linear.Thus the price of faster delivery time is the increase in energy consumption. Sincec≥n/k,
(22)Eavg,multi≤k·Eavg,linear.The average energy consumption is largest when all the segments are equal and there is one transmitter from each segment in each time slice; in this case the multischeduler algorithm consumesk times more energy than the linear one.


## 4.1. Turnaround Time

Turnaround time, denoted withTT is the time required to deliver a packet from a node to all other nodes and get it back to the source node.In linear TDMA scheduling the worst case delivery time can easily be calculated for ann-node network, as follows. In the network asynchronous events occur (e.g., measurements), for which events the network reacts by sending messages (e.g., alerts). After this event, the node first has to wait for its transmission time slice. The worst case is when the node transmitted just before the measurement event, thus it has to wait a full period (n time slices) for the next transmission time. Second, at most n time slices are required for the message to turn around. Therefore, in the worst case the delivery time is
(15)TT,linear=2n.For ak-wide multi-TDMA schedule a lower bound can be calculated. Let c be the length of the period. In the worst case a node has to wait for c time slices to transmit and k·c time slices are required for the message to turn around; thus
(16)TT,multi=c+k·c=(c+1)·c.
The length of the period must be at least the size of the largest segment in the segmentation; therefore, the following lower bound can be given for c:
(17)c≥nk.
Therefore,
(18)TT,multi≥k+1kn>n=TD,linear2.Note that the maximal gain in delivery time is approximately 2, compared to linear TDMA scheduling. The lower bound is a good approximation, when(i)
the segmentation contains segments with equal size,(ii)
in all time slices one node transmits from each segment,(iii)
k is large.


## 4.2.  Power Consumption

Power consumption can be considered in two different ways. The energy, which is necessary to deliver a packet from a node to all other nodes is denoted byEpacket,linear for the linear TDMA and Epacket,multi for the multi-TDMA scheduling. The average energy consumed in a time slice is denoted by Eavg,linear and Eavg,multi for linear and multi-TDMA, respectively.In our model energyEtx is necessary to transmit and Erx to receive a packet, regardless of other parameters (e.g., link quality).In both linear and multi-TDMA scheduling each measurement is transmitted by each node exactly once. In each time sliceEtx is required for the transmission and Erx is required for the reception of the message containing the measurement. Thus the energy required to broadcast a measurement can be calculated with the following equation for both the linear and the multi-TDMA scheduling:
(19)Epacket,linear=Epacket,multi=n·(Etx+Erx).In linear TDMA scheduling in each time slice exactly one node transmits and one node receives the message; thus the average energy consumption is(20)Eavg,linear=Etx+Erx.In multi-TDMA scheduling each node will receive and transmit once in a period; therefore, the multi-TDMA requires the same energy amount in a period with lengthc as the linear TDMA for a longer period with length n. Thus the average energy consumption for the multi-TDMA scheduling can be calculated with the following equation:
(21)Eavg,multi=nc·(Etx+Erx)=nc·Eavg,linear.Thus the price of faster delivery time is the increase in energy consumption. Sincec≥n/k,
(22)Eavg,multi≤k·Eavg,linear.The average energy consumption is largest when all the segments are equal and there is one transmitter from each segment in each time slice; in this case the multischeduler algorithm consumesk times more energy than the linear one.


## 5. Test Results

### 5.1. Computation Time

To test the computational complexity of the scheduling algorithms, both the OMTS and OMTS-A algorithms were implemented in Perl. For reference a brute-force algorithm was also implemented, which did not use the proposed states. For test cases random graphs with controlled numbers of node (n) and link (b) were generated, as follows. n nodes were placed randomly in a square-shaped area and n links for the Hamiltonian cycle were added. Afterwards b-n additional links were added iteratively between the two nodes, which had the shortest distance and no existing link yet. In the test c was chosen as 15% of all the possible number of links; that is, b=0.15·n·(n-1)/2. The value of n varied from 10 to 100. For each n, 10 different random topologies were generated and the average and standard deviation of the runtimes of the three algorithms were measured, where it was feasible. The test platform was a Lenovo Thinkpad T430 with an Intel Core i5-3210M CPU at 2.5 GHz and 8 GB RAM. In the tests k=3 was used. The results are shown in Table 1, where the average and standard deviation values are listed for each experiment. The results are also plotted in Figure 8 in a logarithmic scale, showing the results of all the experiments.Table 1
Computation times of algorithms OMTS, OMTS-A, and brute-force (bf).
n
t
OMTS (s)
t
OMTS-A (s)
t
bf (s)
Avg.
Std. dev.
Avg.
Std. dev.
10
0.3
0.01
0.005
0.005
4.7
11
0.5
0.004
0.014
0.007
28.5
12
0.9
0.02
0.033
0.01
161.4
13
1.5
0.02
0.023
0.01
1578
14
2.3
0.03
0.07
0.05
21 182
15
3.6
0.03
0.08
0.03
—
20
23
0.2
0.22
0.3
—
25
101
0.8
0.6
1.1
—
30
383
33
2.6
0.7
—
40
2380
71
19
25
—
50
12 434
280
107
52
—
60
—
—
228
122
—
70
—
—
1736
261
—
80
—
—
7404
3091
—
90
—
—
11 029
2462
—
100
—
—
64 066
23 836
—Figure 8
Computation times of algorithms OMTS (green), OMTS-A (red), and brute-force (blue).The brute-force algorithm quickly reached the feasibility limit of one day atn=15, the OMTS algorithm could compute schedules for n=40, while OMTS-A was usable even for n=100. The speed differences are clearly shown in Figure 8: the computational time of the brute-force algorithm increases with the number of nodes much faster than in the case of the proposed algorithms. The behavior of algorithms OMTS and OMTS-A are similar, but due to the early cuts, the complexity of OMTS-A is two orders of magnitude lower. Notice the higher variance of OMTS-A, which is due to the fact that the efficiency of early cuts depends largely on the actual topology.Fork=3, used in the tests, the theoretical complexity of the OMTS and OMTS-A algorithms is O(n7), which corresponds well to the measurement results for n≥20.


### 5.2. Performance Comparison

The proposed method is compared to a graph coloring based reference algorithm described in [11]. An example network with 16 nodes was constructed, where 15 nodes form a cycle with symmetrical connections between the neighbors and all nodes in the cycle have symmetrical connection to the central node; see Figure 9(a). The connectivity graph with a Hamiltonian cycle is shown in Figure 9(a) with straight and dashed lines, respectively. From the connectivity graph and the Hamiltonian cycle the constraint graph is constructed for the method described in [11] with constraints C1 and C2, as shown in Figure 9(b).(a) The connectivity graph of the test network (straight lines) and the Hamiltonian cycle (dashed lines). (b) The constraint graph of the network according to the model described in [11].
(a)
(b)Although the method described in [11] contains heuristics to solve the graph coloring problem, in the example of Figure 9 the optimal coloring was found. In Figure 10(a) the constraint graph is colored with 3 colors, which is indeed the minimum, because the graph contains triangles. The sequence of the colors was chosen to be purple → green → blue; that is, purple nodes transmit in time slices t=3m+1, green nodes transmit in time slices t=3m+2 and blue nodes transmit in time slices t=3m   (m∈N).The coloring of the graph according to the method described in [11] (a) and the proposed method (b).
(a)
(b)The optimal schedule found by the proposed OMTS algorithm for the same network is shown in Figure10(b). The optimum was found at k=3 and the graph is colored with 4 colors, with sequence of purple → green → blue → orange.The timing diagrams of the reference and the proposed algorithms are shown in Figure11. The arrows denote the transmission of the information originating from node 1; the dashed vertical lines denote the point, where this information reaches all nodes and is returned back to node 1.The timing diagram of the schedule generated by the reference algorithm (a) and the proposed algorithm (b).
(a)
(b)In Figure11(a) the timing diagram for the reference algorithm is shown. After the information to be disseminated first appears at node 1, the node has to wait for its transmission time slice, which requires 3 time slices in the worst case. From that point the information reaches node 1 again in the 23rd time slice. Thus the propagation of the information requires 3+23=26 time slices.In Figure11(b) the timing diagram for the proposed OMTS algorithm is shown. In worst case, node 1 has to wait 4 time slices to transmit, and the information reaches the last node in the 20th time slice. Thus with this schedule 4+20=24 time slices are required to disseminate the information originating from node 1. The example clearly illustrates the ability of the OMTS algorithm to find the optimal solution in ring topology networks, where messages must be propagated to all other nodes.


## 5.1. Computation Time

To test the computational complexity of the scheduling algorithms, both the OMTS and OMTS-A algorithms were implemented in Perl. For reference a brute-force algorithm was also implemented, which did not use the proposed states. For test cases random graphs with controlled numbers of node (n) and link (b) were generated, as follows. n nodes were placed randomly in a square-shaped area and n links for the Hamiltonian cycle were added. Afterwards b-n additional links were added iteratively between the two nodes, which had the shortest distance and no existing link yet. In the test c was chosen as 15% of all the possible number of links; that is, b=0.15·n·(n-1)/2. The value of n varied from 10 to 100. For each n, 10 different random topologies were generated and the average and standard deviation of the runtimes of the three algorithms were measured, where it was feasible. The test platform was a Lenovo Thinkpad T430 with an Intel Core i5-3210M CPU at 2.5 GHz and 8 GB RAM. In the tests k=3 was used. The results are shown in Table 1, where the average and standard deviation values are listed for each experiment. The results are also plotted in Figure 8 in a logarithmic scale, showing the results of all the experiments.Table 1
Computation times of algorithms OMTS, OMTS-A, and brute-force (bf).
n
t
OMTS (s)
t
OMTS-A (s)
t
bf (s)
Avg.
Std. dev.
Avg.
Std. dev.
10
0.3
0.01
0.005
0.005
4.7
11
0.5
0.004
0.014
0.007
28.5
12
0.9
0.02
0.033
0.01
161.4
13
1.5
0.02
0.023
0.01
1578
14
2.3
0.03
0.07
0.05
21 182
15
3.6
0.03
0.08
0.03
—
20
23
0.2
0.22
0.3
—
25
101
0.8
0.6
1.1
—
30
383
33
2.6
0.7
—
40
2380
71
19
25
—
50
12 434
280
107
52
—
60
—
—
228
122
—
70
—
—
1736
261
—
80
—
—
7404
3091
—
90
—
—
11 029
2462
—
100
—
—
64 066
23 836
—Figure 8
Computation times of algorithms OMTS (green), OMTS-A (red), and brute-force (blue).The brute-force algorithm quickly reached the feasibility limit of one day atn=15, the OMTS algorithm could compute schedules for n=40, while OMTS-A was usable even for n=100. The speed differences are clearly shown in Figure 8: the computational time of the brute-force algorithm increases with the number of nodes much faster than in the case of the proposed algorithms. The behavior of algorithms OMTS and OMTS-A are similar, but due to the early cuts, the complexity of OMTS-A is two orders of magnitude lower. Notice the higher variance of OMTS-A, which is due to the fact that the efficiency of early cuts depends largely on the actual topology.Fork=3, used in the tests, the theoretical complexity of the OMTS and OMTS-A algorithms is O(n7), which corresponds well to the measurement results for n≥20.


## 5.2. Performance Comparison

The proposed method is compared to a graph coloring based reference algorithm described in [11]. An example network with 16 nodes was constructed, where 15 nodes form a cycle with symmetrical connections between the neighbors and all nodes in the cycle have symmetrical connection to the central node; see Figure 9(a). The connectivity graph with a Hamiltonian cycle is shown in Figure 9(a) with straight and dashed lines, respectively. From the connectivity graph and the Hamiltonian cycle the constraint graph is constructed for the method described in [11] with constraints C1 and C2, as shown in Figure 9(b).(a) The connectivity graph of the test network (straight lines) and the Hamiltonian cycle (dashed lines). (b) The constraint graph of the network according to the model described in [11].
(a)
(b)Although the method described in [11] contains heuristics to solve the graph coloring problem, in the example of Figure 9 the optimal coloring was found. In Figure 10(a) the constraint graph is colored with 3 colors, which is indeed the minimum, because the graph contains triangles. The sequence of the colors was chosen to be purple → green → blue; that is, purple nodes transmit in time slices t=3m+1, green nodes transmit in time slices t=3m+2 and blue nodes transmit in time slices t=3m   (m∈N).The coloring of the graph according to the method described in [11] (a) and the proposed method (b).
(a)
(b)The optimal schedule found by the proposed OMTS algorithm for the same network is shown in Figure10(b). The optimum was found at k=3 and the graph is colored with 4 colors, with sequence of purple → green → blue → orange.The timing diagrams of the reference and the proposed algorithms are shown in Figure11. The arrows denote the transmission of the information originating from node 1; the dashed vertical lines denote the point, where this information reaches all nodes and is returned back to node 1.The timing diagram of the schedule generated by the reference algorithm (a) and the proposed algorithm (b).
(a)
(b)In Figure11(a) the timing diagram for the reference algorithm is shown. After the information to be disseminated first appears at node 1, the node has to wait for its transmission time slice, which requires 3 time slices in the worst case. From that point the information reaches node 1 again in the 23rd time slice. Thus the propagation of the information requires 3+23=26 time slices.In Figure11(b) the timing diagram for the proposed OMTS algorithm is shown. In worst case, node 1 has to wait 4 time slices to transmit, and the information reaches the last node in the 20th time slice. Thus with this schedule 4+20=24 time slices are required to disseminate the information originating from node 1. The example clearly illustrates the ability of the OMTS algorithm to find the optimal solution in ring topology networks, where messages must be propagated to all other nodes.


## 6. Conclusion

The Minimum Worst Case Turnaround Time problem was defined. A novel algorithm (OMTS) was proposed for ring-topology networks to compute multi-TDMA schedules for the MWCTT problem. The algorithm was proven to find the optimal schedule (with the shortest turnaround time), which, in worst case, provides the fastest means to distribute information from any node to all other nodes and back to the source node in the network. It was proven that the multi-TDMA scheduling can provide at most twofold acceleration with respect to linear scheduling, at a price of increased energy consumption.An accelerated version of the algorithm (OMTS-A) was also proposed, which narrows the search space during runtime using heuristics but still guarantees the optimal solution.In addition to the mathematical analysis of the proposed algorithms, extensive tests were performed to compare the performances of the proposed algorithms and the conventional (brute-force) search method. While the brute-force algorithm can be used for small networks only (less than 15 nodes), the proposed algorithm can solve problems with even 100 nodes in reasonable time.The performance of the designed schedule was also compared to that of another algorithm. In case of the MWCTT problem the proposed solution was able to find better (optimal) schedule.



---

*Source: 837074-2015-01-06.xml*