Topology-Transparent Duty Cycling for Wireless Sensor Networks

Computer Science& Engineering Arizona State University syrotiuk@asu.edu

Abstract
Our goal is to save energy in wireless sensor networks (WSNs) by periodic duty-cycling of sensor nodes. We schedule sensor nodes between active (transmit or receive) and sleep modes while bounding packet latency in the presence of collisions. In order to support a dynamic WSN topology, we focus on topology-transparent approaches to scheduling; these are independent of detailed topology information. Much work has been done on topology-transparent scheduling in which all nodes are active. In this work, we examine the connection between topology-transparent dutycycling and such non-sleeping schedules. This suggests a way to construct topology-transparent duty-cycling schedules. We analyse the performance of topology-transparent schedules with a focus on throughput in the worst case. A construction of topology-transparent duty-cycling schedules based on a topology-transparent non-sleeping schedule is proposed. The constructed schedule achieves the maximum average throughput in the worst case if the given nonsleeping schedule satisfies certain properties.

1

Introduction

Wireless sensor networking has been a growing research area for the last years. It has a wide range of potential applications, such as environment monitoring, smart spaces, medical systems and robotic exploration. In sensor networks, sensor nodes are normally battery-operated and energy efficiency has become one of the most important constraints on sensor networks [1, 12]. Studies have identified that idle listening is a significant consumer of power [17, 14, 24, 21, 26, 15]. Previous works (e.g.,
1,2 This work is partly supported by the European Commission, project IST-15964. The views given herein represent those of the authors and may not necessarily be representative of the views of the project consortium as a whole. 1-4244-0910-1/07/$20.00 c 2007 IEEE.

[24, 25, 4, 15]) show that, in networks where the traffic load is light most of the time, energy efficiency can be achieved by periodic duty cycling of sensor nodes, that is, scheduling sensor nodes between active and sleep mode. An efficient synchronization mechanism is required by most duty cycling schemes (e.g., [24, 15]). Compared to a TDMA scheme, duty cycling schemes require a much looser synchronization. This low precision requirement enables us to save energy by reducing message exchanges for synchronization. Efficient synchronization protocols have been proposed for sensor networks (e.g., [8, 11, 20, 23, 10]); in particular, works have been done on synchronization for duty cycling (e.g., [23, 10]). In this work, we assume an efficient synchronization scheme is available and we describe system behavior in terms of time slots. Although light traffic networks are the scenarios for which duty cycling schemes are primarily considered, it does not mean collision is no longer a concern. Consider a network in which each node is scheduled to be awake in one of k slots. Since a node has to wait until the receiver wakes up before it can forward the packet, transmissions from neighbors, which were distributed in k slots, now happen in one slot, making a collision very likely. In this work, we aim to save energy by scheduling periodic nodes’ duty cycles while preserving communication connectivity and bounding packet latency in the presence of collisions. In order to handle dynamic topology, we focus on topology-transparent approaches that are independent of topology changes. Given a set of networks N , we say a schedule is topology-transparent with respect to N if, for any network in N , it allows each node to transmit without collisions to each neighbor node infinitely often; the range of N represents the level of transparency. Such an approach tolerates topology changes since for every possible topology, given the same topology-transparent schedule, connectivity of each link is guaranteed. As existing works on topology-transparent schedules [2, 13, 3, 6], our work focuses on topology-transparency in networks where the number of nodes and node degrees are no more than given

bounds. Research has been done on topology-transparent schedules where no node is scheduled to sleep [2, 13, 3]; we refer to such schedules as non-sleeping schedules. In this work, we consider duty cycling of sensor nodes which aims to save energy by switching nodes between active and sleep mode. Letting αT and αR be parameters that capture applications’ requirement on energy efficiency, we focus on schedules in which the number of nodes that are allowed to transmit (receive resp.) per slot is no more than αT (αR resp.); we call such a schedule an (αT , αR )-schedule. Such schedules have been considered in [6], where the requirements on topology-transparent (αT , αR )-schedules are described by a general combinatorial model and a graph construction algorithm is examined with the focus on a special type of schedules in which the number of nodes transmitting and receiving per slot are equal. Different from [6], our work focuses on general schedules and has three main contributions. First, we examine in section 4 the connection between topology-transparent (αT , αR )-schedules and non-sleeping schedules. Our analysis indicates that, given bounds on the number of nodes and node degrees, a necessary condition for the existence of a topology-transparent (αT , αR )schedule, for any αT and αR , is the existence of a topologytransparent non-sleeping schedule; furthermore, any construction of a topology-transparent (αT , αR )-schedule involves the construction of a topology-transparent nonsleeping schedule. Secondly, we present our analyses in section 5 on schedules’ performance; as most works on topology-transparent schedules (e.g., [13, 3]), we consider throughput in the worst case, that is, each node has the maximum degree and each neighbor has a packet to transmit. We show that the average throughput in the worst case only depends on the number of nodes that are allowed to transmit and receive per slot. An upper bound on the average throughput, together with the optimal numbers of transmitters and receivers per slot to achieve this upper bound, is given for both general schedules and (αT , αR )-schedules for given αT and αR . Our analyses indicate that a necessary condition for the existence of a topology-transparent (αT , αR )schedule to achieve this upper bound is the existence of a topology-transparent non-sleeping schedule that has certain properties. Thirdly, we investigate in section 6 whether a topologytransparent non-sleeping schedule (that has the appropriate properties) can be converted to a topology-transparent (αT , αR )-schedule (that has good performance). This is motivated by our observation in sections 4 and 5 that a necessary condition of the existence of a topology-transparent (αT , αR )-schedule (that has good performance) is the existence of a non-sleeping topology-transparent schedule (that satisfies certain properties), and any construction of a

topology-transparent (αT , αR )-schedule involves the construction of a topology-transparent non-sleeping schedule. Our answer to this question is positive and we present a construction of an (αT , αR )-schedule based on a non-sleeping schedule. Such a conversion is feasible since much work has been done on the construction of topology-transparent non-sleeping schedules (e.g. [2, 13, 22, 3]), and it has been pointed out in [22, 3] that topology-transparent nonsleeping schedules can be constructed by cover-free families, which have been well investigated by numerous researchers (e.g., [9, 7, 16, 19, 18, 5]). Our construction is very straightforward and it shows good properties. We prove that given any topologytransparent non-sleeping schedule, a topology-transparent (αT , αR )-schedule can be constructed by our approach for any αT and αR . The performance of the constructed schedule depends on the number of transmitters per slot in the non-sleeping schedule — given n and D, the constructed schedule is optimal in terms of average worst-case throughput if the number of transmitters per slot in the non-sleeping schedule is at least min{αT , n−D }, otherwise the larger D is the minimum number of transmitters per slot, the better average throughput can be achieved. We also give a lower bound on the minimum throughput.

2 Related work
Research has been done on topology-transparent nonsleeping schedules [2, 13, 22, 3]. These works aim to guarantee communication between any pair of adjacent nodes in the presence of collisions. It is pointed out in [22, 3] that topology-transparent non-sleeping schedules can be constructed by a cover-free family, and the constructions in [2, 13] are indeed to construct a cover-free family using an orthogonal array. Cover-free families were first introduced in [9] and have been considered in different subjects such as information theory, combinatorics and group testing by numerous researchers (e.g., [7, 16, 19, 18, 5]). All these research results provide a strong base for the construction of a topology-transparent duty cycling based on a topology-transparent non-sleeping schedule. The details of how to construct non-sleeping schedules and cover-free families are out of the scope of this paper; see [3, 5] for more information. Topology-transparent duty cycling which aims to achieve energy efficiency by scheduling nodes to sleep was first considered in [6], in which a general combinatorial model is described. In [6], a graph construction algorithm is examined with the focus on a special type of schedules in which the number of nodes transmitting and receiving per slot are equal. Note such schedules are optimal when the cost to transmit and receive are the same order of magnitude; furthermore, the number of interferences is bounded

in the constructed schedules. In this work, we focus on general cases and a different construction is considered. Throughput in the worst case has been investigated in [13, 3] for topology-transparent non-sleeping schedules that are constructed in certain ways. The focus in [13] is on schedules constructed using polynomial functions of degree k mod p; note polynomial function is only one of the standard constructions of cover-free family based on orthogonal arrays. The focus in [3] are on schedules based on cover-free families constructed from orthogonal arrays and Steiner systems. Different from these works, we consider throughput for general schedules; by saying general schedules, we mean there is no constraint on how schedules are constructed, schedules can be topology-transparent or not, and schedules can be non-sleeping or not.

packet transmissions might fail due to many reasons. We restrict our attention to failures caused by collisions — by saying node x is guaranteed to successfully transmit to node y in some slot, we mean in this slot y is eligible to receive and x is the only node in y’s neighborhood that is allowed to transmit. Given two adjacent nodes x and y, if there exist slots in which node x is guaranteed to successfully transmit to node y, we say the connectivity from node x to y is guaranteed. As most works on topology-transparency, given two parameters n and D, 2 ≤ D ≤ n, we consider a class of D networks, denote by Nn , that consist of at most n nodes, denoted by Vn , and in which node degrees are no more than D.

4 Requirements on topology-transparency
In this section we consider the requirements on topology-transparent schedules. Informally, a schedule is topology-transparent if the connectivity between any pair of adjacent nodes is guaranteed in any network where the number of nodes and node degrees are bounded by given values. The requirement on topology-transparent duty cycling has been proposed in [6]. Here we give an equivalent requirement which presents a connection between topology-transparent (αT , αR )-schedules and non-sleeping schedules. This connection implies that any construction of a topology-transparent (αT , αR )-schedule involves the construction of a topology-transparent non-sleeping schedule. It also suggests a way to construct a topology-transparent (αT , αR )-schedule based on a topology-transparent nonsleeping schedule. Since our construction is based on a topologytransparent non-sleeping schedule, we present in Requirement 1 the requirement proposed in [3] on topologytransparent non-sleeping schedules. Given a schedule T, R , a node x and a set Y of nodes, we define a denotation to represent the set of slots in which node x is guaranteed to successfully transmit to a node y ∈ Y whose neighborhood is Y − {y} ∪ {x}. Intuitively, in each of these slots, x is the only node that is allowed to transmit among the neighbors of y. f reeSlots
T ,R

3

System model

We assume time is structured into discrete units called slots. A schedule of node activities is represented by a pair T, R , where T and R are two disjoint arrays with the same length, say L, such that ∀i ∈ [0, L − 1], T [i] ⊆ V and R[i] ⊆ V ; T [i] and R[i] are the sets of nodes that are eligible to transmit and receive respectively in slots i + Ll, l = 0, 1, . . ., while other nodes turn off their radio and stay in sleep mode. We say T is the transmission schedule and R is the reception schedule. We call the L continuous slots lL, lL + 1, . . . , lL + L − 1, ∀l ≥ 0, a frame, and L is the frame length. Given a schedule T, R and a node x, we denote the set of slots in which x is allowed to transmit and receive by tran T ,R (x) = {i ∈ [0, L − 1]|x ∈ T [i]} and recv T ,R (x) = {i ∈ [0, L − 1]|x ∈ R[i]} respectively. The subscript T, R is omitted when it is clear from context. In this work, our goal is to design a schedule of nodes’ activities where nodes are put into sleep mode to meet applications’ requirement on energy saving. We use two parameters αT and αR to describe applications’ requirement on energy efficiency: the maximum number of nodes that are allowed to transmit and receive per slot are no more than αT and αR respectively. Given αT and αR , we aim to design a schedule T, R that has the desirable property, that is, ∀i ∈ [0, L − 1], |T [i]| ≤ αT and |R[i]| ≤ αR , where L = |T | = |R|; we call such a schedule an (αT , αR )schedule. We say a schedule T, R is a non-sleeping schedule if all nodes are active in each slot, that is, ∀i ∈ [0, L−1], T [i] ∪ R[i] = V . Since such a schedule can be completely decided by T , we abbreviate the representation T, R to T . Our focus is on topology-transparent scheduling. Given a set N of networks, a schedule is topology-transparent for networks in N if it ensures that, for any network in N , each node is guaranteed to successfully transmit a packet to each adjacent node in at least one slot of each frame. In practice,

(x, Y ) ≡ tran

T ,R

(x) − y∈Y tran

T ,R

(y)

Note given any two nodes x, y and any set S ⊆ Vn − D {x, y} of D − 1 nodes, there exists network in Nn such that x and y are adjacent and y’s neighborhood is {x} ∪ S. Thus a topology-transparent schedule should guarantee ∀x, ∀y, ∀ S ⊆ Vn − {x, y} such that |S| = D − 1, f reeSlots(x, S ∪ {y}) = ∅, which is equivalent to ∀x, ∀ Y ⊆Vn − {x} such that |Y | = D, f reeSlots(x, Y ) = ∅. On the other hand, if this condition is true, for any network

D in Nn , given any two adjacent nodes x and y, denoting y’s neighborhood by S ∪ {x}, we have f reeSlots(x, S ∪ {y}) ⊆ f reeSlots(x, Y ) = ∅, where Y is some set of D nodes such that S ∪ {y} ⊆ Y , thus the connectivity from x to y is guaranteed. This requirement is formally addressed below.

Theorem 1 Requirement 2 and Requirement 3 are equivalent.

Requirement 1 [3] A non-sleeping schedule T ensures a successful transmission in each frame between any pair of D adjacent nodes in any network in Nn provided that
• ∀x ∈ Vn , ∀ set Y ⊆ Vn − {x} of D nodes, f reeSlots
T

(x, Y ) = ∅

We give in Requirement 2 the requirements proposed in [6] on topology-transparent schedules where nodes might switch to sleep mode. Intuitively, σ(x, y) denotes the set of slots in which node x can successfully transmit to node y. It is required at least one slot in σ(x, y) is collision-free for any two nodes x and y under any possible neighborhood of y. Requirement 2 [6] A schedule T, R ensures a successful transmission in each frame between any pair of adjacent D nodes in any network in Nn provided that
• ∀x, y ∈ V , x = y, and ∀ set of d ≤ D − 1 nodes {y1 , . . . , yd } ⊆ Vn − {x, y}, d Proof. We first prove if a schedule satisfies Requirement 2, then it satisfies Requirement 3; we only need to prove condition (2) of Requirement 3, which implies condition (1). Assume in contradiction that condition (2) is not true, that is, ∃ node x and D nodes y0 , . . . , yD−1 , and k ∈ [0, D − 1], such that recv(yk ) ∩ f reeSlots(x, {y0 , . . . , yD−1 }) = ∅. By the definition of f reeSlots, we have recv(yk ) ∩ tran(x) − ∪D−1 tran(yi ) = ∅, which implies i=0 recv(yk ) ∩ tran(x) ⊆ ∪D−1 tran(yi ), that is, σ(x, yk ) i=0 ⊆ ∪D−1 tran(yi ). Now for any t ∈ σ(x, yk ), we prove i=0 ∃k ∈ [0, D−1], k = k, such that t ∈ σ(yk , yk ) as follows: since σ(x, yk )∩tran(yk ) = tran(x)∩recv(yk )∩tran(yk ) = ∅ and σ(x, yk ) ⊆ ∪D−1 tran(yi ), we have i=0 ∃k ∈ [0, D − 1], k = k, such that t ∈ tran(yk ); since t ∈ recv(yk ), we have t ∈ σ(yk , yk ). Thus we prove ∪D−1 σ(yi , yk ) ⊇ σ(x, yk ), which contradicts to i=k,i=0 Requirement 2. Now we prove if a schedule satisfies Requirement 3, then it satisfies Requirement 2. Consider ∀x, y ∈ V , x = y, and d ≤ D − 1 nodes y1 , . . . , yd ∈ Vn − {x, y}. By condition (2) of Requirement 3, we have recv(y) ∩ f reeSlots(x, {y1 , . . . , yd }) = ∅, which implies σ(x, y) ∩ (tran(x) − ∪d tran(yi )) = ∅. Letting t be i=1 a slot in σ(x, y) ∩ (tran(x) − ∪d tran(yi )), we have i=1 t ∈ ∪d tran(yi ). Thus ∀i ∈ [1, d], t ∈ σ(yi , y) and we i=1 prove ∪d σ(yi , y) ⊇ σ(x, y). i=1

σ i=1 T ,R

(yi , y) ⊇ σ

T ,R

(x, y)

where, letting L = |T | = |R|, we define σ
T ,R

(a, b)

≡ =

{j ∈ [0, L − 1]|a ∈ T [j] ∧ b ∈ R[j]} tran
T ,R

(a) ∩ recv

T ,R

(b)

Since much work has been done on topology-transparent non-sleeping schedule, here we examine the connection between topology-transparent non-sleeping schedules and duty cycling. We propose a requirement equivalent to Requirement 2. Intuitively, given any node x and any set Y of D nodes, for any yk ∈ Y , condition (1) requires the existence of slots in which x is the only node in yk ’s neighborhood that is allowed to transmit and condition (2) requires yk is eligible to receive in at least one of these slots. Note condition (1) is implied by condition (2); we write it separately to emphasize that condition (1) states that the nonsleeping schedule T should be topology-transparent. Requirement 3 A schedule T, R ensures a successful transmission in each frame between any pair of adjacent D nodes in any network in Nn provided that
• ∀ x ∈ Vn and ∀ set of D nodes Y = {y0 , . . . , yD−1 } ⊆ Vn − {x}, f reeSlots ∀k∈[0,D−1], recv
T ,R T ,R T ,R

(x, Y ) = ∅ (x, Y ) = ∅

(1) (2)

(yk ) ∩ f reeSlots

Given any topology-transparent schedule T, R , Requirement 3 states that the non-sleeping schedule T is also topology-transparent, which implies that any construction of a topology-transparent (αT , αR )-schedule involves the construction of a topology-transparent non-sleeping schedule. Furthermore, condition (2) of Requirement 3 indicates that given a non-sleeping schedule, as far as connectivity is concerned, it is not necessary to keep all the non-transmitting nodes active; instead, nodes can be scheduled to sleep provided that they are active in at least one of the free slots. Based on this observation, we consider constructing a topology-transparent schedule in two steps: we first construct a topology-transparent non-sleeping schedule, and then reduce the numbers of nodes transmitting and receiving per slot without violating the topologytransparency requirement. In the sequel, we discuss in section 5 the throughput achievable in networks with the number of nodes and node degrees less than given bounds; then we propose our construction in section 6, with the focus on the second step since much work has been done on constructing topology-transparent non-sleeping schedules,

5

D Upper bounds on throughput in Nn

where
F
T ,R

In this section, we discuss the throughput of general schedules and general (αT , αR )-schedules for networks in D Nn . Our focus is on throughput in the worst case, that is, each node has D neighbors and each neighbor has a packet to transmit in each of the slots in which it is allowed to transmit. We first give the definitions of the minimum throughput in the worst case and the average throughput in the worst case, then we present our analyses on the average throughput. We give upper bounds on the average throughput that can be achieved by general schedules and general (αT , αR )schedules in the worst case, as well as the condition for a schedule to achieve the upper bound. Given any pair of adjacent nodes x, y, we consider the number of guaranteed successful transmissions from x to y. Letting S be the set of y’s neighbors other than x, we define T T ,R (x, y, S) as the set of slots in which transmissions from x to y are guaranteed to be successful under schedule T, R :
T
T ,R

≡ x,y∈Vn S⊆Vn −{x,y},|S|=D−1

|T

T ,R

(x, y, S)|

(x, y, S) ≡ recv

T ,R

(y) ∩ f reeSlots

T ,R

(x, {y} ∪ S)

Note T T ,R (x, y, S) ⊇ T T ,R (x, y, S ) if S ⊆ S . Since we focus on throughput in the worst case, in our definition of the minimum throughput, we only need to consider S such that |S| = D − 1. Definition 1 Given a schedule T, R , its minimum worstD case throughput T hrmin in Nn is defined below, where T ,R L = |T | = |R|:
T hr min ≡ T ,R
∀x,y∈Vn ,S⊆Vn −{x,y},|S|=D−1

Since our focus is on throughput in the worst case, in the sequel we abbreviate “throughput in the worst case” to “throughput” for presentation simplicity. Note T hrmin T ,R and T hrave are not defined particularly for topologyT ,R transparent schedules. A schedule T, R is topologytransparent if and only if T hrmin >0. If a schedule T, R T ,R is not topology-transparent, we have T hrmin =0, that is, T ,R there exists two nodes x, y and y’s neighborhood S such that no slot exists in which the transmissions from x to y is guaranteed to be successful; the average throughput T hrave can still be computed according to Definition 2. T ,R Requirements 2 and 3 show whether a schedule is topology-transparent depends on how nodes are scheduled to transmit and receive. The theorem below states that the average throughput only depends on the number of transmitters and receivers per slot; furthermore, higher average throughput can be achieved by allowing more nodes to receive. So if there is no constraint on the numbers of receivers and transmitters, the maximum throughput is achieved by a non-sleeping schedule. Note it is not necessary true if only specific topologes are considered, as shown by an example presented later in section 5.2. Theorem 2 Given a schedule T, R , we denote L = |T | = |R|. The average throughput T hrave of T, R in netT ,R D works Nn is T hr T ,R = ave L−1 i=0

min

|T

T ,R

(x, y, S)| L

|T [i]| · |R[i]| n(n − 1)

n−|T [i]|−1 D−1

It is easy to see the average value of |T T ,R (x, y, S )| over all the S such that |S | ≤ D−1 is no less than the average value of |T T ,R (x, y, S)| over all S such that |S| = D−1. So the number of guaranteed successful transmissions in each frame from x to y averaged over all the D possible y’s neighborhoods in Nn is at least: tx T ,R

n−2 D−1

L

Proof. We define C T ,R (i) as the set of tuples x, y, S such that i ∈ T T ,R (x, y, S), where x, y are two different nodes and S is any set of D − 1 nodes other than x and y. Formally,
C
T ,R

(x, y) ≡

S⊆Vn −{x,y},|S|=D−1 n−2 D−1

|T

T ,R

(x, y, S)|

(i) ≡ { x, y, S

|i ∈ T

T ,R

(x, y, S), where x, y ∈ Vn ,

x = y, S ⊆ Vn − {x, y}, |S| = D − 1}

We define the average worst-case throughput T hrave T ,R D of a schedule T, R in Nn as the ratio of the average number of tx T ,R (x, y) over all pairs of nodes x and y to the frame length. Definition 2 Given a schedule T, R , its average worstD case throughput T hrave in networks in Nn is defined beT ,R low, where L = |T | = |R|:
T hr ave T ,R ≡ tx ∀x,y∈Vn
T ,R

We have F T ,R = i∈[0,L−1] |C T ,R (i)|. Since given i, for x,y and S such that i ∈ T T ,R (x, y, S), x can be any node in T [i], y can be any node in R[i], and S can be any D − 1 nodes of those other than nodes in T [i] and y, we have C T ,R (i) = |T [i]| · |R[i]| n−|T [i]|−1 and the theorem D−1 is proved. In the rest of this section, we examine the maximum avD erage throughput in Nn that can be achieved by general schedules and by general (αT , αR )-schedules for given αT

(x, y)

n(n − 1)L

=

F

T ,R

n(n − 1)

n−2 D−1

L

and αR . Before that, we present two properties of function gn,D (x) = x D n−x n n−1
D

for integer x. These properties will

Proof. Given any schedule T, R , we have |R[i]| ≤ n − |T [i]|, ∀i ∈ [0, L − 1]. By Theorem 2, we have
L−1 i=0

be used in our proofs and x will represent the number of nodes that are allowed to transmit in a slot. Intuitively, gn,D (x) represents the throughput of a non-sleeping schedule in which the number of transmitters per slot is fixed at x. (1) ∀x ∈ [0, n − 1], gn,D (x) ≤ nD D (n−D)(D+1)D+1

T hr ave T ,R

=

|T [i]||R[i]|

n−|T [i]|−1 D−1

n(n − 1)
L−1 i=0

n−2 D−1

L n−|T [i]|−1 D−1

≤

|T [i]|(n − |T [i]|) n(n − 1) n−2 D−1

.
=
L−1 i=0

L 1 L
L−1

n−D (2) ∃x0 ∈ , n−D , such that gn,D (x0 ) ≥ D+1 D+1 gn,D (x), ∀ x ∈ [0, n−1].

|T [i]| n−1 D

n−|T [i]| D

n

L

=

gn,D (|T [i]|) i=0 Property (1) is true since gn,D (x) = x
(n−(D−1)−x) 1 n−(D−1) n−D 1 n−D

(n−x) (n−1−x) n n−1

...

=x 1− x D n

x n

1− ≤

x n−1

... 1 −

x n−(D−1)

. Property (2) can be proved by showing the following properties for x ≤ n − (D − 1): (a) gn,D (x) is monotonically increasing up to some point and then monotonically decreasing, and (b) gn,D (x) ≥ gn,D (x + 1) if and only x ≥ n−D since D+1 gn,D (x) gn,D (x+1)

≤ x 1−

1 n−D

nD D (n−D)(D+1)D+1

Note |T [i]| ∈ [1, n − 1]. By property of function gn,D (x), nD D we have T hrave ≤ (n−D)(D+1)D+1 . In order to maxT ,R imize T hrave , gn,D (|T [i]|) should be maximum for all T ,R i ∈ [0, L − 1]. By property of gn,D (x), the maximum gn,D (|T [i]|) is achieved when |T [i]|∈ n−D , n−D . D+1 D+1 Theorem 3 indicates only schedules in which all the nodes are active can achieve the proposed upper bound. Since the number of transmitters and receivers might be constrained due to energy efficiency, we consider in the next section the throughput of schedules with bounded numbers of transmitters and receivers.

=

x(n−x) (x+1)(n−D−x) .

5.1

An upper bound on average throughput

In this section, we consider the average throughput that D can be achieved in networks in Nn by general schedules, where there is no constraint on the numbers of transmitters and receivers per slot. The theorem below presents an upper bound on the average throughput, as well as the condition for a schedule to achieve this upper bound: the number of transmitters in each slot is about n−D and the number of D+1 receivers in each slot is about n − n−D . D+1 Theorem 3 (An Upper Bound on Average Throughput of D General Schedules in Nn ) Given any schedule T, R , letD ting T hrave be its average throughput in networks in Nn , T ,R we have
T hr where αT = ave T ,R

5.2

An upper bound on average throughput of (αT , αR )-schedules

≤

αT n

n−αT D n−1 D

≤

nDD (n − D)(D + 1)(D+1)

  

n−D D+1 n−D D+1

, if

n−D D+1

n− D

n−D D+1

≥

n−D D+1

n− D

n−D D+1

, otherwise

Furthermore, defining T hr T hrave T,R

≡

αT

n−α D D

When only connectivity between any pair of adjacent nodes is considered, Requirement 3 shows it is not necessary to keep all the nodes active. However, Theorem 2 indicates that, the performance is affected by putting nodes into sleep mode if we focus on the average throughput beD tween all pairs of nodes for all the networks in Nn . It is worth pointing out that, if only a specific topology is considered, it is possible to save energy by scheduling nodes to sleep while preserving the same throughput. An example is given in Figure 1, where nodes are denoted by the numbers in circles and arrays T and R are given. We consider two schedules T and T, R : schedule T is a non-sleeping schedule and in schedule T, R some nodes are scheduled to sleep. It is easy to see these two schedules have the same throughput. Now we consider the average throughput T hrave T ,R D of an (αT , αR )-schedule T, R in Nn . By Theorem 2, we have T hrave = T ,R ≤ αR L−1 i=0 n−1−|T [i]| D−1 n−2 n(n−1) L D−1 |T [i]| L−1 i=0 |T [i]|·|R[i]| n−|T [i]|−1 D−1 n−2 n(n−1) L D−1

T

= T hr if and only if T, R is a non-sleeping schedule such that ∀i ∈ [0, L − 1], |T [i]| = αT and |R[i]| = n − αT , where L = |T | = |R|.

n(n−1 )

, we have

=

αR nL

L−1 i=0

gn−1,D−1 (|T [i]|). αR n

By properties of gn−1,D−1 (x), we have T hrave ≤ T ,R

4 3 0 2 1 5

slots

0 {0}

1 {1} {0,5}

2 {2,5} {0,1}

3 {3} {0}

4 {4} {0}

T

R {1,2,3,4}

number of transmitters in each slot is at least αT . Our construction indicates such a condition is also a sufficient condition.

Figure 1. An example of networks in which throughput can be preserved when nodes are scheduled to sleep

6 Our construction of topology-transparent (αT , αR )-schedules
In this section, we present our construction of topologytransparent (αT , αR )-schedules. Given a topologytransparent non-sleeping schedule, our goal is to reduce the number of nodes that are allowed to transmit and receive in each slot, while preserving the connectivity between any pair of adjacent nodes. In our construction, we first compute the optimal number αT of transmitters per slot, then we construct an (αT , αR )schedule by calling function Construct(αT , αR , T ). In this function, for each slot i, we divide T [i] into subsets T [i] = T0 ∪ . . . ∪ TkT −1 and V − T [i] into subsets Vn − T [i] = R0 ∪ . . . ∪ RkR −1 . Note subsets in {Ti |i ∈ [0, kT − 1]} (subsets in {Ri |i ∈ [0, kR − 1]} resp.) are not necessarily disjoint. Instead, in order to achieve maximal throughput, we require each |Ti | to be as close to αT as possible, and each |Ri | to be as close to αR ¯ ¯ as possible. In the constructed schedule T , R , we add kT kR entries to guarantee that each subset of T [i] transmits to each subset of Vn − T [i]; in particular, we require ∀it ∈ [0, kT − 1] and ∀ir ∈ [0, kR − 1], ∃k such that ¯ ¯ T [k] = Tit and R[k] ⊆ Rir . If |Rir | < αR , we add ¯ nodes in Vn − Tit to R[k] to get |R[k]| = αR , which is feasible since Tit ≤ αT and αT + αR ≤ n. Note the way to divide T [i] (line 3) and R[i] (line 4) and the way to add nodes in Vn − Tit to Rir (line 8) are not unique, and the specific way they are computed will not affect the correctness, frame length and average worst-case throughput of the constructed schedule, as we show in Theorem 6, Theorem 7 and Theorem 8 respectively. The code is given in Figure 2.

and the maximum of gn−1,D−1 (|T [i]|) is n−D , n−D . Since |T [i]| achieved when |T [i]| ∈ D D is constrained by the requirement that |T [i]| ≤ αT , we have the following theorem on the average throughput of D an (αT , αR )-schedule in Nn networks. This theorem implies, in order to achieve the best average throughput, the number of receivers in each slot should be as large as possible, while the number of transmitters should be as close to n−D D as possible. Theorem 4 (An Upper Bound on Average Throughput of D (αT , αR )-schedules in Nn ). Given any (αT , αR )-schedule ave T, R , letting T hr T ,R be its average throughput in netD works in Nn , we have αR αT n−αT −1 D−1 n−2 D−1

(n−1)(D−1)D−1 , (n−D)DD

T hr

ave
T ,R

≤

n(n − 1)

≤

αR (n − 1)(D − 1)D−1 n(n − D)DD

where αT = min{αT , α}, and  n− n−D  n−D n−D D α≡  n−D
D

D

if

−1

D

D−1

≥

n−D D

n− n−D −1 D D−1

otherwise αR ·αT n−α T D−1 −1

Furthermore, defining T hrαR ,αT ≡

have T hrave = T hrαR ,αT if and only if ∀i ∈ [0, L − 1], T,R |R[i]| = αR and |T [i]| = αT . Theorem 4 presents an upper bound on the throughput D that is achievable by an (αT , αR )-schedule in Nn networks. An interesting question is whether there exists a topology-transparent (αT , αR )-schedule that achieves this upper bound. Requirement 3 indicates, given any topologytransparent (αT , αR )-schedule T, R , T is a topologytransparent non-sleeping schedule, and Theorem 4 states, in order to achieve the maximum average throughput, it is required |T [i]|=αT , ∀i ∈ [0, |T |−1]. Thus a necessary condition for the existence of a topology-transparent (αT , αR )schedule that achieves this upper bound is the existence of a non-sleeping topology-transparent schedule such that the

n(n−1)(n−2 ) D−1

, we

7 Correctness and performance analyses
In this section, we present correctness proofs and performance analyses of our construction. Given any topologytransparent non-sleeping schedule T , we first show the correctness of the schedule constructed by the algorithm in Figure 2. Then we discuss the frame length and throughput of the constructed schedule. We show that the constructed schedule is optimal in terms of average throughput if the topology-transparent non-sleeping schedule T satisfies ∀i ∈ [0, L − 1], |T [i]| ≥ min αT , n−D . D We first consider the correctness of our construction. In the following lemma, we show that the constructed schedule is topology-transparent.

Input: integers n, D, αT , αR , and schedule T , such that n ≥ D ≥ 2, D αT + αR ≤ n, and T is topology-transparent for networks in Nn . ¯ ¯ Output: An (αT , αR )-schedule T , R that is topology-transparent in D networks in Nn . Main Program: • Let αT be the optimal number of transmitters per slot computed as in Theorem 4. ¯ , R =Construct (α , αR , T ) ; • T ¯ ¯ ¯ • return T , R ;
T

¯ yk ∈ Rir ⊆ R[t ], we have t ∈ recv T ,R (yk ). ¯ ¯ So t ∈ recv T ,R (yk ) ∩ f reeSlots T ,R (x, Y ), that is, ¯ ¯ ¯ ¯ recv T ,R (yk ) ∩ f reeSlots T ,R (x, Y ) = ∅. Thus by Re¯ ¯ ¯ ¯ ¯ ¯ quirement 3, we prove T , R is a topology-transparent D schedule for Nn . It is easy to see the number of transmitters in each slot is no more than αT ≤ αT and the number of receivers in each slot is no more than αR . Thus we prove the correctness of our construction. Theorem 6 (Correctness). The schedule constructed by the algorithm in Figure 2 is an (αT , αR )-schedule that is D topology-transparent for networks in Nn . Our construction also indicates that, given any αT , αR , αT +αR ≤ n, if a topology-transparent non-sleeping schedule T such that |T [i]| ≥ αT , ∀i ∈ [0, |T | − 1] is available, then a topology-transparent schedule such that the number of transmitters in each slot is exactly αT and the number of receivers in each slot is exactly αR can be constructed by calling function Construct(αT , αR , T ). The frame length of the constructed schedule can be obtained directly from the code. Theorem 7 (Frame Length). The frame length of the schedule constructed by the algorithm in Figure 2 is L−1 |T [i]| n−|T [i]| n−Min ≤ Max L, where i=0 αT αR αT αR L = |T |, Max = max{|T [i]|, ∀i ∈ [0, L − 1]} and Min = min{|T [i]|, ∀i ∈ [0, L − 1]}. In order to compare the average throughput of the conD structed (αT , αR )-schedule in Nn networks to the maximum average throughput, we define function r(x) ≡ x αT
D−1

Function Construct (αT , αR , T ) Input: integers αT , αR and a non-sleeping schedule T ¯ ¯ Output: T , R 1 k=0; 2 for i = 0; i < |T |; i + + 3 Divide T [i] into kT =
|T [i]| α
T

subsets T [i] = T0 ∪ . . . ∪ TkT −1 ,
|R[i]|

such that |Ti | = min{αT , |T [i]|}, ∀i ∈ [0, kT − 1]; 4 5 6 7 8 9 10 11 subsets R[i] = R0 ∪ Divide R[i] = V − T [i] into kR = α R . . .∪RkR −1 , such that |Ri | = min{αR , |R[i]|}, ∀i ∈ [0, kR −1]; for it = 0; it < kT ; it + + for ir = 0; ir < kR ; ir + + ¯ ¯ T [k] = Tit , R[k] = Rir , k + +; if |Rir |