Wireless Ad Hoc and Sensor Networks

Greedy-based Construction of Load-balanced Virtual Backbones

 21

LBCDS-approximate algorithm as shown in Algorithm 1 is a centralized one-

phase greedy algorithm. Initially, all the nodes are white. All black nodes form an

LBCDS finally. We use the following terms in the algorithm: d

i

: degree of node s

i

,

and

¯

d: mean degree of G.

Algorithm 1: : LBCDS-Approximate

Require: A WSN represented by graph G =(V,E); Node degree d

i

; Mean degree

of the graph

¯

d.

1: Make all nodes white {dominatee nodes}.

2: Sort the n sensors based on their |d

i

−

¯

d| values. If there exists a tie, use greater

d

i

value to break the tie, where 1 ≤ i ≤ n. The node IDs are stored in the sort ...