# An Efficient Algorithm to Find Broadcast Schedule in  Ad Hoc TDMA Networks

Authors: Imtiaz Ahmad; Buthaina Al-Kazemi; A. Shoba Das
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

The broadcast scheduling is of fundamental importance and practical concern for ad hoc network performance measures such as the communication delay and the throughput. The scheduling problem on hand involves determination of a collision-free broadcast schedule with the minimum length TDMA frame and the maximum slot utilization by efficient distribution of slots among stations. The problem is widely known as NP-complete, and diverse heuristic algorithms were reported to solve this problem recently. The intractable nature of the broadcast scheduling problem and its importance in ad hoc TDMA networks necessitates development of more efficient heuristic algorithms. In this paper, we developed a new heuristic approach which employs a tight lower bound derived from the maximal incompatibles and generates a search space from the set of maximal compatibles. The developed algorithm is very efficient and effective in conquering the intractable nature of the broadcast scheduling problem in the sense that it explores complex solution space in smaller CPU time. A comparison with existing techniques for the test examples reported in the literature shows that our algorithm achieves a collision-free broadcast with minimum frame length and the maximum slot utilization in relatively shorter time.


---

## Body

## 1. Introduction

Ad hoc networks have attracted a lot of attention in the recent years
because of their flexible structure and useful applications particularly in
areas such as mobile commerce, combat search, and rescue, to name a few. These
networks apply a packet switching technique over a shared radio channel to
provide flexible high-speed communications between a large numbers of
potentially mobile stations which may be geographically disbursed.
Communication over the shared radio channel is established by broadcasting [1, 2]. Mobile stations are assumed to use unidirectional antennas. The wireless
channel is assumed to be noise-free, and an unsuccessful reception is only due
to collisions. Mobile stations operate in half-duplex mode; that is, a mobile
station can transmit or receive but cannot do both at the same time. Thus, it
is often necessary to use intermediate stations as relays to forward messages
over the network to the intended recipients. Since every station in the network
shares the same channel, it is a fundamental requirement that precautions are
taken when messages are scheduled to be transmitted. That is, stations should
be scheduled in such a way that there is no destructive interference, or
message collision. Collisions in ad hoc networks may occur in two ways: direct
or hidden. Direct collision is a result of two adjacent stations broadcasting
at the same time. Hidden collision occurs when two nonneighboring stations
transmit simultaneously to a station that can receive messages from both
senders [3].Time division multiple access (TDMA) technology is envisioned to be
widely used to provide collision-free packet transmission with quality-of-service
(QoS) support for ad hoc networks [4, 5]. In a TDMA-based ad hoc network, time
is divided into equal-length frames, and each frame is composed of a fixed
number of unit-length transmission slots. The duration of each slot is equal to
one maximum-length packet transmission time plus the maximum propagation time
between two neighboring mobile stations in the network. Once the optimum
transmission pattern for the TDMA frame is decided, the same frame is repeated
over time. It should be ensured that all the stations must be allocated at
least one time slot in every TDMA frame. This is one of the constraints of
scheduling problem and the other being the collision-free transmission. The
broadcast scheduling problem in ad hoc networks involves the determination of a
collision-free broadcast schedule with the minimum length TDMA frame and the
way to distribute the slots among stations for maximum slot utilization. The
frame structure is directly related to the main network performance measures
such as the communication delay and the throughput. Frame length essentially
determines the packet average delay and for a fixed frame length the channel
utilization, which is the number of simultaneous transmissions of
noninterfering stations, determines the throughput in ad hoc network [6, 7].
Therefore, broadcast scheduling problem is of crucial importance and practical
concern to effectively harness the shared radio channel bandwidth in ad hoc
networks.A number of
approaches with varying degree of success have been applied for solving scheduling
problem for delay and throughput in ad hoc networks [1–17]. These
approaches can be classified as graph theoretic [1–3, 13], graph
coloring [6], and probabilistic approaches such as mean field annealing [5],
tabu search [10], genetic algorithms [9, 11, 16], neural networks algorithms
[14, 15, 17], mixed neural-genetic [7], and greedy randomized adaptive search
procedure (GRASP) [12]. A good overview of the techniques applied for the
broadcast scheduling problem can be found in [18]. Most of these algorithms are
based on two phases: phase one minimizes the frame length without considering
the slot usage, and phase two attempts to maximize the slot utilization within
the frame achieved during the first phase. Optimizing the two objectives
separately does not lead to a good solution with respect to both criteria. A better
approach is to consider both of these criteria in an integrated fashion to
solve the broadcast scheduling problem. Probabilistic approaches have considered both of these criteria at the same time and produced better results as compared with other techniques.In this paper,
a new heuristic algorithm based on concepts from the field of finite state
machine synthesis [19, 20] is presented for the broadcast scheduling problem which
determines the minimum frame length with the maximum slot utilization. The stations
which can broadcast without collisions among themselves are grouped as maximal
compatibles. A tight lower bound derived from set of maximal incompatibles
forms the basis for deriving minimum frame length. The proposed algorithm applies
set of rules on the maximal compatibles in order to maximize utilization of
slots. To our knowledge, this approach based on maximal compatibles and maximal
incompatibles for the broadcast scheduling problem has not been reported so
far. A comparison with existing techniques for the test examples reported in
the literature shows that our algorithm explores a complex solution-space in
smaller CPU time.The remaining paper is organized in
the following manner. In Section2, we discuss the broadcast scheduling problem
based on finite state machine approach. Section 3 explains the heuristic scheduling
algorithm proposed in this paper. Results are discussed in Section 4, and
Section 5 concludes the paper.


## 2. Broadcast Scheduling Problem:  Finite State
Machine Approach

In this
section, we discuss the broadcast scheduling problem modeling the network as a
finite state machine. An ad hoc TDMA
network can be modeled by an undirected graphG=(V,E), where the node set V
represents the mobile stations and edge set E represents the set of transmission
links between adjacent mobile stations in the network [8, 9]. Two stations i
and j connected by an undirected edge (i,j)∈E means that both can directly receive packets
transmitted from the other, but both cannot transmit simultaneously in the same
time slot. It represents direct collision and we say stations i and j are
one-hop neighboring stations. If an undirected edge (i,j)∉E but there exists an intermediate node k∈V such that (i,k)∈E and (k,j)∈E, then stations
i and j are referred as two-hop neighboring stations. A hidden collision is a
result of two-hop neighbors transmitting in the same time slot. Two mobile
stations can transmit in the same time slot without mutual interference if they
are located more than two hops apart. Therefore, it is highly desirable for
multiple stations to transmit during the same time slot provided that they do
not cause any collision, either direct or hidden.Some basic
definitions related to finite state machine [20] as applicable to our
scheduling problem on hand are presented here.Finite State Machine
a tripletM=(I,ε,δ) defines a finite state machine M, where I is
a unit value function representing the transmission path between two adjacent
stations, εis the
set of states of the machine, δ:I*ε→εis the
next state function.State Transition Graph
a state transition graph (STG)
describes an ad hoc TDMA network
modeled as an FSM.Compatible and Incompatible
two
statessi and sj are compatible if and only if there is
no collision (direct or hidden) between them. Otherwise, si and sj are incompatible. A set of states is compatible (incompatible) if and only if
each pair of states in the set is compatible (incompatible). A set of compatible states Ci(ICi)
is referred to as a compatible (incompatible), for short.Compatible (Incompatible) Covering
a compatibleCi (incompatible
ICi) covers another compatible Cj (incompatible ICj)
if and only if every state contained in Cj(ICj) is
contained in Ci(ICi).Maximal Compatible (Incompatible)
a compatible (incompatible) becomes a maximal compatible (maximal incompatible)
if it is not covered by any other compatible (incompatible). The set of all maximal
compatibles (incompatibles) is denoted byΩc(Ωi). In the context of the broadcast
scheduling problem, maximal compatibles are set of nodes, which can be assigned
to the same time slot. These sets
of maximal compatibles are maximal cliques in the complement graph of a given
ad hoc network. The maximal incompatibles are the ones which cannot be assigned
to the same time slot.Lower and Upper Bounds
the lower bound is equal to the
maximum degree of the graph modeling the network+1 (direct collision states) and
upper bound is the number of nodes in the network. Optimum frame length is
between the lower and upper bounds. The lower bound represents cardinality of a
set which consists of incompatible state pairs with one state identical in all
the pairs +1 and upper bound is the number of states in STG.Tight Lower Bound
minimum slot length required for collision-free (direct
and hidden) broadcast schedule accommodating all the stations in the network is
the tight lower bound. In the FSM model, tight lower bound is the cardinality
of an incompatible with maximum number of states.Cover
a set that includes all the states of a machine is referred
to as a cover of a machineM. The set of states of the machine, set of maximal
compatibles, and set of incompatibles are all covers of the machine [20]. In
the context of broadcast schedule, a cover refers to the condition that every
node is allowed to transmit at least once in a TDMA cycle.Optimal Cover
a cover is said to be optimalℜm if number
of compatibles in the cover is equal to
the tight lower bound and utility factor μ(si) of every state
is maximum, that is, its frame length is
equal to tight lower bound and slot utilization is maximum.As an example, a 5-node network is shown in Figure1(a) [9], where the
graph has been augmented with two-hop neighbors to represent hidden collision. Nodes 1 and 3 are one-hop
neighbors, while nodes
3 and 5 are two-hop neighbors. A trivial TDMA broadcast schedule solution
satisfying all constraints is shown in Figure 1(c). However, it is not
optimized with respect to both the frame length and the slot utilization.(a)
Graph of a five-node ad hoc network, (b) complement graph of the five-node
network, (c) trivial TDMA broadcast schedule, (d) and (e) optimal TDMA
schedule.
(a)(b)(c)(d)(e)An optimal TDMA broadcast schedule with respect to frame length is shown
in Figure1(d). Figure 1(b) shows the complement graph and the maximal compatibles are {1, 5},{2, 5},{3},{4}. This set of maximal compatibles is a cover of the machine. The
incompatible pairs are {1, 2},{1, 3},{1, 4},{2, 3},{2, 4},{3, 4},{3, 5},{4,
5}. For the graph of Figure 1(a), the maximal incompatible is {1, 2, 3, 4} as
all the states in this are incompatible to each other representing direct and
indirect collisions.
The largest cardinality maximal incompatible will provide the tight lower bound
for the frame length [7]. The optimal solution with the minimum frame length
and the maximum slot utilization are shown in Figure 1(e), where the maximal compatibles {1, 5},{2, 5},{3},{4} are assigned to different slots.


## 3. Scheduling Algorithm

This section discusses
the scheduling algorithm for a 15-node network [12] shown in Figure 2 and modeled
as an FSM (M1). The goal of the algorithm is to find an equivalent
FSM which is a minimized cover of the given FSM. The basic steps of the
algorithm are summarized in Algorithm 1 and individual steps are explained in
detail in subsections. From the STG of M1, all the compatible
(incompatible) pairs which are more than 2 hops away to each other are
generated. If there are no compatible pairs, then no two states can be allotted
to the same slot, hence, all the states of the machine which is the upper bound
are the solution and
every state has to be in a separate slot. The algorithm terminates at this
point. If the algorithm proceeds, solution is obtained at Step (6).Algorithm 1:Outline
of broadcast scheduling algorithm.
Input:FSM
table of networkOutput:  ℜm - Optimum
cover(1)From FSM table of network, generate all compatible
(incompatible) pairs;If (no compatibles){ℜm←
set of
states ε;stop;}else Find maximal compatibles Ωm and incompatibles Ωi;(2)Find the tight
lower bound L and the bound incompatible ICb;(3)Form compatible
groups CG with respect to ICb;(4)Let limit = min(|CG1|,100);j=1;Let s1be the first state in ICb;(5)while (j< limit) {Include in schedule ℜ(j), compatible
Cj∈CG(s1);for (every state si∈ICb where si≠s1)
{(a)Apply selection criteria and include a compatible
Cn∈CG(si) in ℜ(j);(b)for (every state sk∈Cn)
Increment utility factor μ(sk);}for (every state si∣si∈ε,si∉ℜ(j))Include in ℜ(j) largest
cardinality compatible covering the state si;j=j+1;}(6)for (every ℜ(j))compute the performance indices and choose ℜm.Network
with 15 stations.
(a)
FSM table representation (M1) of the network(b)
Undirected graph of the network
(STG)The complexity of our
algorithm is dictated by the number of maximal compatibles generated in Step (1) of the algorithm. Modeling an ad hoc TDMA network as an undirected graph,
where the nodesn represent the
stations and edges m represent the
transmission path between two stations, the maximal compatibles
represent the cliques present in the graph. The complexity for finding cliques
in a graph is O(n∗m∗p(n)) [21], where the polynomial p(n) represents the number of maximal compatibles
in the graph. Step (2) basically sorts
the incompatibles and sorting has a complexity O(p(n)log(p(n))).
As the rest of the steps basically deal with fewer than p(n) compatibles, the complexity of Step (3) to Step (6) is much smaller
than the other two steps. For the graphs, where n∗m>>p(n),
complexity will be O(n∗m∗p(n)).


### 3.1. Generation of Maximal Compatibles (Incompatibles)

The set of
maximal compatibles (incompatibles) is generated from the set of compatibles
(incompatibles) by excluding compatibles (incompatibles) which are covered by
other compatibles (incompatibles). For generating compatible pairs, maximal compatibles
and incompatibles, the part of state minimization algorithm of [20] is used
with the modified definition of the FSM. For FSM of Figure 2, the number of
states n=15 and the set of states, ε={1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. The FSM has 23 maximal
compatibles and 12 maximal incompatibles as listed in Table 1.Table 1
Maximal compatibles and incompatibles ofM1.
Maximal compatibles (Ωm)Maximal incompatibles (Ωi)(12,13,2)(13,7,2)(12,4)(15,2)(13,10,9,8,5,4)(12,11,10,6,5,3)(12,9,1)(10,7)(11,4)(12,13,1)(14,15,12,11,10,6,5)(10,9,6,5,4,3,2)(15,8,3)(9,7)(14,8,3)(15,8,1)(14,15,13,11,10,9,6,5)(12,11,7,6,5,3)(14,8,7)(8,6)(13,3)(10,1)(15,12,11,7,6,5)(10,9,8,5,4,2)(12,8,1)(14,7,4)(11,2)(14,8,1)(13,10,9,6,5,4)(6,5,4,3,2,1)(11,8,1)(15,4)(14,7,2)(11,10,9,6,5,3)(7,6,5,3,1)


### 3.2. Tight Lower Bound

Lower bound
takes into account only direct collision states. A tight lower bound is hence derived
by taking into consideration the hidden collision states. In the FSM model, an incompatible
represents the states which have direct or indirect collision. A maximal
incompatible with the highest cardinality represents all the states which have
either a direct or indirect collision and hence cannot be in the same time
slot. Hence, the tight lower bound for the frame length is imposed by a maximal
incompatible with the highest cardinality [19]. In addition, the optimum
solution should cover all the internal states of the FSM which is the upper
bound.Finding the
highest cardinality maximal incompatible fromΩi, tight lower bound =|{14,15,13,11,10,9,6,5}|=8 and let this incompatible be ICb={14,15,13,11,10,9,6,5}. Every state in ICb has to be covered by a
different maximal compatible in the solution set. If there exist more than one
maximal incompatible with the maximum cardinality, choose one at random.


### 3.3. Compatible Group Formation

The broadcast
schedule is built by including compatibles which cover every state inICb.
As several compatibles cover a state in ICb, a weight factor is
associated with maximal compatibles to aid in selecting a compatible. Compatibles
with smaller weights are more essential than a bigger weight compatible and
they get a preference if there is a tie in selection in the solution schedule.The compatible
group formation is done in three steps:(1)
group the compatibles which cover one state of ICb;(2)
find the weight of maximal compatibles;(3)
sort the compatibles in CG according to their weights in ascending
order.Step 1.
for every statesi∈ICb, form a cover group such that it
consists of all maximal compatibles which covers si, that is, CG(si)={Cj∣si∈ICb,si∈Cj}Step 2.
for every statesi∈ε, associate a weight ω(si) which is
the number of maximal compatibles covering the state si. Adding ω(si)
of every state si∈Cj, find the weight of maximal
compatible, W(Cj). The compatible Cj = (14, 7, 4) has
three states 14, 7, and 4. Find the number of maximal compatibles covering
every state in this compatible from Table 1, ω(14) = 5, ω(7) = 6, and ω(4) = 4.  Add the weight of individual states in Cj,
and find weight W(Cj), which is 15.Step 3.
sort the compatibles in CG according to their weightsW(Cj)
in ascending order.
In Table2,
compatible groups for every state in ICb=(14,15,13,11,10,9,6,5) formed
using the above three listed steps are shown. The maximal compatibles are
grouped to cover the respective states in ICb.Table 2
Compatible groups ofM1.
Incompatible statesi∈ICbCompatible groupsCG(si)Weight of compatibles in order{W(Cj)}14(14,7,4) (14,8,3)
(14,7,2) (14,8,7) (14,8,1)15, 16, 16,
20, 2015(15,4) (15,2)
(15,8,3) (15,8,1)8, 9, 15,
1913(13,3) (12,13,2)
(13,7,2) (12,13,1)7, 14, 15,
1611(11,4) (11,2)
(11,8,1)7, 8, 1810(10,7) (10,1)8, 99(9,7) (12,9,1)8, 146(8,6)95(5)1


### 3.4. Iteration Limit

Multiple
feasible schedules are possible for the broadcast schedule problem. The
performance parameters aid in selecting the optimum schedule. The states inICb,
weight of compatibles, and utility factor of states in a compatible guide the
selection of compatibles to be included in the solution. Among the several
compatibles in CG(si) covering the first state si∈ICb, one of the compatibles has to be selected as a
starting point. The states in this compatible decide the formation of rest of
the schedule. Hence, the compatibles CG(si) covering the first state
si are used in order as a starting point and several schedules are
derived. An upper limit of 100 is set for the number of schedules generated. The
number of schedules for M1 is 5 as there are five compatibles in
CG(14), where si = 14 is the first state in ICb. One of
the compatibles in the first group is included by default in every schedule and
the selection criteria are applied only for subsequent CGs. For M1,
in the first schedule ℜ(1), the first
compatible in CG(14), namely, (14,7,4) is included. At this stage, ℜ(1) =  {(14,7,4)}.


### 3.5. Compatible Selection Criteria

The feasible
schedule should basically cover all the states of the machine without any
collision and with the minimum frame
length and the maximum slot utilization. A compatibleCj∈CG(si) is included in a feasible
schedule ℜ(k) based on two criteria
applied in succession: (i) uncoveredState factor, that is, number of
uncovered states in Cj, and (ii) cardinality of the compatible Cj.Initially, for
everyCj∈CG(si) compute uncoveredstate factor γ(Cj)=|{si∣si∈Cj⋀si∉ℜ(k)}|. Choose the
compatible with maximum γ(Cj). If there is a tie, then apply the
second criterion, that
is, choose the compatible with higher cardinality as this represents a
compatible which if included will improve the channel utilization. If there is
still a tie, select the first compatible in the list.InM1,ℜ(1) = {(14, 7, 4)}
and the uncovered states are {1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 13, 15}. In the
group of next state 15 in ICb, that is, CG(15),γ(Cj) of
the compatibles {(15,4) (15,2) (15,8,3) (15,8,1)}, respectively, are (1, 2, 3,
3). Out of these, the compatibles {(15,8,3) (15,8,1)} have a tie as none of the
states in them are covered by ℜ(1) and both of
them have γ(Cj) = 3, in this compatible group. Hence, the first one
in the list is included. ℜ(1) = {(14,7,4) (15,8,3)}.
Proceeding to next three states, ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7)}. At this point, the states that are not covered by ℜ(1) are (5,6,9).
Taking the group of next state 9, CG(9) = {(9,7) (12,9,1)}. Both cover only one
uncovered state 9, and the tie is broken by choosing the second one with
greater cardinality as there are two covered states, thereby improving the
channel utilization. Including the next two compatibles in order to cover all
the states in the network, the schedule ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)}.LetN  be the number of nodes and let L be
the number of slots in a TDMA schedule. The feasible transmission schedule will
be an N*L binary matrix S=(sij) such that (1)sij={1,if time slotiin a frame is assigned to a nodej,0,otherwise. In M1,
number of nodes N=15 and L=8, and all the schedules generated are shown in
Table 3. Even though 5 schedules were generated, one of them did not satisfy
the constraint that all states should be covered with in tight lower bound and
the solution slot length has to be increased above the tight upper bound by 1
to accommodate a compatible covering the uncovered state. Hence, this solution
had a slot length of 9 and this schedule is marked with (*) in Table 3.Table 3
Feasible schedules ofM1.
Schedule indexjScheduleℜ(j)1(14,7,4)
(15,8,3) (12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)2(14,8,3) (15,8,1)
(12,13,2) (11,4) (10,7) (12,9,1) (8,6) (5)3(14,7,2) (15,8,3)
(12,13,1) (11,4) (10,7) (12,9,1) (8,6) (5)4(14,8,1) (15,8,3)
(12,13,2) (11,4) (10,7) (12,9,1) (8,6) (5)5*(14,8,7)
(15,8,3) (12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5) (11,4)


### 3.6. Optimum Schedule Selection

The following
performance indices are computed for every feasible scheduleℜ(j).(i)
Average time delay for each node to broadcastτ [14].(ii)
Throughputσ.
Average time delay(2)τ=LN∑i=1N(1∑j=1Lsij).
Throughput(3)σ=∑i=1N∑j=1Lsij.The
performance indices of the above schedules forM1 are shown in Table 4 along with the frame length.Table 4
Performance
characteristics ofM1.
Schedule indexjAverage time delayτThroughputσFrame length(L)16.820827.119836.919847.11985*6.45229The schedule within
the tight lower bound which yields the maximum throughput and the minimum
average time delay is selected as the optimum scheduleℜm. The
optimum schedule for M1 is ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)}.


## 3.1. Generation of Maximal Compatibles (Incompatibles)

The set of
maximal compatibles (incompatibles) is generated from the set of compatibles
(incompatibles) by excluding compatibles (incompatibles) which are covered by
other compatibles (incompatibles). For generating compatible pairs, maximal compatibles
and incompatibles, the part of state minimization algorithm of [20] is used
with the modified definition of the FSM. For FSM of Figure 2, the number of
states n=15 and the set of states, ε={1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. The FSM has 23 maximal
compatibles and 12 maximal incompatibles as listed in Table 1.Table 1
Maximal compatibles and incompatibles ofM1.
Maximal compatibles (Ωm)Maximal incompatibles (Ωi)(12,13,2)(13,7,2)(12,4)(15,2)(13,10,9,8,5,4)(12,11,10,6,5,3)(12,9,1)(10,7)(11,4)(12,13,1)(14,15,12,11,10,6,5)(10,9,6,5,4,3,2)(15,8,3)(9,7)(14,8,3)(15,8,1)(14,15,13,11,10,9,6,5)(12,11,7,6,5,3)(14,8,7)(8,6)(13,3)(10,1)(15,12,11,7,6,5)(10,9,8,5,4,2)(12,8,1)(14,7,4)(11,2)(14,8,1)(13,10,9,6,5,4)(6,5,4,3,2,1)(11,8,1)(15,4)(14,7,2)(11,10,9,6,5,3)(7,6,5,3,1)


## 3.2. Tight Lower Bound

Lower bound
takes into account only direct collision states. A tight lower bound is hence derived
by taking into consideration the hidden collision states. In the FSM model, an incompatible
represents the states which have direct or indirect collision. A maximal
incompatible with the highest cardinality represents all the states which have
either a direct or indirect collision and hence cannot be in the same time
slot. Hence, the tight lower bound for the frame length is imposed by a maximal
incompatible with the highest cardinality [19]. In addition, the optimum
solution should cover all the internal states of the FSM which is the upper
bound.Finding the
highest cardinality maximal incompatible fromΩi, tight lower bound =|{14,15,13,11,10,9,6,5}|=8 and let this incompatible be ICb={14,15,13,11,10,9,6,5}. Every state in ICb has to be covered by a
different maximal compatible in the solution set. If there exist more than one
maximal incompatible with the maximum cardinality, choose one at random.


## 3.3. Compatible Group Formation

The broadcast
schedule is built by including compatibles which cover every state inICb.
As several compatibles cover a state in ICb, a weight factor is
associated with maximal compatibles to aid in selecting a compatible. Compatibles
with smaller weights are more essential than a bigger weight compatible and
they get a preference if there is a tie in selection in the solution schedule.The compatible
group formation is done in three steps:(1)
group the compatibles which cover one state of ICb;(2)
find the weight of maximal compatibles;(3)
sort the compatibles in CG according to their weights in ascending
order.Step 1.
for every statesi∈ICb, form a cover group such that it
consists of all maximal compatibles which covers si, that is, CG(si)={Cj∣si∈ICb,si∈Cj}Step 2.
for every statesi∈ε, associate a weight ω(si) which is
the number of maximal compatibles covering the state si. Adding ω(si)
of every state si∈Cj, find the weight of maximal
compatible, W(Cj). The compatible Cj = (14, 7, 4) has
three states 14, 7, and 4. Find the number of maximal compatibles covering
every state in this compatible from Table 1, ω(14) = 5, ω(7) = 6, and ω(4) = 4.  Add the weight of individual states in Cj,
and find weight W(Cj), which is 15.Step 3.
sort the compatibles in CG according to their weightsW(Cj)
in ascending order.
In Table2,
compatible groups for every state in ICb=(14,15,13,11,10,9,6,5) formed
using the above three listed steps are shown. The maximal compatibles are
grouped to cover the respective states in ICb.Table 2
Compatible groups ofM1.
Incompatible statesi∈ICbCompatible groupsCG(si)Weight of compatibles in order{W(Cj)}14(14,7,4) (14,8,3)
(14,7,2) (14,8,7) (14,8,1)15, 16, 16,
20, 2015(15,4) (15,2)
(15,8,3) (15,8,1)8, 9, 15,
1913(13,3) (12,13,2)
(13,7,2) (12,13,1)7, 14, 15,
1611(11,4) (11,2)
(11,8,1)7, 8, 1810(10,7) (10,1)8, 99(9,7) (12,9,1)8, 146(8,6)95(5)1


## 3.4. Iteration Limit

Multiple
feasible schedules are possible for the broadcast schedule problem. The
performance parameters aid in selecting the optimum schedule. The states inICb,
weight of compatibles, and utility factor of states in a compatible guide the
selection of compatibles to be included in the solution. Among the several
compatibles in CG(si) covering the first state si∈ICb, one of the compatibles has to be selected as a
starting point. The states in this compatible decide the formation of rest of
the schedule. Hence, the compatibles CG(si) covering the first state
si are used in order as a starting point and several schedules are
derived. An upper limit of 100 is set for the number of schedules generated. The
number of schedules for M1 is 5 as there are five compatibles in
CG(14), where si = 14 is the first state in ICb. One of
the compatibles in the first group is included by default in every schedule and
the selection criteria are applied only for subsequent CGs. For M1,
in the first schedule ℜ(1), the first
compatible in CG(14), namely, (14,7,4) is included. At this stage, ℜ(1) =  {(14,7,4)}.


## 3.5. Compatible Selection Criteria

The feasible
schedule should basically cover all the states of the machine without any
collision and with the minimum frame
length and the maximum slot utilization. A compatibleCj∈CG(si) is included in a feasible
schedule ℜ(k) based on two criteria
applied in succession: (i) uncoveredState factor, that is, number of
uncovered states in Cj, and (ii) cardinality of the compatible Cj.Initially, for
everyCj∈CG(si) compute uncoveredstate factor γ(Cj)=|{si∣si∈Cj⋀si∉ℜ(k)}|. Choose the
compatible with maximum γ(Cj). If there is a tie, then apply the
second criterion, that
is, choose the compatible with higher cardinality as this represents a
compatible which if included will improve the channel utilization. If there is
still a tie, select the first compatible in the list.InM1,ℜ(1) = {(14, 7, 4)}
and the uncovered states are {1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 13, 15}. In the
group of next state 15 in ICb, that is, CG(15),γ(Cj) of
the compatibles {(15,4) (15,2) (15,8,3) (15,8,1)}, respectively, are (1, 2, 3,
3). Out of these, the compatibles {(15,8,3) (15,8,1)} have a tie as none of the
states in them are covered by ℜ(1) and both of
them have γ(Cj) = 3, in this compatible group. Hence, the first one
in the list is included. ℜ(1) = {(14,7,4) (15,8,3)}.
Proceeding to next three states, ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7)}. At this point, the states that are not covered by ℜ(1) are (5,6,9).
Taking the group of next state 9, CG(9) = {(9,7) (12,9,1)}. Both cover only one
uncovered state 9, and the tie is broken by choosing the second one with
greater cardinality as there are two covered states, thereby improving the
channel utilization. Including the next two compatibles in order to cover all
the states in the network, the schedule ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)}.LetN  be the number of nodes and let L be
the number of slots in a TDMA schedule. The feasible transmission schedule will
be an N*L binary matrix S=(sij) such that (1)sij={1,if time slotiin a frame is assigned to a nodej,0,otherwise. In M1,
number of nodes N=15 and L=8, and all the schedules generated are shown in
Table 3. Even though 5 schedules were generated, one of them did not satisfy
the constraint that all states should be covered with in tight lower bound and
the solution slot length has to be increased above the tight upper bound by 1
to accommodate a compatible covering the uncovered state. Hence, this solution
had a slot length of 9 and this schedule is marked with (*) in Table 3.Table 3
Feasible schedules ofM1.
Schedule indexjScheduleℜ(j)1(14,7,4)
(15,8,3) (12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)2(14,8,3) (15,8,1)
(12,13,2) (11,4) (10,7) (12,9,1) (8,6) (5)3(14,7,2) (15,8,3)
(12,13,1) (11,4) (10,7) (12,9,1) (8,6) (5)4(14,8,1) (15,8,3)
(12,13,2) (11,4) (10,7) (12,9,1) (8,6) (5)5*(14,8,7)
(15,8,3) (12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5) (11,4)


## 3.6. Optimum Schedule Selection

The following
performance indices are computed for every feasible scheduleℜ(j).(i)
Average time delay for each node to broadcastτ [14].(ii)
Throughputσ.
Average time delay(2)τ=LN∑i=1N(1∑j=1Lsij).
Throughput(3)σ=∑i=1N∑j=1Lsij.The
performance indices of the above schedules forM1 are shown in Table 4 along with the frame length.Table 4
Performance
characteristics ofM1.
Schedule indexjAverage time delayτThroughputσFrame length(L)16.820827.119836.919847.11985*6.45229The schedule within
the tight lower bound which yields the maximum throughput and the minimum
average time delay is selected as the optimum scheduleℜm. The
optimum schedule for M1 is ℜ(1) = {(14,7,4) (15,8,3)
(12,13,2) (11,8,1) (10,7) (12,9,1) (8,6) (5)}.


## 4. Experimental Results

The experiments were conducted on a Pentium 4/1.7 GHz
PC and tested on network examples available in the literature. The specifications
of the three network cases, namely, 15, 30, and 40 station networks introduced
by Wang and Ansari [5] which have become the benchmark test cases for broadcast
scheduling problem and the other networks found in literature are shown in
Table 5. The broadcast networks are modeled as FSMs modifying the standard
definitions to suit the network parameters. The maximal compatibles and
incompatibles were generated by modifying an algorithm for state minimization
of FSMs [20].Table 5
Specifications of test cases.
Problem no.No. of nodesNo. of edgesMaximum degree1 [2]7672 [12]152973 [2]162244 [12]307085 [12]40667The optimal schedules for the test cases 2 to 5 are
shown in Figures3, 4, 5, and 6, respectively.
The rows represent the slots in a TDMA frame and columns represent the nodes in
the network. Out of the four feasible schedules in 15 station networks, only
one is the optimal solution. Two feasible schedules exist for problem no. 3 and the optimum solution
is the one shown in Figure 4.Figure 3
Optimal
schedule of 15-station network.Figure 4
Optimal
schedule of 16-station network.Optimal
schedule of 30-station network.
(a)(b)Figure 6
Optimal
schedule of 40-station network.In 30-node network, there are two feasible schedules, which are shown in Figures5(a) and 5(b), {(18,23,5,2) (17,24,15,13,29,9) (22,28,8) (20,6,7) (14,26) (12,23,27,2)
(16,21,3,2) (30,19,1) (13,4,25) (30,11,10)}, and {(18,5,26) (17,24,15,13,29,9) (22,28,8)
(20,6,7) (14,23,2) (12,23,27,2) (16,21,3,2) (30,19,1) (13,4,25) (30,11,10)}.
Average time delay and throughput are identical in both the schedules and hence
both are optimum schedules. There are 14 feasible schedules in the case of 40-node
network but only one of them is an optimum which is shown in Figure 6.We report two performance parameters, namely, average time
delay (τ) and throughput (σ), and these are listed in Table 6 for
the test cases. The average time delay and number of slots in a TDMA frame of
our algorithm are compared
with respective values of [2], [5], [6], [7], and [14] which is presented in
Table 7. We achieved the average delay close to BSC-NCNN [14] and much better
than all the other cases listed in this table and maximum slot utilization in
negligible time.Table 6
Performance measurements.
Problem no.Network
nodes(N)Average
time delay
(τ)Throughput
(σ)17372156.8203164.8174309.235540664Table 7
Comparison of average time delay and number of slots.
NodesOur
algorithmBSC-NCNN
[14]HNN-GA
[7]SVC
[6]MFA
[5]GNN
[2](N)(L)(τ)(L)(τ)(L)(τ)(L)(τ)(L)(τ)(L)(τ)1586.886.887.087.287.287.130109.2109.2109.310101210.5109.5408685.886.386.7696.986.2For the problem no. 2, our algorithm has an average delay of 4.8 with a
throughput of 17 and the solution in [2] has a delay of 5 with a throughput of
16. The comparison tables show that our algorithm could generate optimum
schedule for the benchmark cases with minimum average delay and maximum
utilization compared to almost all other cases shown in the table.


## 5. Conclusion

A heuristic algorithm for finding an optimal feasible
broadcast schedule for ad hoc TDMA networks is presented. By modeling the
network as an FSM, the concept of maximal compatibles and incompatibles is used
to find a schedule that will minimize the frame length and maximize the slot utilization in an
integrated fashion. To our knowledge, this approach of modeling
the network as an FSM has
not been reported so far. Suboptimal schedules with an increased time slot per
frame also were generated, which gives more throughputs. The algorithm was
efficient for all the benchmark cases and generated schedules within the tight
lower bound in negligible time. Future work will take into account the QoS of
the nodes (i.e., bandwidth or delay requirements) when determining the
broadcast schedule.



---

*Source: 712126-2009-02-25.xml*