Optimized Wireless Broadcasting Efficiency
W
i
r
e
l
e
s
s
B
r
o
a
d
c
a
s
t
i
n
g
w
i
t
h
O
p
t
i
m
i
z
e
d
T
r
a
n
s
m
i
s
s
i
o
n
E
f
f
i
c
i
e
n
c
y
Jehn-Ruey Jiang
and Yung-Liang Lai
National Central University,
Taiwan
Wireless Broadcasting
•
Broadcasting is one of the most fundament
operations in wireless networks
•
Each node has one antenna of which wireless
transmission range is modeled as
a circle of fixed
radius R
•
One node, called the
source node
, would like to
disseminate a packet to all network nodes
•
Nodes receiving the packet will intelligently decide
whether to rebroadcast it or not
R
A Simple Scheme -- Flooding
•
Flooding is a simple method to realize
broadcasting
•
But it incurs a large number of
redundant
retransmissions
–
leading to
low
transmission efficiency
–
Resulting in the well-known “
Broadcasting Storm
Problem
”
Proposed Scheme
•
In this paper, an optimized broadcast protocol
(OBP) is proposed
–
to optimized the
transmission efficiency
of wireless
broadcasting
0.55
0.61
–
while maintaining as high as possible
reachability
100%
Outline
•
Transmission Efficiency of Broadcasting
Related Work
–
Optimal Flooding Protocol (OFP)
–
Broadcast Protocol for Sensor networks (BPS)
–
Hexagon Flooding Protocol (HFP)
•
Our solution
–
Optimized Broadcasting Protocol (OBP)
•
Performance Analysis and Comparison
•
Conclusion
Transmission efficiency of Broadcasting
•
Transmission efficiency(TE) is the ratio
–
TE=
Effective Area Covered
/
Total Transmission Area
=
|C
A
C
B
|
/
( |C
A
|+|C
B
|)
•
For instance,
Node A
broadcasts one packet and then
Node B
rebroadcasts one packet,
•
Effective area covered by A and B is |C
A
C
B
|
•
Total Communication Area is | C
A
| + | C
B
|
Node A
Node B
Node A
Node B
|C
A
|
|C
B
|
Transmission efficiency :
Upper bound
•
Transmission efficiency(TE) is the ratio
–
TE=
Effective Area Covered
/ Total Transmission Area
=|C
A
C
B
|/ ( |C
A
|+|C
B
|)
•
When
Distance between A and B = Transmission radius R
TE
reaches the
theoretical upper bound
0.61
Node A
Existing Broadcasting Protocol :OFP
•
Geometry-based protocols
–
Assume that
each node is aware of its own
location
to make retransmission decisions
•
Optimal Flooding Protocol (OFP)
–
With the highest transmission efficiency among all
existed Geometry-based protocols, so far
–
Proposed by
Paruchuri et al., in IEEE WCNC 2002
–
Has transmission efficiency of 0.41
–
About 67% of the
theoretical upper bound
Optimal Flooding Protocol (OFP)
•
Idea
–
based on a regular hexagonal partition of the
network
–
only the nodes nearest to hexagon vertexes
need to rebroadcast
s
S: Source node, the node to broadcast a packet throughout the network
Do nothing
The nearest one has to rebroadcast
R
Optimal Flooding Protocol (OFP)
•
Steps
Step.1
Step.2
Step.3
(1)
(6)
(6)
Optimal Flooding Protocol (OFP)
•
Steps
Total Retransmission times =(1)+(6)+(6)+(12)=
( 25 ) times
Result: Network Area is covered so every node receive the packet
CAN WE FURTHER IMPROVE
THE TRANSMISSION EFFICIENCY?
Transmission
Efficiency
?
OFP, 0.41
Upper Bound 0.61
Our proposed protocol: OBP
•
Basic Idea of OBP (Optimized Broadcast Protocol)
–
To activate nodes to rebroadcast Ring by Ring
•
Nodes on centers of hexagons
•
Nodes on vertexes of hexagons
Step.1 (1)
Step.2 (3)
Step.3 (6)
•
Total Retransmission times of OBP =(1)+(3)+(6)=
( 10 ) times
•
25 (OFP) vs 10 (OBP)
OBP : Activation Sequence
C
0,0
C
0,0
V
1,0
V
1,1
V
1,2
C
1,0
C
1,1
C
1,2
C
1,3
C
1,4
1.node S broadcasts a packet
2. To activate three vertexes node {V1,0
, V
1,1
, V
1,2
}
3. Each
Vertex Node
activates
Two Center Nodes
C
1,5
C
0,0
V
1,1
V
1,2
C
1,0
C
1,1
C
1,2
C
1,3
C
1,4
C
1,5
V
2,0
V
2,1
V
2,2
V
2,3
V
2,4
V
2,5
4. Each
Center Node
activates
One Vertex Node
… Finally, all centers of hexagons will activated
to rebroadcast
OBP : Basic Structure
•
By the way, all centers of hexagons will activated to
rebroadcast
ring by ring
side
length (R)
C
2,6
S
C
1,2
C
1,1
C
1,0
C
1,4
C
2,5
C
2,4
C
1,3
C
2,3
C
2,2
C
2,1
C
2,11
C
2,10
C
2,8
C
2,9
C
2,7
V
1,0
V
2,2
V
2,1
C
1,5
V
2,4
V
2,5
V
1,1
V
1,2
C
0,0
C
2,0
V
2,0
V
2,3
Horizontal axis
C
3
,0
C
3
,
1
C
3
,
2
C
3
,
3
C
3
,
4
C
3
,
5
C
3
,
6
C
3
,
7
C
3
,
8
C
3
,
9
C
3
,
10
C
3
,
11
C
3
,
12
C
3
,
13
C
3
,
14
C
3
,
15
C
3
,
16
C
3
,
17
V
3
,0
V
3
,
1
V
3
,
2
V
3
,
3
V
3
,
4
V
3
,
5
V
3
,
6
V
3
,
7
V
3
,
8
In each ring, index started
along the Horizontal axis
Ring 1
Ring 2
Ring 3
OBP: Two Key Components
•
Two key components of OBP
–
How to calculate location of C
i,j
•
Position of {C
k,
i
} =
Geometric Mapping
G(C
k,i
)
s
G(C
1,0
)
C
1,0
s
C
k,i
C
k+1,w
C
k+1,w+1
H
o
w
t
o
f
i
n
d
t
w
o
n
e
x
t
-
l
e
v
e
l
n
e
i
g
h
b
o
r
i
n
g
c
e
n
t
e
r
n
o
d
e
s
C
k
+
1
,
w
C
k
+
1
,
w
+
1
o
f
C
k
,
i
Activation Target Mapping
T(C
k,i
)
Geometric Mapping
.
Activation Target Mapping
.
OBP : Algorithm
•
The step for the source node S to broadcast a packet
P
:
–
S1. S sends the packet P(LS, F) with F={LV1,0
, LV
1,1
, LV
1,2
}.
For example, LV
1,0
is used to indicate the location of vertex node V
1,0
for the node which is nearest to this location to be activated
OBP : Algorithm
•
For other node Y receiving P(LS, F)
–
S1. If Y is not closest to the target locations, Y stops
–
S2. If Y is a vertex node, it will activate two center nodes
–
S3. If Y is a center node, it will activate one vertex node
(when required)
V
1,0
V
1,1
V
1,2
V
2,0
C
1,0
C
1,1
C
1,0
Each vertex(or center) node can know whether it is nearest the location by
exchange location information (like HELLO message) in the network initial stage
OBP : Details
•
The step for the source node S to broadcast a packet
P
:
–
S1. S sends the packet P(LS, F) with F={LV1,0
, LV
1,1
, LV
1,2
}.
•
Steps for other node Y receiving P(LS, F)
:
–
S1. If Y receives P for the first time, it registers P.
Otherwise, it drops P and stops
–
S2. If Y is not a node nearest to a location in F, it stops
–
S3. If Y is nearest to a center node associated with C
k,i
of
a location in F and T(C
k,i
)
, then Y sends P(LS, F
) and
stops, where F
={LVk,i
} if
T(C
k,i
)
and
F
=
if T(C
k,i
)=
.
–
S4. If Y is nearest to a vertex node associated with V
k
,
i
of
a location in F, X sends P(LS, F
) and stops. Indeed, Y can
calculate T(C
k
1
,i
)= {Ck,w
, C
k,w+
1
} based on indexes
k
,
i
and
then set F
={LCk,w
, LC
k,w+
1
}
Based on Geometric Mapping G(C
k,i
), Activation Target Mapping
T(C
k,i
) , OBP can be designed to broadcast packet into the network
Performance Analysis of OBP
•
Transmission efficiency
η:
•
OBP approximates the theoretical upper
bound of transmission efficiency by a
ratio of
η
OBP
/
η
U
90%
OBP IS WITH HIGHER TRANSMISSION
EFFICIENCY
Transmission
Efficiency
OFP, 0.41
Upper Bound 0.61
OFP, 0.55
In IEEE WCNC 2002
2009
Performance Comparisons
•
Required Transmissions for OBP and OFP
Reachability of OFP and OBP for
various node densities
•
We also observe OBP may not have 100%
reachability when the node density is not
sufficiently high
Conclusion
•
We have proposed an optimized broadcast protocol
(OBP) for wireless networks
•
The Key idea of OBP is to select nodes based on a
hexagon ring pattern to minimize the number of
retransmissions for better transmission efficiency
•
Analysis result shows that OBP’s transmission
efficiency is over 90% of the theoretical upper bound
•
Currently, we are studying broadcasting in 3D wireless
network
Thanks for your listening
Thanks for your listening
This research focuses on optimizing transmission efficiency in wireless broadcasting, proposing an Optimized Broadcast Protocol to enhance reachability while reducing redundant retransmissions. It discusses the challenges of traditional methods like flooding and introduces new strategies to improve transmission efficiency. The study analyzes various protocols and presents a performance comparison, highlighting the significance of optimizing broadcasting in wireless networks for enhanced communication.
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
Wireless Broadcasting with Optimized Transmission Efficiency Jehn-Ruey Jiang and Yung-Liang Lai National Central University, Taiwan
Wireless Broadcasting R Broadcasting is one of the most fundament operations in wireless networks Each node has one antenna of which wireless transmission range is modeled as a circle of fixed radius R One node, called the source node, would like to disseminate a packet to all network nodes Nodes receiving the packet will intelligently decide whether to rebroadcast it or not
Retransmission of some extra coverage Totally redundant retransmission
A Simple Scheme -- Flooding Flooding is a simple method to realize broadcasting But it incurs a large number of redundant retransmissions leading to low transmission efficiency Resulting in the well-known Broadcasting Storm Problem
Proposed Scheme In this paper, an optimized broadcast protocol (OBP) is proposed to optimized the transmission efficiency of wireless broadcasting 0.55 0.61 while maintaining as high as possible reachability 100%
Outline Transmission Efficiency of Broadcasting Related Work Optimal Flooding Protocol (OFP) Broadcast Protocol for Sensor networks (BPS) Hexagon Flooding Protocol (HFP) Our solution Optimized Broadcasting Protocol (OBP) Performance Analysis and Comparison Conclusion
Transmission efficiency of Broadcasting Transmission efficiency(TE) is the ratio TE= Effective Area Covered / Total Transmission Area =|CA CB|/ ( |CA|+|CB|) Node A Node B For instance, Node A broadcasts one packet and then Node B rebroadcasts one packet, Effective area covered by A and B is |CA CB| Total Communication Area is | CA| + | CB| |CB| |CA| Node A Node B
Transmission efficiency : Upper bound Transmission efficiency(TE) is the ratio TE= Effective Area Covered / Total Transmission Area =|CA CB|/ ( |CA|+|CB|) When Distance between A and B = Transmission radius R TE reaches the theoretical upper bound 0.61 R Node B Node A
Existing Broadcasting Protocol :OFP Geometry-based protocols Assume that each node is aware of its own location to make retransmission decisions Optimal Flooding Protocol (OFP) With the highest transmission efficiency among all existed Geometry-based protocols, so far Proposed by Paruchuri et al., in IEEE WCNC 2002 Has transmission efficiency of 0.41 About 67% of the theoretical upper bound
Optimal Flooding Protocol (OFP) Idea based on a regular hexagonal partition of the network only the nodes nearest to hexagon vertexes need to rebroadcast The nearest one has to rebroadcast Do nothing R s S: Source node, the node to broadcast a packet throughout the network
Optimal Flooding Protocol (OFP) Steps s s s Step.1 (1) Step.2 (6) s Step.3 (6)
Optimal Flooding Protocol (OFP) Steps Result: Network Area is covered so every node receive the packet s s Step.4 (12) Total Retransmission times =(1)+(6)+(6)+(12)= ( 25 ) times
CAN WE FURTHER IMPROVE THE TRANSMISSION EFFICIENCY? Transmission Efficiency ? OFP, 0.41 Upper Bound 0.61
Our proposed protocol: OBP Basic Idea of OBP (Optimized Broadcast Protocol) To activate nodes to rebroadcast Ring by Ring Nodes on centers of hexagons Nodes on vertexes of hexagons s s s Step.1 (1) Step.2 (3) s Step.3 (6) Total Retransmission times of OBP =(1)+(3)+(6)= ( 10 ) times 25 (OFP) vs 10 (OBP)
OBP : Activation Sequence 1.node S broadcasts a packet 2. To activate three vertexes node {V1,0, V1,1, V1,2} V1,0 V1,1 C0,0 C0,0 V2,2 V2,1 V1,2 C1,2 C1,1 V2,0 V1,1 3. Each Vertex Node activates Two Center Nodes C0,0 V2,3 C1,3 C1,0 C1,1 C1,2 V1,2 V1,1 C1,4 V1,0 C1,5 C0,0 C1,0 V2,5 C1,3 V2,4 V1,2 4. Each Center Node activates One Vertex Node C1,4 C1,5 Finally, all centers of hexagons will activated to rebroadcast
OBP : Basic Structure By the way, all centers of hexagons will activated to rebroadcast ring by ring C3,6 C3,4 C3,5 C3,3 V3,3 V3,2 V3,1 C3,7 C2,4 C2,2 C3,2 In each ring, index started along the Horizontal axis C2,3 V2,1 V2,2 C3,8 C2,5 C3,1 C2,1 C1,2 C1,1 V3,4 V1,1 V3,0 V2,0 V1,0 C3,0 C0,0 V2,3 S C2,0 C3,9 C1,0 C2,6 C1,3 Horizontal axis V1,2 C3,10 C1,5 C1,4 V3,5 C2,11 C3,17 C2,7 V2,5 V3,8 V2,4 C2,8 C2,10 C3,11 C3,16 Ring 1 C2,9 V3,6 V3,7 side length (R) Ring 2 C3,12 C3,14 C3,15 C3,13 Ring 3
OBP: Two Key Components Two key components of OBP How to calculate location of Ci,j Position of {Ck, i} = Geometric Mapping G(Ck,i) G(C1,0) s C1,0 How to find two next-level neighboring center nodes Ck+1,w Ck+1,w+1of Ck,i Ck+1,w+1 Activation Target Mapping T(Ck,i) s Ck,i Ck+1,w
. Geometric Mapping
. Activation Target Mapping Sector 1 C3,5 C3,4 C3,6 C3,3 Sector 2 Sector 0 C2,2 C3,7 C2,4 C3,2 C2,3 C3,8 C1,2 C1,1 C2,1 C3,1 C2,5 C0,0 C3,9 A0 A3 S C2,6 C1,0 C1,5 C2,0 C3,0 C1,3 C2,11 C1,4 C3,10 C3,17 C2,7 Sector 3 C2,8 C3,11 C2,9 C2,10 Sector 5 C3,16 C3,15 C3,12 C3,13 C3,14 A4 A5 Sector 4
OBP : Algorithm The step for the source node S to broadcast a packet P: S1. S sends the packet P(LS, F) with F={LV1,0, LV1,1, LV1,2}. V1,1 V1,0 C0,0 V1,2 For example, LV1,0is used to indicate the location of vertex node V1,0 for the node which is nearest to this location to be activated
OBP : Algorithm For other node Y receiving P(LS, F) S1. If Y is not closest to the target locations, Y stops S2. If Y is a vertex node, it will activate two center nodes S3. If Y is a center node, it will activate one vertex node (when required) C1,1 V2,0 V1,1 V1,0 C1,0 C1,0 V1,2 Each vertex(or center) node can know whether it is nearest the location by exchange location information (like HELLO message) in the network initial stage
OBP : Details The step for the source node S to broadcast a packet P: S1. S sends the packet P(LS, F) with F={LV1,0, LV1,1, LV1,2}. Steps for other node Y receiving P(LS, F): S1. If Y receives P for the first time, it registers P. Otherwise, it drops P and stops S2. If Y is not a node nearest to a location in F, it stops S3. If Y is nearest to a center node associated with Ck,iof a location in F and T(Ck,i) , then Y sends P(LS, F ) and stops, where F ={LVk,i} if T(Ck,i) and F = if T(Ck,i)= . S4. If Y is nearest to a vertex node associated with Vk,iof a location in F, X sends P(LS, F ) and stops. Indeed, Y can calculate T(Ck 1,i)= {Ck,w, Ck,w+1} based on indexes k, i and then set F ={LCk,w, LCk,w+1} Based on Geometric Mapping G(Ck,i), Activation Target Mapping T(Ck,i) , OBP can be designed to broadcast packet into the network
Performance Analysis of OBP Transmission efficiency : OBP approximates the theoretical upper bound of transmission efficiency by a ratio of OBP/ U 90%
OBP IS WITH HIGHER TRANSMISSION EFFICIENCY In IEEE WCNC 2002 2009 Transmission Efficiency OFP, 0.55 OFP, 0.41 Upper Bound 0.61
Performance Comparisons Required Transmissions for OBP and OFP 300 No. of Transmissions 151 OFP OBP 250 200 97 150 55 91 100 55 25 50 28 10 0 Level of Hexagon Rings 2 3 4 5
Reachability of OFP and OBP for various node densities We also observe OBP may not have 100% reachability when the node density is not sufficiently high 1 0.98 0.96 0.94 Reachability 0.92 0.9 OBP 0.88 0.86 OFP 0.84 0.82 0.8 Densitity 10 12 14 16 18 20
Conclusion We have proposed an optimized broadcast protocol (OBP) for wireless networks The Key idea of OBP is to select nodes based on a hexagon ring pattern to minimize the number of retransmissions for better transmission efficiency Analysis result shows that OBP s transmission efficiency is over 90% of the theoretical upper bound Currently, we are studying broadcasting in 3D wireless network Thanks for your listening
