Optimizing Barrier Coverage Quality in Wireless Sensor Networks
Barrier Coverage with Optimized
Quality for Wireless Sensor
Networks
Yung-Liang Lai*
, Jehn-Ruey Jiang
National Central University
Taoyuan Innovation Institute of Technology*
Taiwan
Wireless Sensor based Barrier
Coverage
USA
Wireless sensor
Barrier Coverage Optimization Problem
Barrier Coverage Optimization Problem
How to construct a barrier coverage such that :
How to construct a barrier coverage such that :
Degree of Detecting intruders is Maximized
Degree of Detecting intruders is Maximized
,
Probability of Detecting intruders is Maximized
Probability of Detecting intruders is Maximized
Data transmission time is Minimized?
Data transmission time is Minimized?
Barrier Coverage Optimization Problem
Barrier Coverage Optimization Problem
T
o
o
p
t
i
m
i
z
e
Q
u
a
l
i
t
y
o
f
B
a
r
r
i
e
r
C
o
v
e
r
a
g
e
W
e
d
e
f
i
n
e
t
h
r
e
e
Q
u
a
l
i
t
y
m
e
t
r
i
c
s
d
e
t
e
c
t
i
o
n
d
e
g
r
e
e
,
d
e
t
e
c
t
i
o
n
p
r
o
b
a
b
i
l
i
t
y
,
e
x
p
e
c
t
e
d
t
r
a
n
s
m
i
s
s
i
o
n
t
i
m
e
W
e
m
o
d
e
l
t
h
e
p
r
o
b
l
e
m
a
s
a
G
r
a
p
h
P
r
o
b
l
e
m
S
o
l
v
e
i
t
b
y
t
h
e
M
i
n
i
m
u
m
C
o
s
t
M
a
x
i
m
u
m
F
l
o
w
A
l
g
o
r
i
t
h
m
Outline
B
a
c
k
g
r
o
u
n
d
Network Modeling
Barrier Coverage Optimization Problem
Optimal Barrier Coverage Algorithm
Time Complexity Analysis
Conclusion
Background
k-Barrier Coverage Problem
Sink Connected Barrier Coverage
k
-Barrier Coverage Problem
Degree (k) is the number of virtual detection
lines
How to select nodes to maximize degree (
k)
Given:
S
o
l
u
t
i
o
n
:
k
=
2
Sink Connected Barrier Coverage
Intruder
Boundary area
Sensor node for only
forwarding events
Sink Node
Sensor node (center dot) with a
sensing area for detecting and
forwarding events
Transmission Link
Detection Line
Outline
Background
N
e
t
w
o
r
k
M
o
d
e
l
i
n
g
Barrier Coverage Optimization Problem
Optimal Barrier Coverage Algorithm
Time Complexity Analysis
Conclusion
Network Model
Coverage Graph Gc
Transmission Graph Gt
Coverage Graph (Gc)
Ni and Nj have overlapped sensing coverage, then
Edge (Ni, Nj)
exists
Coverage Graph (Gc)
Detection Probability
depend on distance
P(d)=e
-
d
Detection Quality
W
o
r
s
t
C
a
s
e
o
f
P
P
w
(Si, Sj)=P(
Dist
/ 2 )
Distance (d)
Intruder Path in Middle
(Worst Case)
P(d)
Dist
Transmission Graph (Quality)
<Ni, Nj> =
node Ni can transmit data to Nj
Detection Quality
Transmission Graph (Gt)
Packet size
Bandwidth
Successful Ratio of Sending Packet
Successful Ratio of ACK Packet
Transmission Graph (Gt)
Outline
Background
Network Modeling
B
a
r
r
i
e
r
C
o
v
e
r
a
g
e
O
p
t
i
m
i
z
a
t
i
o
n
P
r
o
b
l
e
m
Optimal Barrier Coverage Algorithm
Time Complexity Analysis
Conclusion
Barrier Coverage Optimization Problem
(
(
k
k
,
,
p
p
,
,
t
t
)–Barrier Coverage Optimization Problem
)–Barrier Coverage Optimization Problem
How to select nodes from randomly deployed
sensor nodes to reach
three
goals :
Goal 1: Maximizing the degree
k
of barrier coverage
Goal 2: Maximizing the minimum probability
p
of
detecting intruders crossing the monitoring region
Goal 3: Minimizing the expected transmission time
t
to send data to the sink nodes.
Outline
Background
Barrier Coverage Optimization Problem
Optimal Barrier Coverage Algorithm
O
p
t
i
m
a
l
B
a
r
r
i
e
r
C
o
v
e
r
a
g
e
A
l
g
o
r
i
t
h
m
B
a
c
k
g
r
o
u
d
:
M
a
x
i
m
u
m
F
l
o
w
A
l
g
o
r
i
t
h
m
&
M
a
x
i
m
u
m
F
l
o
w
M
i
n
i
m
u
m
A
l
g
o
r
i
t
h
m
O
p
t
i
m
a
l
B
a
r
r
i
e
r
C
o
v
e
r
a
g
e
A
l
g
o
r
i
t
h
m
Time Complexity Analysis
Conclusion
Background:
Maximum Flow Algorithm
Maximum Flow (MaxFlow) ALG
Each edge is assigned
capacity constraint
To find some flows from
s
to
t
, such that:
Number of Flow is
Maximized
Flow on edge
capacity
M
a
x
i
m
u
m
F
l
o
w
P
l
a
n
=
2
F
l
o
w
s
Background:
Maximum Flow Algorithm
Maximum Flow (MaxFlow) ALG
To find MaxFlow plan from
s
to
t
, such that:
Number of Flow (
) is Maximized
2 Flows
Background:
Maximum Flow Minimum Cost Algorithm
Maximum Flow Minimum Cost
(MaxFlowMinCost) ALG
To find flows from
s
to
t
, such that:
$2
$1
$3
$1
$2
$1
$1
$1
Flow value
capacity
Background:
Maximum Flow Minimum Cost Algorithm
Maximum Flow Minimum Cost
(MaxFlowMinCost) ALG
To find flows from
s
to
t
, such that:
Number of Flow(
) is Maximized
Total Cost ($) is Minimized
$2
$1
$3
$1
$2
$1
$1
$1
Flow value
capacity
Optimal Barrier Coverage Algorithm
Basic Idea : 3 Phases
Phase1)To find a set of nodes (FP) with
maximized number of node-disjointed flows (
k
) in
Coverage Graph (Gc) by
MaxFlow ALG
MaxFlow ALG
Phase2)To refine FP such that minimum detection
probability (
p
) is maximized by
MaxFlow ALG
MaxFlow ALG
Phase3)To select some additional nodes for
connecting sink nodes with minimized Expected
Transmission Time (
t
) by
MaxFlowMinCost ALG
MaxFlowMinCost ALG
Phase1
To find a set of nodes (FP) with maximized
number of node-disjointed flows (
k
) in Coverage
Graph (Gc) by MaxFlow ALG
K=2
Phase 2
(Repeatedly remove edges such that minimum
detection probability (
p
) is Maximized without
loss number of flows in Phase 1
Quality of Barrier Coverage = 0.4
Quality of Barrier Coverage = 0.5
X
Phase 3
To select some additional nodes for connecting
sink nodes with minimized Expected
Transmission Time (t) by MaxFlowMinCost ALG
Expected Transmission Time = (5+4+4+2 + 2+5+5+3)/8
, which is Optimized
Optimal Barrier Coverage Algorithm
Step 1: Construct a coverage graph Gc
Each edge is associated with a weight
(
detection probability
)
For Multiple-in & Multiple-Out
Optimal Barrier Coverage Algorithm
S
t
e
p
2
:
E
x
e
c
u
t
e
t
o
N
N
o
o
d
d
e
e
-
-
D
D
i
i
s
s
j
j
o
o
i
i
n
n
t
t
T
T
r
r
a
a
n
n
s
s
f
f
o
o
r
r
m
m
a
a
t
t
i
i
o
o
n
n
t
r
a
n
s
f
e
r
G
c
i
n
t
o
t
h
e
n
e
w
g
r
a
p
h
G
c
*
N
N
o
o
d
d
e
e
-
-
D
D
i
i
s
s
j
j
o
o
i
i
n
n
t
t
T
T
r
r
a
a
n
n
s
s
f
f
o
o
r
r
m
m
a
a
t
t
i
i
o
o
n
n
Optimal Barrier Coverage Algorithm
Step 3:(To Find Maximum barrier
coverage)
Execute the
maximum flow algorithm
on Gc*
to decide the
maximum flow plan
FP
Optimal Barrier Coverage Algorithm
Step 4: Remove all edges with the minimal
probability without loss of Degree(k)
C
a
n
w
e
r
e
m
o
v
e
t
h
e
M
I
N
e
d
g
e
w
i
t
h
o
u
t
l
o
s
s
n
u
m
b
e
r
o
f
f
l
o
w
s
?
Yes, remove it and continue to test
No, quality is maximized
S
T
0.6
0.6
0.6
0.4
0.5
Optimal Barrier Coverage Algorithm
Step 4: Remove all edges with the minimal
probability without loss of Degree(k)
Can we remove the MIN edge without loss
number of flows?
Yes, remove it and continue to test
No, quality is maximized
S
T
0.6
0.6
0.6
0.4
0.5
Optimal Barrier Coverage Algorithm
Step 4: Remove all edges with the minimal
probability without loss of Degree(k)
Can we remove the MIN edge without loss
number of flows?
Yes, remove it and continue to test
N
o
,
q
u
a
l
i
t
y
i
s
m
a
x
i
m
i
z
e
d
S
T
0.6
0.6
0.6
0.5
A Barrier is constructed with MIN_Quality=0.5
Optimal Barrier Coverage Algorithm
Step 5:
Construct
a transmission graph
Add a
virtual source node S
and a
virtual target node T
Optimal Barrier Coverage Algorithm
Step 6:
For each node selected in Step. 4
, add an edge
from S, For each sink node, add edge to T
The ETT (Expected Transmission Time) is assigned on each
edge
Optimal Barrier Coverage Algorithm
Step 7: Execute Maximum Flow Minimum Cost Algorithm
Maximum Flow with Minimized Cost
Thus, a node set with
maximized degree (k),
maximized degree (k),
maximized minimum_detection_probability (p), and
maximized minimum_detection_probability (p), and
minimized average transmission time (t)
minimized average transmission time (t)
is determined
Time Complexity Analysis
Time complexity of Optimal Barrier Coverage
Algorithm is dominated by step 4
Try to
remove minimum weight edge
on coverage
graph and to execute
maximum flow algorithm
,
repeatedly (in step 4)
T
i
m
e
c
o
m
p
l
e
x
i
t
y
i
n
s
t
e
p
4
:
O
(
E
V
E
2
)
=
O
(
V
E
3
)
E
is the number of edges,
Maximum flow algorithm
needs O(
V
E
2
)
Conclusions
Barrier Coverage with Optimized Quality
Problem
is molded and solved in this paper
Aiming at this problem, we proposed a Optimal
Barrier Coverage Algorithm (OBCA)
The OBCA is time-efficient (polynomial time
complexity)
▆
Explore the optimization of barrier coverage quality in wireless sensor networks, focusing on maximizing intruder detection, detection probability, and minimizing data transmission time. The problem is modeled graphically and solved using the Minimum Cost Maximum Flow Algorithm, with a background in k-Barrier Coverage and sink-connected barrier coverage. The article delves into network modeling, algorithm complexity analysis, and provides a detailed conclusion on achieving optimal barrier coverage quality.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Barrier Coverage with Optimized Quality for Wireless Sensor Networks Yung-Liang Lai*, Jehn-Ruey Jiang National Central University Taoyuan Innovation Institute of Technology* Taiwan
Wireless Sensor based Barrier Coverage USA Wireless sensor
Barrier Coverage Optimization Problem How to construct a barrier coverage such that : Degree of Detecting intruders is Maximized , Probability of Detecting intruders is Maximized Data transmission time is Minimized?
Barrier Coverage Optimization Problem To optimize Quality of Barrier Coverage We define three Quality metrics detection degree, detection probability, expected transmission time We model the problem as a Graph Problem Solve it by the Minimum Cost Maximum Flow Algorithm
Outline Background Network Modeling Barrier Coverage Optimization Problem Optimal Barrier Coverage Algorithm Time Complexity Analysis Conclusion
Background k-Barrier Coverage Problem Sink Connected Barrier Coverage
k-Barrier Coverage Problem Degree (k) is the number of virtual detection lines How to select nodes to maximize degree (k) Solution: k=2 Given:
Sink Connected Barrier Coverage Sensor node (center dot) with a sensing area for detecting and forwarding events Sensor forwarding events Detection Line node for only Transmission Link Sink Node Boundary area Intruder
Outline Background Network Modeling Barrier Coverage Optimization Problem Optimal Barrier Coverage Algorithm Time Complexity Analysis Conclusion
Network Model Coverage Graph Gc Transmission Graph Gt
Coverage Graph (Gc) Ni and Nj have overlapped sensing coverage, then Edge (Ni, Nj) exists
Coverage Graph (Gc) Detection Probability depend on distance P(d)=e- d Distance (d) sensor target P(d) Dist Detection Quality Worst Case of P Pw(Si, Sj)=P( Dist / 2 ) S i S j Intruder Path in Middle (Worst Case)
Transmission Graph (Quality) <Ni, Nj> = node Ni can transmit data to Nj Detection Quality
Transmission Graph (Gt) Weight of edge on Gt Quality of Link: Packet size 1 S B ETT Ni,Nj = Bandwidth R Ni,Nj R Nj,Ni Successful Ratio of Sending Packet Successful Ratio of ACK Packet N3 N1 N2 N4 2 2 2 2 N14 K1 3 1 N11 N9 2 K2 N13 1 N10 3 2 N12 4 1 2 N5 N6 N8 N7
Transmission Graph (Gt) Quality of Path Set: Quality of Path Set: To measure the expected transmission time of a path set(PS) set(PS) path 1 |PS| h PSETT h N1 N2 2 ETT(PS) = N3 N4 2 2 2 N14 K1 3 1 N11 N9 2 K2 N13 1 N10 3 2 N12 4 1 2 N5 N6 N8 N7
Outline Background Network Modeling Barrier Coverage Optimization Problem Optimal Barrier Coverage Algorithm Time Complexity Analysis Conclusion
Barrier Coverage Optimization Problem (k,p,t) Barrier Coverage Optimization Problem How to select nodes from randomly deployed sensor nodes to reach three goals : Goal 1: Maximizing the degree k of barrier coverage Goal 2: Maximizing the minimum probability p of detecting intruders crossing the monitoring region Goal 3: Minimizing the expected transmission time t to send data to the sink nodes.
Outline Background Barrier Coverage Optimization Problem Optimal Barrier Coverage Algorithm Optimal Barrier Coverage Algorithm Backgroud: Maximum Flow Algorithm & Maximum Flow Minimum Algorithm Optimal Barrier Coverage Algorithm Time Complexity Analysis Conclusion
Background: Maximum Flow Algorithm Maximum Flow (MaxFlow) ALG Each edge is assigned capacity constraint To find some flows from s to t , such that: Number of Flow is Maximized Maximum Flow Plan = 2 Flows capacity Flow on edge
Background: Maximum Flow Algorithm Maximum Flow (MaxFlow) ALG To find MaxFlow plan from s to t , such that: Number of Flow ( ) is Maximized 2 Flows
Background: Maximum Flow Minimum Cost Algorithm Maximum Flow Minimum Cost (MaxFlowMinCost) ALG To find flows from s to t , such that: $1 $1 $2 $3 $1 $1 $1 $2 capacity Flow value
Background: Maximum Flow Minimum Cost Algorithm Maximum Flow Minimum Cost (MaxFlowMinCost) ALG To find flows from s to t , such that: Number of Flow( ) is Maximized Total Cost ($) is Minimized $1 $1 $2 $3 $1 $1 $1 $2 capacity Flow value
Optimal Barrier Coverage Algorithm Basic Idea : 3 Phases Phase1)To find a set of nodes (FP) with maximized number of node-disjointed flows (k) in Coverage Graph (Gc) by MaxFlow ALG Phase2)To refine FP such that minimum detection probability (p) is maximized by MaxFlow ALG Phase3)To select some additional nodes for connecting sink nodes with minimized Expected Transmission Time (t) by MaxFlowMinCost ALG
Phase1 To find a set of nodes (FP) with maximized number of node-disjointed flows (k) in Coverage Graph (Gc) by MaxFlow ALG K=2
Phase 2 (Repeatedly remove edges such that minimum detection probability (p) is Maximized without loss number of flows in Phase 1 Quality of Barrier Coverage = 0.4 Quality of Barrier Coverage = 0.5 N2 N2 N1 N3 N1 N3 N4 N4 0.7 0.6 0.7 0.6 0.6 0.6 X N9 N9 N5 0.6 N5 0.6 0.5 0.5 N6 N6 N7 N7 N8 N8 0.6 0.6 0.4 0.6 0.6 Minimum detection probability =0.5 Minimum detection probability =0.4
Phase 3 To select some additional nodes for connecting sink nodes with minimized Expected Transmission Time (t) by MaxFlowMinCost ALG (5) (4) (2) (4) N3 N1 N2 N4 N3 N1 N2 N4 2 2 2 2 2 2 2 2 N14 K1 3 1 K1 3 1 N11 2 K2 N11 N9 2 K2 N9 1 1 3 2 3 2 N13 N13 N12 N12 N10 N10 4 4 1 1 2 2 N5 N6 N5 (2) N8 N7 N8 N6 N7 (5) (5) (3) Expected Transmission Time = (5+4+4+2 + 2+5+5+3)/8 , which is Optimized
Optimal Barrier Coverage Algorithm Step 1: Construct a coverage graph Gc Each edge is associated with a weight (detection probability) N2 N1 N3 N4 0.7 0.6 0.6 N9 0.5 N5 0.5 N6 N7 N8 0.6 0.4 0.5
Optimal Barrier Coverage Algorithm Step 2: Execute to Node-Disjoint Transformation transfer Gc into the new graph Gc* For Multiple-in & Multiple-Out Node-Disjoint Transformation
Optimal Barrier Coverage Algorithm Step 3:(To Find Maximum barrier coverage) Execute the maximum flow algorithm on Gc* to decide the maximum flow plan FP N2 N1 0.6 N3 N4 0.7 0.6 T S N9 0.5 N5 0.5 N6 N7 N8 0.6 0.4 0.5
Optimal Barrier Coverage Algorithm Step 4: Remove all edges with the minimal probability without loss of Degree(k) Can we remove the MIN edge without loss number of flows? Yes, remove it and continue to test No, quality is maximized S T 0.6 0.5 0.6 0.6 0.4
Optimal Barrier Coverage Algorithm Step 4: Remove all edges with the minimal probability without loss of Degree(k) Can we remove the MIN edge without loss number of flows? Yes, remove it and continue to test No, quality is maximized S T 0.6 0.5 0.6 0.6 0.4
Optimal Barrier Coverage Algorithm Step 4: Remove all edges with the minimal probability without loss of Degree(k) Can we remove the MIN edge without loss number of flows? Yes, remove it and continue to test No, quality is maximized S T 0.6 0.5 0.6 0.6 A Barrier is constructed with MIN_Quality=0.5
Optimal Barrier Coverage Algorithm Step 5: Construct a transmission graph Add a virtual source node S and a virtual target node T S T
Optimal Barrier Coverage Algorithm Step 6: For each node selected in Step. 4, add an edge from S, For each sink node, add edge to T The ETT (Expected Transmission Time) is assigned on each edge S T
Optimal Barrier Coverage Algorithm Step 7: Execute Maximum Flow Minimum Cost Algorithm Maximum Flow with Minimized Cost S T Thus, a node set with maximized degree (k), maximized minimum_detection_probability (p), and minimized average transmission time (t) is determined
Time Complexity Analysis Time complexity of Optimal Barrier Coverage Algorithm is dominated by step 4 Try to remove minimum weight edge on coverage graph and to execute maximum flow algorithm, repeatedly (in step 4) Time complexity in step 4: O(E V E2)= O(V E3) E is the number of edges, Maximum flow algorithm needs O(V E2)
Conclusions Barrier Coverage with Optimized Quality Problem is molded and solved in this paper Aiming at this problem, we proposed a Optimal Barrier Coverage Algorithm (OBCA) The OBCA is time-efficient (polynomial time complexity)
