International Journal of Distributed Sensor Networks
of wireless media, each node can broadcast the data packets
to all neighbor nodes with only one transmission. As a result,
the objective of traditional broadcasting algorithm is to deter-
mine the forwarding nodes in broadcasting. Each forwarding
node retransmits the data packets once aer receiving them
to complete the broadcasting process. However, considering
the eect of sleeping schedule, the active time-slots of nodes
are always dierent. A node cannot guarantee that all its
neighbors are able to receive the data package successfully
with one transmission. As a result, the broadcasting problem
becomes dierent from the traditional WSN and thus is
needed to be redened. We dene a broadcast backbone ()
on (,) as a subset of V, where the broadcast backbone
is the set of forwarding nodes. e data package will be
forwardedinthenetworkonthebroadcastingbackbone.Also
we dene a broadcast schedule BS(B)asthesetofSL
𝑠
(V) in
which v is the node in broadcasting backbone B.Wealso
dene Cov
𝑖
(V) as the set of neighbor nodes in which node
v covers at time-slot i. e sleeping schedule-aware broadcast
problem can be described as follows.
Denition 1 (the sleeping schedule-aware broadcast (SA-
broadcast)). Given a WSN with sleeping schedule which is
modeled as a UDG (,), nd a connected backbone ()
for broadcast and a corresponding broadcast schedule BS()
so that
V∈𝐵
(
𝑖∈SL
𝑠
(V)
COV
𝑖
(V)) = .
Dierent broadcasting algorithms have dierent broad-
cast backbones and broadcast schedules, which determine the
number of transmissions and the broadcast latency. Finally
we present a useful denition.
Denition 2 (inversion). Given a data transmitting node
sequence V
0
,V
1
,...,V
𝑘
,V
𝑘+1
,..., for two adjacent transmitting
and receiving nodes V
𝑘
and V
𝑘+1
,ifSL
𝑎
(V
𝑘
)≤SL
𝑎
(V
𝑘+1
)holds,
we dene it as an inversion.
When node receives a data package at time-slot SL
𝑎
()
and sends data to node c through node b,ifthereisno
inversion, node c can receive the data package within the
minimum latency: SL
𝑎
() − SL
𝑎
() time-slots. If an inversion
exists, for example, SL
𝑎
() ≥ SL
𝑎
(),thelatencyofnode
c receiving the data package will be increased by || time-
slots. If the inversion appears k times, the time-slots will
be increased by ||. erefore, to decrease the latency, we
usually try to avoid the appearance of inversions in the
sequence of forwarding nodes from the source node to the
destination node.
4. Local Algorithm for SA-Broadcast Problem
In this section, we introduce the details of the proposed SALB
algorithm. e design of SALB algorithm consists of two
parts: construction of a broadcast backbone and the active
time-slot-oriented forwarding mechanism.
4.1. Construction of Broadcast Backbone. Among existing
broadcast backbone constructing algorithms, the MCDS is
proved to have the minimum forwarding nodes, perform-
ing well in reducing both transmission and latency [].
erefore, we would like to use a MCDS as the broadcast
backbone. Many MCDS constructing algorithms have been
proposed so far, like [–]. Among them, a widely used
local algorithm for mobile ad hoc networks proposed by
Alzoubi et al. in [] has constant message complexity and
constant approximation ratio. erefore, we employ this
algorithm with some modication here to construct the
broadcast backbone of SALB.
As described in [, ], the construction of broadcast
backbone can consist of two phases: dominator election
and dominator connection. e elected dominators and
connectors form a connected dominating set (CDS), acting
as the broadcast backbone. In the construction phase of the
broadcast backbone, we assume that all nodes are in the
active state. Aer the construction, each node will become
a dominator, a dominate, or a connector. According to [],
there must be a dominator within three hop distance of any
dominator. During the broadcast, each dominator delivers
message to its neighbors, and connectors relay messages
among dominators. Each node maintains a forwarding node
list FWD
LIST, containing the IDs of destination nodes
and their active time-slots. e FWD
LIST will be used in
designing the forwarding mechanism.
4.1.1. Electing Dominators. We assume that each node in the
networkobtainsallits-hopneighbors’IDandactivetime-
slot by exchanging beacon messages. To reduce inversions in
thebroadcastprocess,wewouldliketomaketheactivetime-
slot of each dominator smaller than its neighbors’. Let (V)
be the set of node V’s -hop neighbors. We dene a metric
to represent the possibility of no inversion happening while a
node transmits to its neighbors:
=
| ∈
(
V
)
,SL
𝑎
(
V
)
< SL
𝑎
(
)
|
(
V
)
|
.
()
In electing the dominators, nodes with larger value of will
be more likely to win. Initially, all nodes are in the “Blank”
state.enthemodiedelectionprocedurebasedonthatin
[]withmetric is as follows.
(i) A Blank node becomes a dominator if it has the
largest among all its Blank -hop neighbors and then
broadcast a message IamDominator (ID, i)withitsID
and active time-lot i (IDisusedtobreakthetie).
(ii) A Blank node becomes a dominator if there are no
Blank nodes nor dominators in its -hop neighbors
(knowledge from the received IamDominatee mes-
sage) and then broadcast the IamDominator(ID, i)
message.
(iii) A Blank node becomes a dominatee if it receives a
IamDominator message and then broadcast message
IamDominatee(ID, i).
Aer election, if a dominator has the largest ID among
all its dominatee V’s neighbor dominators, it stores the ID and
thescheduleofactivetime-slotsofV in its FWD
LIST. Each