Wireless Se
n
doi:10.4236/
w
Copyright ©
2
An
A
T
o
Depa
Abstract
Topology-t
r
throughput
modify the
the cover-f
r
Second, w
e
squashed o
u
all of its re
d
put can be
transparent
mission del
Keywords:
1. Introdu
Recently, m
a
monitoring
a
on Mobile
A
ties have gr
e
sion throug
h
guaranteed
Q
cations.
Since M
A
and is the ba
guaranteed
Q
pensible [1].
MAC pro
t
One is the c
o
known Carr
i
ance (CSM
A
its possibili
t
wireless coll
other one is
a time fram
e
*This research
i
dation of Chin
a
Basic Disciplin
e
leum(Beijing)
u
n
sor Network
,
w
sn.2010.2100
9
2
010 SciRes.
A
lgorit
h
o
polog
y
rtment of C o
m
R
e
r
ansparent
M
guarantee,
a
cove
r
-free s
r
ee se
t
is pr
o
e
prove that
u
t. Our algo
r
d
undant slot
s
guaranteed
i
node sched
u
ay can be g
o
MAC Sche
d
ction
a
ny multime
d
a
nd voice rec
o
A
d hoc Netw
o
e
at relationshi
p
h
put and tran
s
Q
oS on MA
N
A
C layer is di
r
sis of all othe
Q
oS, guarante
t
ocols in wir
e
o
ntention-
b
as
e
i
er Sense M
u
A
/CA) protoc
o
t
y of infinite
isions, it can
n
the scheduli
n
e
is divided in
t
i
s supported in
p
a
(NSFC) under
e
s Research Fo
u
u
nder grant No.(J
C
,
2010, 2, 801
9
6 Published O
n
h
m fo
r
y
-Tran
s
m
puter Scienc
e
ceived June
5
M
AC sched
u
a
cove
r
-free
et so that b
e
o
posed and
f
any subset
o
r
ithm choos
e
s
, and then d
e
i
f the squas
h
u
ling strateg
o
tten by just
u
d
uling, Qos,
C
d
ia applicatio
n
o
rding, are s
u
o
rks (MANE
T
p
with the gu
a
s
mission del
a
N
ET is requir
e
r
ectly above
t
r protocols, f
o
ed QoS on
M
e
less network
e
d MAC proto
u
ltiple Access
o
l as its repr
e
transmission
n
o
t
p
rovide Q
o
n
g-
b
ased MA
C
t
o multiple ti
m
p
art by National
N
grant No.(6100
u
ndation of Chi
n
C
X
K
-2010-01).
-806
n
line October 2
r
Impr
o
s
paren
t
C
e and Techno
xu
5
, 2010; revis
e
u
ling strateg
i
set is outpu
t
e
tter through
p
f
ound to ha
v
o
f a cove
r
-f
r
e
s the subset
e
signates it
a
h
ed subset i
s
y, both the
i
u
sing our al
g
C
ombinator
i
n
s, such as
v
u
ggested to d
e
T
). Their feas
i
a
ranteed tran
s
a
y. In other
w
e
d by these a
p
t
he ph
y
sical
l
o
r a MANET
M
AC layer is i
n
are of two t
y
col, with th e
w
/Collision A
v
e
sentative. D
u
delay cause
d
o
S guarantee.
C
pro
t
ocol,
w
m
e slots, and
N
atural Science
3307, 60803159
n
a University of
010 (http://ww
w
o
ving T
t
MA
C
C
haonong
X
logy, China
U
u
chaonong@
c
e
d July 12, 2
0
i
es nowaday
t
as scheduli
p
ut can be g
u
v
e negative i
n
r
ee set is sti
which has t
h
a
s the netwo
r
s
adopted as
i
ncreased m
i
g
orith
m
as a
n
i
al Design, S
v
ideo
e
ploy
i
bili-
s
mis-
w
ord,
p
pli-
l
ayer
with
n
dis-
y
pes.
w
ell-
v
oid-
u
e to
d
by
The
w
here
each
no
d
slo
t
wh
o
mis
be
e
S
gor
i
de
n
the
les
s
eit
h
no
d
dep
of
c
mo
b
p
ar
e
of
n
app
T
p
ro
t
p
er
,
N
p
ro
t
clu
d
tho
g
Foun-
), an
d
Pet
r
o-
w
.SciRP.org/j
o
hroug
h
C
Sche
d
X
u
U
niversity of
P
c
up.edu.cn
0
10; accepted
s are all ba
s
ng strategy
o
u
aranteed.
A
n
fluence on
ll a cove
r
-f
r
h
e maximal
r
k schedulin
g
network sc
h
i
nimal throu
n
extra acce
s
uperimpose
d
d
e is assigned
t
s [2]. We ta
k
o
se topology
sions into di
f
e
liminated ef
f
S
cheduling-
b
a
i
zed into two
n
t and the to
p
topolog
y
-dep
e
s
collisions, a
h
er in every n
o
d
e in centraliz
e
endent MAC
c
onstantly ch
a
b
ility of node
e
nt MAC sc
h
n
etwork topo
l
licatio ns depl
T
he scheduled
t
ocols can be
,
we focus on
N
owadays, al
l
t
ocols are all
d
ing the mult
i
g
onal array [
8
o
urnal/wsn/).
h
put G
u
d
uling
S
P
etroleum-Be
ij
August 17, 2
0
s
ed on com
b
o
f network.
A
t the first s
t
the minima
l
r
ee set after
number of
r
g
strategy.
T
h
eduling str
a
ghput and d
s
sory.
d
Code, Cov
e
the transmitti
n
k
e Figure 1
f
is known, b
y
f
ferent time s
l
f
iciently.
sed MAC pr
o
subcategorie
s
p
ology-transp
a
e
ndent MAC
p
uniform topo
l
o
de in distrib
u
e
d manne
r
[3
]
protocols are
a
nged topolo
g
[4]. On the c
o
h
eduling prot
o
l
ogy and ma
y
oyed on MA
N
object of the
either wirele
node sched ul
i
l
topology-tr
a
b
ased on co
m
i
nomial theo
r
8
], latin squar
e
u
arant
S
trateg
y
ij
ing, Beijing,
0
10
b
inatorial de
In this pape
r
t
ep,
t
he redu
n
l
guarantee
d
its redunda
n
r
edundant sl
o
T
herefore, be
t
a
tegy. For a
n
ecreased m
a
er
-Free Set
n
g right at so
m
f
o
r
example,
f
y
arranging c
o
l
ots, wireless
o
tocols can b
e
s
, i.e., the to
p
a
rent MAC
p
p
rotocols, to
m
l
ogy graph h
a
u
ted manne
r
,
]
. Obviously,
unfit for M
A
g
y which is
c
o
ntrary, the t
o
o
cols are full
y
y
be
p
romisi
n
N
ET.
topolog
y
-tra
n
ss link or no
d
i
ng.
a
nsparent no
d
m
binatorial d
e
r
y in Galois
fi
e
s [9], balanc
e
WS
N
ee of
y
*
China
sign. To ge
t
r
, we aim t
o
n
dant slot o
f
d
throughput
.
n
t slots wer
e
o
ts, squashe
s
t
ter through
-
n
y topology
-
a
ximal trans
-
m
e given tim
e
f
or a networ
k
o
lliding trans
-
collision ca
n
e
further ca
t
e
-
p
olog
y
-depen
-
p
rotocols. Fo
r
m
inimize wire
-
a
s to be set u
p
or in the sin
k
t
he topology
-
A
NET becaus
e
c
aused by th
e
o
polog
y
-trans
-
y
independen
t
n
g choices fo
r
n
sparent MA
C
d
e. In this pa
-
d
e schedulin
g
e
signs [5], in
-
fi
eld [6,7], or
-
e
d incomplet
e
N
t
o
f
.
e
s
-
-
-
e
k
-
n
-
-
r
-
p
k
-
e
e
-
t
r
C
-
g
-
-
e

802 C. N. XU
block [10,11] and superimposed code[12-14]. The aim of
them is same, that is, to give birth to a cover-free set as
MAC scheduling codes, which is the key to QoS guaran-
tee. Of course, the sets generated by different strategies
are distinct even if they are feed with same parameters.
Due to the existence of co mbinatorial designs, the car-
dinal of the cover-free set is no less than the node num-
ber of network [5 ]. Therefore, the prob lem of how to se-
lect an appropriate subset comes into being, for every no-
de has to be uniquely associated with one element of the
cover-free set. In other word, if the node number of a
network is N, and the cardinal of the set is M, then there
are
M
N



optional subsets which can be assigned as the
MAC schedu ling tr agedy o f networ k. Obv iously, rando m
selection is not a considerate policy, although it is ado-
pted by all of the topology-transparent MAC scheduling
protocols nowadays. Which subset can provide the best
throughput gu aran tee? Fur ther, can the selected subset be
optimized further? This paper tries to answer the ques-
tions.
We propose the definition of the redundant slot of the
cover-free set, and pro ve that the redundant slot has neg-
ative influence on thr oughpu t guaran tee. Furth er, we pro-
ve that any subset of a cover-free set is still a cover-free
set after any of its redundant slots is squashed out. There-
fore, the more minimal throughput and the less maximal
delay can be guaranteed. Our algorithm therefore picks
the subset which has the maximal number of redundant
slots, squashes all redundant slots of the subset, and then
designates it as node scheduling strategy of network.
Therefore, for any topology-transparent node scheduling
strategy, both the increased minimal throughput and de-
creased maximal transmission delay can be gotten by just
using our algorithm as an extra accessory.
2. Network Model
Wireless network is modeled by a directed graph G = (V,
E), where V is the set of nodes and E is the set of directed
links. If node w is within the transmission range of node
u, then a directed edge connecting these two nodes is
denoted by (u, w)E, with u being a neighbor of w. Th e
degree of a node w, i.e.,()|{|(,) ,,}|DwuuwEuw V


is defined as the number of its neighbors. We assume
that the maximum nodal degree Dmax, i.e.,max( )
wVDw ,
remains constant when network operate s. O f course, Dmax
> 0 is necessary for keeping connectivity.
In this paper, we assume that the transmission channel
is error-free and a reception failure is caused only by
packet collisions. A packet transmitted from a neighbor
of a node, is successfully received by the node only if no
packet is transmitted from other neighbor nodes simul-
taneously. All nodes are homogeneous. We also assume
that the transceiver at each node is half-duplex. As a re-
sult, a node cannot transmit and receive concurrently.
Time is assumed to be synchronized over the network.
Furthermore, time is slotted and slots are grouped into
time frame. For example, a time frame consists of four
time slots in Figure 1. In other word, a frame F = {S1,
S2, …, Sb} consists of b consecutive slots. A slot assign-
ment is given by a set ()Sw F for every node w,
where S(w) consists of time slots in which node w has
the transmitting right in a frame.
3. Redundant Slot and QoS Guarantee
3.1. Redundant Slot
Definition 1. Assume [k] = {0, 1, …, k-1}, a set A = {A0,
A1, …, AM-1} of subsets of the [T] is a (s, M, T) cover-free
set if for any proper subset I of [M] su ch tha t |I| = s (|I| is
the cardinal of set I), and any integer []
j
MI
, we
have {} {}
ji
AA

. s is called the intensity of the co-
ver-free set.
Cover-free set is equivalent with the d-disjunct matrix
[15] and the superimposed code.
A (s, M, T) cover-free set A can be represented by a T
× M matrix A where
101,0 1
0
j
ij j
if iA
AiTjM
if iA




 



The matrix is referred as the scheduling matrix. For
convenience, the jth column vector and the ith row vec-
tor of the scheduling matrix A are denoted as A*j and
Ai* respectively. Besides, for a T × M scheduling matrix,
ATj is the MSB (Most Significant Bit) of A*j and A0j is the
LSB (Least Significant Bit) of A*j.
Definition 2. For two vectors X = (x1, x2, …, xm)T
and Y = (y1, y2, …, ym)T, the sum of X and Y is
112 2
(, ,...,)
T
mm
XYx yxyxy . If X + Y = X, then
Y is covered by X.
Obviously, for the scheduling matrix of a (s, M, T)
cover-free set, any column vector is not covered by any
other s column vectors.
Lemma 1. Any L (
s
LM

) elements in a (s, M, T)
Figure 1. An example of MAC scheduling code.

C. N. XU 803
cover-free set form a (s, L, T) cove r- free set.
Proof: For the scheduling matrix of a (s, M, T) cov-
er-free set, any one column vector will not be covered by
any other s column vectors. So it will not be covered by
any other L column vectors since L < s. Therefore, it is a
(s, L, T) cover-free family.
Definition 3. Assume the scheduling matrix of a (s, M,
T) cover-free set is denoted as A, for some integer i
(01iT ) and an y integer j(0 1)jM , if Aij = 0
or Aij = 1, then i is a redundant slot of A.
Theorem 1. Assume the scheduling matrix of a (s, M,
T) cover-free set is denoted as A, a (1)TM matrix
which is generated by removing (deleting, or squashing)
redundant slot of A is a (s, M, T-1) cover-free set.
Proof: For any s + 1 column vectors of A, without loss
of generality, assume them to be A*0, A*1, …, A*s. Ob-
viously, A*s is not covered by A*0 + A*1 + … + A*(s-1) . In
other word, there exist at least one integer k
(01kT
), which satisfies
[1]
(1)({}{0})
ks ki
is
A
Atrue
 
 . Therefore, k is not a
redundant slot of A.
Assume a (1)TM matrix B is generated by
squashing any one redundant slot of A, and A*0, A*1, …,
A*s are turned into B*0, B*1, …, B
*s correspondingly.
Since k is not a redundant slot of A, Ak* is still kept in B.
Thus, B*s is not covered by B*0 + B*1 + … + B*(s-1). Con-
sidering the generality of choosing A*0, A*1, …, and A*s,
the set of all column vectors in B is a (s, M, T-1) cov-
er-free set.
Redundant slot results in less throughput guarantee.
Assume the scheduling matrix of a (s, M, T) cover-free
set to be A and i is one of its redundant slot. If
01
{}{0}
ij
jM A  
, none of nodes will transmit at slot i.
On the other hand, if 01
{}{1}
ij
jM A  
, all nodes will
transmit at slot i and no any packets can be received cor-
rectly due to the half-duplex transceiver. In a word, the
throughput of redundant slots is wasted in both cases.
3.2. Redundant Slot and QoS Guarantee
Definition 4. The minimal guaranteed throughput Gmin is
defined as the ratio of the number of guaranteed suc-
cessful transmissions in one frame to frame length.
Definition 5. The transmission delay under the worst
traffic condition is called the maximal transmission de-
lay, and it is defined as the ratio of frame length to the
minimal number of successful transmission slots in one
frame.
Theorem 2. For a (s, M, T) cover-free set A and a (s,
M, T-1) cover-free set A’ which is generated by squash-
ing one redundant slot of A, if the minimal guaranteed
throughput and the maximal transmission delay are Gmin
and max
DT , and ' min
G and 'ma x
D
T respectively when A
and A’ are adopted respectively as node scheduling
codes, then'
min min
//(1)GG TT

, and
'
max max
/(1)/DT DTTT .
Proof: For any node, assume there are at least k exclu-
sive transmission slots can be guaranteed if A is adop-
ted as the MAC scheduling codes of network, based
on the definition of the minimal guaranteed throughput,
min k
GT

. Similarly, if A’ is adopted, '
min 1
k
GT 

.
Therefore, '
min min
//(1)GG TT

.
Since the maximal transmission delay is the reciprocal
of the minimal guaranteed throughput,
'
max max
/(1)/DT DTTT .
4. Algorithm and Performance Analysis
4.1. Algorithm
For selecting N scheduling codes from M candidates, there
are
M
N



optional subsets in total. Based on Theorem 2,
QoS guarantee can be enhanced if a redundant slot is
squashed. So our algo rithm chooses the su bset which has
the maximal number of redundant slots, squashes all re-
dundant slots of the subset, and then designates it as the
node scheduling strategy.
4.2. Performance Analysis
Theorem 3. Assume the scheduling matrix of a (s, M, T)
cover-free set to be ATM, if its row vectors have equal
weight w, then the algorithm can squash at least i redun-
dant slots if the node number N satisfies
(1)
M
iwNMiw

  (01
M
iw  , and i is
an integer).
Proof: We prove it using mathematical induction.
1) If
M
wNM

, i.e., i = 0, Theorem 3 is ob-
viously correct.
2) Assume when (1)
M
kwNMkw

 , at
least k redundant slots can be squashed.
3) If (2) (1)
M
kwNMkw

 , since
(1)
M
kwNwMkw

, for N + w nodes,
at least k redundant slots can be squashed from ATM
based on the assumption 2). If the scheduling matrix af-
ter the k redundant slots are squashed from ATM is notated
()
()( )
k
TkNw
A . Since the row weight of ATM is w, there are at
most w column vectors whose MSBs are 1 in()
()( )
k
TkNw
A .
In other word, there are at least N column vectors whose

804 C. N. XU
MSBs are 0 in()
()( )
k
TkNw
A
.
If we select any N column vectors whose MSBs are all
0 as the node scheduling codes of network, then the MSB
slot is obviously a redundant slot. Therefore, at least k +
1 redundant slots can be founded and squashed.
Corolla ry 1. Fo r the scheduling matrix A of a (s, M, T)
cover-free set, if its row vectors have equal weight M-w,
then if the node number N satisfies
(1)
M
iwNMiw （01
M
iw  , and i is
an integer） , the algorithm can squash at least i redundant
slots.
Proof: Since the scheduling matrix is just the com-
plementary matrix of that in Theorem 3, the proof is ob-
vious.
5. Apply into Popular Topology-Transparent
Node Scheduling Strategies
Based on Theorem 3, the performance of our algorithm
can be estimated if the row vectors in scheduling matrix
have equal weight. Therefore, to show its universality,
we prove that the most popular topology-transparent no-
de scheduling strategies generate scheduling matrix with
equal weight.
5.1. Strategy Based on the Multinomial Theory
in Galois Field
Both Chlamtac’s and Ju’s algorithm are based on the
multinomial theory in Galois field. Based on two input
parameters, the node number N and the maximal node
degree Dmax, two parameters q and k are get based on a
sufficient condition of forming a cover-free set. Further,
based on q and k, every node is associated with a unique
vector (ak, ak-1, …, a0), where []( 0,1,...,)
i
aqi k . In
other word, every node is associated with a unique mul-
tinomial 1
110
...
kk
kk
axaxax a


 .
To map from the multinomial to scheduling matrix, a
frame is divided into q subframes and a subframe is fur-
ther divided into q slots. Every node has transmission
right only at one slot dur ing a subfr ame. For ex ample, for
the subframe i, []iq, node which is associated with
the vector (ak, ak-1, …, a0) has transmission right only at
the 1
110
((...) mod)
kk
kk
aiaiaiaq th


 slot in
the subframe i.
Theorem 4. For scheduling matrix generated by
strategy based on the multinomial theory in Galois field
with parameters q and k, its row vectors have equal
weight qk.
Proof: Based on the principle of the algorithm, the
weight of the jth row vector in scheduling matrix is the
number of node which has transmission right at the jth
slot. For the slot j in subframe i, it is the number of vec-
tor (ak, ak-1, …, a0) which satisfies
1
110
(...)mod
kk
kk
aiaiai aqj



 .
Assume 1
11
...
kk
kk
aiaiaimq z



 ,01zq


where m is an integer. For every z, there is a unique
0()modajzq

 which satisfies
1
110
(...)mod
kk
kk
aiaiai aqj



 , i.e., a0 is
determined by (ak, ak-1, …, a1). In other word, there are k
independent variables in (ak, ak-1, …, a0). So, the number
of (ak,ak-1,…,a0) which satisfies
1
110
(...)mod
kk
kk
aiaiai aqj



 is qk, i.e.,
the row vectors of scheduling matrix have equal weight
qk.
5.2. Strategy Based on the Orthogonal Array
Definition 5. A OA(k, t, v) is a k
tv matrix with en-
tries from [v], 0kt

, if for any k
kv submatrix,
each of its vk column vectors is unique.
A OA(k, t, v) can be mapped into a k
vt v schedul-
ing matrix. A frame is composed of vt slots. Each node is
assigned a unique column vector of orthogonal array as
its scheduling code. For example, if a node is assigned a
column vector (0, 3, 1), its scheduling code is
000110000010.
Theorem 6. For scheduling matrix generated by stra-
tegy based on OA(k, t, v), its row vectors have equal
weight vk-1.
Proof: For any k row vectors in OA(k, t, v), they form
a k
kv

matrix. Since every column vector in the
k
kv

matrix is unique, there are vk different k-tuples.
Since every entry in [v] appears equal times in any row
vector, every entry appears vk-1 times in any row vector.
Based on the mapping from orthogonal array to schedul-
ing matrix, every row vector of scheduling matrix has
equal weight vk-1.
5.3. Strategy Based on Orthogonal Latin
Square
Definition 7. A orthogonal latin square with order p is a
pp

matrix, with every row and every column to be a
full permutation of [p].
Definition 8. Two different nn latin squares A =
(ai, j), B = (bi,j), ,{1,2,...,}ij n

is orthogonal if all
2-tuples (ai,j, b
i,j) are different. As a generalization, r
nn

latin squares A(1),A(2),…,A(r) form a latin squares
family with order (r, n) if they are different and ortho-
gonal between any two of them. Especially, if r = n-1,
the latin squares family is a complete orthogonal latin
squares family with order n.

C. N. XU 805
A complete orthogonal latin squares family with order
n can be mapped into a 2(1)nnn scheduling matrix.
For all n(n-1) column vectors in the family, each of them
can be associated to a node as its scheduling code.
Theorem 6. If n is a prime or prime power, for sche-
duling matrix generated by strategy based on a complete
orthogonal latin squares family with order n, its row
vectors have equal weight n-1.
Proof: Since a complete orthogonal latin squares fam-
ily with order n consists of n-1 latin squares if n is a
prime or prime power. For each latin square, every ele-
ment appears just once in any column and row. So, the
weight of the scheduling matrix is n-1 based on the map-
ping from latin square to scheduling matrix.
6. Experiments
We take the Chlamtac algorithm for examples to test the
effect of the redundant slot squashing algorithm.
Based on the principle of Chlamtac algorithm, given
the node number N and the maximum nodal degree Dmax,
the two parameters, q and k, can be get. For example, if
N = 120，Dmax = 5, then q = 1 1，k = 2. That is, we have
qk+1 = 1331 candidate node scheduling codes for 120
nodes. In fact, there are at least 11 redundant slots can be
squashed. Figure 2 illustrates the relationship among
qk+1/N, N and Dmax generated by Chlamtac algorithm.
Obviously, the larger the qk+1/N is, the more redundant
slots can be anticipated.
Seen from Figure 2, qk+1/N increases quickly with N
or Dmax. So it can be easily anticipated that our algorithm
performs better in network with more nodes or larger no-
de degree.
We now begin to test the effect of our algorithm under
various values of N and Dmax for Chlamtac algorithm.
The range of N is 2~60, and that of the maximal node
degree is 1~N-1, i.e., all possibilities of maximal node
degree are tested. Figure 3 illustrates the effect of our
algorith m. The th ree coordinates are the node number N,
the maximal node degree Dmax and the number of redun-
dant slot. It can be found from Figure 3 that ther e a lwa ys
exist redundant slots in any case. The larger the N or
Dmax is, the more redundant slots can be squashed, which
is consistent with our anticipation.
7. Conclusions
The topology-transparent node scheduling strategy is suit-
able for MANET because it can provide guaranteed QoS
and be independent of network topology. In this paper, to
improve QoS guarantee, we present a universal algo-
rithm which can be realized as an accessory of any to-
pology-tran s pa re nt n ode scheduling strategy nowaday s.
Figure 2. The relationship among qk+1/N, N and Dmax gener-
ated by the Chlmatac algorithm.
Figure 3. The effect of redundant slot squashing algorithm
for the Chlamtac algorithm.
Node scheduling codes generated by each topology-
transparent node scheduling algorithm nowadays form a
cover-free set. We propose the redundant slot of the cov-
er-free set, and prove that the redundant slot has negative
influence on the minimal guaranteed throughput. Further,
we prove that any subset of a cover-free set is still a cov-
er-free set after any of its redundant slots is squashed.
Our algorithm chooses the subset which has the maximal
number of redundant slots, squashes all redundant slots
of the subset, and then designates it as the node schedul-
ing strategy of wireless network. Both theoretical analy-
sis and experiments prove that the increased minimal
throughput and decreased maximal transmission delay
are guaranteed. Simulation results reveal that the larger
the network node number or the maximal node degree, the
better QoS can be guaranteed by employing our algorithm.
8. References
[1] X. Lin and N. Shroff, “The Impact of Imperfect Schedul-
ing on Cross-layer Congestion Control in Wireless Net-
works,” IEEE/ACM Transactions on Networking, Vol. 14,

806 C. N. XU
No. 2, 2006, pp. 302-315.
[2] R. Nelson and L. Kleinrock, “Spatial TDMA - A Colli-
sion-Free Multihop Channel Access Protocol,” IEEE Tran-
sactions on Communications. Vol. 33, No. 9, 1985, pp.
934-944.
[3] T. Moscibroda, R. Wattenhofer and Y. Weber, “Protocol
Design Beyond Graph-based Models,” Proceedings of the
ACM 5th Workshop Hot Topics in Networks, Pisa, 2006,
pp. 25-30.
[4] A. Behzad and I. Rubin, “On the Performance of Graph-
Based Scheduling Algorithms for Packet Radio Networks,”
Proceedings of the IEEE Global Telecommunications Co n-
ference, San Francisco, 2003, pp. 3432-3436.
[5] A. Shen, “Combinatorial Theory,” Shanghai Jiao Tong Uni-
versity Press, Shanghai, 2008.
[6] I. Chlamtac and A. Farago, “Making Transmission Sche-
dules Immune to Topology Changes in Multi-Hop Packet
Radio Networks,” IEEE/ACM Transactions on Network-
ing, Vol. 2, No. 1, 1994, pp. 23-29.
[7] J. Ju and V. O. K. Li, “An Optimal Topology-Transparent
Scheduling Method in Multihop Packet Radio Networks,”
IEEE/ACM Transactions on Networking, Vol. 6, No. 3,
1998, pp. 298-306.
[8] V. R. Syrotiuk, C. J. Colbourn and A. C. H. Ling, “To-
pology-Transparent Scheduling for MANETs Using Or-
thogonal Arrays,” Proceedings of the 9th Annual Interna-
tional Conference on Mobile Computing and Networking,
San Diego, 2003, pp. 43-49.
[9] J. Ju and V. O. K. Li, “TDMA Scheduling Design of
Multihop Packet Radio Networks Based on Latin Squares,”
IEEE Journal on Selected Areas in Communications, Vol.
17, No. 8, 1999, pp. 1345-1352.
[10] B. Xiang and Y. M. Mao, “Balanced Incomplete Block
Designs Based Scheduling Scheme for Multi-Hop Ad
Hoc Networks,” Proceedings of IEEE International Con-
ference on Communications, Circuits and Systems, Xia-
men, 2008, pp. 388-393.
[11] A. Dey, “Theory of Block Designs,” John Wiley & Sons,
New York, 1986.
[12] P. C. Li, G. H. J. Van Rees and R. Wei, “Constructions of
2-Cover-Fee Families and Related Separating Hash Fam-
ilies,” Journal of Combinatorial Designs, Vol. 14, No. 6,
2006, pp. 423-440.
[13] H. K. Kim and V. Lebedev, “On Optimal Superimposed
Codes,” Journal of Combinatorial Designs, Vol. 12, No.
2, 2004, pp. 79-91.
[14] W. H. Kautz and R. C. Singleton, “Nonrandom Binary
Superimposed Codes,” IEEE Transaction on Information
Theory, Vol. 10, No. 4, pp. 363-377, 1964.
[15] P. Erdos, P. Frankl and Z. C. Furedi, “Families of Finite
Sets in Which No Set is Covered by the Union of R Oth-
ers,” Israel Journal of Mathematics, Vol. 51, No. 1-2,
1985, pp. 79-89.