Suppose there are N nodes and at most R CRegions. Let A be an R ?—N binary
matrix whose element aij is set if node Nj can communicate with CRegion i in
less than or equal toMhops hops specified beforehand. Let x be an R?—1 vector,
and 1 be the identity vector (all elements are set to 1). Then the objective is to
minimize the number of 1??™s in x, which is translated into objective function
Y = MIN(1???x).
The only constraint is to ensure that each sensor node can communicate with at
least one gateway, which is expressed as
Ax ?? 1.
2. For a given bound k on the number of gateways, minimize the worst-case number
of communication hops for any node to reach a gateway.
To solve this problem, a virtual graph V is constructed over two vertex sets. One
is the set of all sensor nodes, and another is the set of all possible CRegions.
Each sensor node and each CRegion are connected by an edge with the communication
hop as the edge weight. The goal is to select at most K CRegion
vertices such that
a) all sensor nodes are connected to at least one CRegion in graph V .
b) the maximum (worst-case) weight of selected edges in V is minimized.
Using the same symbols as the first problem, let x??? be the complement value of
x (thus x + x??? = 1), minj be the minimum hop to reach a CRegion for node
Nj , m be the maximum of minj for j = 1, 2, . . . ,N, and R?—N matrix H with
element hij records the number of hop counts for node Nj to reach CRegions i.
Pages:
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552