A routing algorithm using the gateway location via broadcasting the hello packet in a hybrid wireless mesh network
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
A ROUTING ALGORITHM USING THE GATEWAY LOCATION VIA BROADCASTING
THE HELLO PACKET IN A HYBRID WIRELESS MESH NETWORK
THUẬT TOÁN ĐỊNH TUYẾN SỬ DỤNG VỊ TRÍ GATEWAY
QUA QUẢNG BÁ GÓI TINHELLO TRONG MẠNG HÌNH LƯỚI KHÔNG DÂY LAI
Lê Anh Ngọc
Trường Đại học Điện lực
Ngày nhận bài: 23/09/2020, Ngày chấp nhận đăng: 16/03/2021, Phản biện: TS. Ngô Hải Anh
Abstract:
In a hybrid wireless mesh network (HWMN), traffic is mainly concentrated to and from the gateways
due to the need for mobile devices to exploit services on the Internet. Therefore, routing algorithms
in the HWMN network requires consideration of this traffic characteristic. In this paper, we have
proposed a routing protocol based on the gateway location via hello messages to limit the broadcast
area of the routing request in the HWMN network. The simulation results show the efficiency of the
proposed protocol through the analysis of routing overhead and network throughput.
Keywords:
HWMN, AODV, routing, gateway, ad-hoc.
Tóm tắt:
Trong mạng hình lưới không dây lai (HWMN), lưu lượng chủ yếu tập trung đi và đến các gateway do
nhu cầu của các thiết bị di động là khai thác các dịch vụ trên Internet. Do đó, việc xác định tuyến
trong mạng HWMN đòi hỏi phải chú ý đến đặc tính lưu lượng này. Trong bài báo này, chúng tôi đã
đề xuất một giao thức định tuyến dựa trên vị trí gateway nhờ các thông báo hello nhằm hạn chế
vùng quảng bá của yêu cầu định tuyến trong mạng HWMN. Kết quả mô phỏng cho thấy hiệu quả
của giao thức đề xuất qua phân tích dư thừa các gói tin định tuyến và thông lượng mạng.
Từ khóa:
HWMN, AODV, routing, gateway, ad-hoc
connectivity to other networks, such as
the Internet and other networks (level 1).
1. INTRODUCTION
A Hybrid Wireless Network (HWMN) is Besides, mobile clients can act as a
dynamic extension of the static
Networks [1, 2]. As shown in Fig 1, a infrastructure part of the network, by
implementing routing and packet
that form the backbone of the network forwarding functionalities (level 3). The
hybrid mesh architecture is the most
gateway functionality (IGW) and provide applicable because mesh clients can not
the most generic type of Wireless Mesh
HWMN consists of static mesh routers
(level 2). Some mesh routers can include
Số 25
85
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
only directly communicate with other HWMN.
mesh clients, but also access the Internet
The remainder of the paper is organized
service through mesh routers. In this
paper, we focus on this architecture,
especially on mesh clients accessing
Internet service through gateway nodes
(see Fig. 1).
as follows: Section 2 discusses relevant
related works. The proposed protocol is
described in Section 3. Section 4 provides
details of the simulation environment and
simulation results. Some conclusions are
given in Section 5.
Although hybrid wireless mesh networks
are a particular type of mobile ad hoc
network (MANET) [2, 3], there are also
significant differences between hybrid
wireless mesh networks and general
MANETs. In hybrid wireless mesh
networks, the mesh routers are relatively
powerful and static nodes, which have
access to a power mains system or are
equipped with high capacity batteries.
Mesh routers are typically equipped
with multiple radio interfaces assigned
to non-overlapping channels, thereby
significantly increasing the transmission
capacity of wireless mesh networks [4]. In
contrast to the mesh routers, the mesh
clients are relatively constrained mobile
client devices, such as a smartphone,
laptop, or PDA, with just a single radio,
high mobility, and limited battery power.
Furthermore, in hybrid wireless mesh
networks, most of the traffic is directed
to/from a gateway, as the mesh clients
generally access services on the Internet
or other networks. Consequently, an
efficient routing strategy needs to take
into account the traffic pattern in hybrid
wireless mesh networks. Accordingly, this
paper proposes an improvement of
AODV routing protocol based on gateway
discovery using HELLO packet and
Internet
Level 1
gateways
IGW
IGW
IGW
Level 2
backbone of mesh
routers
Mesh router
Mesh client
Level 3
mesh clients
Mesh client
Mesh clients connected in
multi-hop
Fig. 1. A Hybrid Wireless Network (HWMN)
2. RELATED WORKS
Many routing protocols have already been
proposed for ad hoc networks and can be
applied for HWMN. They generally can
be categorized as reactive [5, 6] or
proactive [7] based on the time of the
route availability to the source node when
a node has a data packet to send. In
proactive routing protocols, the source
node knows the route before it has any
data packets to send. Routes to the
destination nodes are semi-permanently
maintained in a routing table based on the
periodic exchange of routing tables
between neighboring nodes. Destination
Sequence Distance Vector (DSDV) [7] is
restricting the broadcast area of route commonly used as a proactive routing
requests to reduce routing overhead in protocol. In reactive routing protocols, the
86
Số 25
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
routes are established on-demand. When executing the AODV can use link layer
the source node has data to send, it feedback or periodic HELLO packets to
initiates a route discovery procedure, and detect link breakages with nodes that it
once the node acquires the desired routing considers as its immediate neighbors.
information from the route discovery When a link break is detected for a next
procedure, it forwards the data using the hop of an active route, a Route Error
acquired route. Dynamic Source Routing (RERR) packet is sent to the active
(DSR) [5] and Ad-hoc On-demand Dis- neighbors using that particular route. The
tance Vector (AODV) [6] are examples of proactive and reactive approaches have
reactive routing protocols. In AODV [6], already been merged in hybrid routing
when
a
source node intends to protocols that aim to combine the
communicate with a destination node advantages of both approaches. For
whose route is unknown, it broadcasts a example, the Zone Routing Protocol
Route Request (RREQ) packet. Each (ZRP) [8] is a hybrid routing protocol
RREQ contains an ID, source address, based on the notion of a zone, where a
destination address, sequence number proactive protocol is used among the
together with a hop count and control nodes of a particular zone, while a
flags. If the RREQ recipients have not reactive protocol is used to reach a node
seen the source address and RREQ ID outside that zone. However, this routing
pair or do not have a fresher (with a protocol was designed for homogeneous
higher sequence number) route to the ad hoc networks, and is unable to
destination, they rebroadcast the same differentiate between the different types
packet after incrementing the hop-count. of node in hybrid wireless mesh networks.
Intermediate nodes also create and
preserve a Reverse Route to the source
node for a certain interval of time. When
the RREQ reaches the destination node or
any node that has a fresh route to the
destination, a Route Reply (RREP) packet
Ad hoc routing protocols are promising
candidates for hybrid wireless mesh net-
works, due to their capability to deal with
dynamic environments. However, the
direct application of routing techniques
is generated and unicast back to the for ad hoc networks to hybrid wireless
source of the RREQ. Each RREP contains mesh networks results in inferior
the destination sequence number, source performance, as the characteristics of
mesh networks are not utilized. In hybrid
wireless mesh networks, most of the
traffic is directed towards a gateway and
thus all the source nodes require a route to
a gateway node for data delivery beyond
the mesh. Reactive routing protocols [5,
6] generate multiple requests towards a
gateway, they increase the traffic and
and destination node addresses, route
lifetime, and hop count and control flags.
Each intermediary node that receives the
RREP then increments the hop-count,
establishes a Forward Route to the source
of the packet, and transmits the packet via
the Reverse Route. To preserve the
connectivity information, each node
Số 25
87
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
overhead near the gateway. Moreover, in performance.
the case of a large network, the time
In this section, we introduce IMP-AODV
required to acquire a route towards a
gateway becomes significant, thereby
increasing the overall delay. Conversely,
in the case of proactive routing protocols
[7], each node periodically sends updates
of its routing table to maintain correct
route information to all destinations,
which results in a large overhead. In
particular, the high mobility of the mesh
clients degrades the performance of
routing protocol for HWMN, which is an
improvement of AODV routing protocol
based on gateway discovery using hello
packet and restricting the broadcast area
of route requests to reduce routing
overhead in HWMN.
3.1. Gateway discovery
The AODV uses periodical HELLO
proactive routing, as the routing table messages to indicate the presence of a
becomes quickly outdated and requires an
enormous overhead to keep it up to date.
In addition, since ad hoc routing
protocols were originally designed for
homogeneous ad hoc networks, consisting
of resource-constrained mobile devices,
their performance is not optimal in hybrid
wireless mesh networks, as they are
unable to take full advantage of the mesh
routers in hybrid wireless mesh networks.
mesh node to its neighbors. We utilized it
for gateway discovery without any
protocol overhead. HELLO message is
modified with I-flag to indicate that these
packets were originated by a gateway
[9,10]. It also contains the gateway’s
address and the distance value of the
broadcasted mesh node.
Each mesh node maintains a distance
value (HC) to indicate the distance
(number of hops) to a gateway, which is
initially set to be infinite. Only a
gateway’s HC value is set to 0. Mesh
nodes periodically send HELLO message
3. PROPOSED ROUTING PROTOCOL
FOR HYBRID WIRELESS MESH
NETWORKS
As mentioned in the previous section, the
large amount of overhead needed in
broadcasting RREQ messages is the main
drawback of the AODV in high load net-
works such as HWMN. The overhead
mostly consists of route request messages.
In the route discovery process, each
intermediate node can broadcast packets
to all neighbors whereas most traffic is
destined from mesh clients to the gateway
in HWMN. These increase the number of
redundant messages transmitted in the
network and reduce the network
to
update
neighbor
information,
meanwhile, gateway node broadcasts
HELLO with gateway information
(I-Flag) and distance value (HC+1) (Fig.
2a). When mesh nodes within one-hop
away from the gateway receive a HELLO
message with I-flag and smaller distance
value (HCHELLO), they update gateway
information and set their HC value with
the HC value in the HELLO message.
Mesh nodes later broadcast their HELLO
message with I-flag and their new HC
88
Số 25
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
value (Fig 2b). Thereafter, the two-hop When mesh node desires a route to a
away nodes receive these HELLO gateway for which it does not have a
packets, thus they learn that they are two-
hop away from the gateway. In this
manner, every node discovers the
gateway’s information and learns their
distance (HC) to the gateway. Imp-AODV
also used sequence number in HELLO
packet to determine the timeliness of each
packet.
route, it broadcasts the RREQ with an HC
set to its HC value as shown in Fig. 3(a).
When a mesh node receives a RREQ
message with a smaller distance value
(HC), it discards RREQ message.
Otherwise, it replaces the HC value on the
RREQ with its HC value and then re-
broadcasts the RREQ to all neighbors in
the same manner in AODV (Fig. 3b).
Begin
Begin
Begin
Begin
Node i receives
HELLO packet
Generate the
HELLO packet
Node i receives
RREQ packet
Generate RREQ
HCRREQ=HCS
No
No
No
Packet has
Gateway ID
Node i has
Gateway ID
Yes
No
HCRREQ<HCi
Yes
Yes
HCRREQ=HCi
Broadcast RREQ
End
HCHELLO=HCi+1
Discard
RREQ packet
HCHELLO<HCi
GatewayIDHELLO=GatewayIDi
Forward RREQ
packet
Yes
HCi=HCHELLO
Broadcast
GatewayIDi=GatewayIDHELLO
HELLO packet
End
Update the neighbor
information
End
(a) Source mesh node; (b) Intermediate mesh nodes
End
Fig 3. Route Request Forwarding
(a) Sending Hello
with I-Flag
(b) Receiving Hello
with I-Flag
When a mesh node receives the RREQ, it
establishes a reverse route to the RREQ
source in its routing table, and it either
replies to the RREQ if it has an entry for
the gateway or it forwards the RREQ.
Finally, the RREQ reaches the gateway
and it unicasts a RREP. The node
receiving a RREP sets up a forward route
to the gateway and desirable routes can be
discovered.
Fig. 2. Gateway discovery algorithm
3.2. Route discovery
The route discovery in IMP-AODV is
fundamentally similar with AODV. It
only improves RREQ forwarding process
such that reduces the scope of
broadcasting to the gateway. IMP-AODV
protocol adds distance value (HC field) to
the Route Request (RREQ) message to
Route maintenance is similar to that of the
indicate the distance to the gateway. AODV. An existing routing entry may be
Số 25
89
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
invalidated if it is not used within a
specified time interval, or if the next hop
node is no longer reachable. In these
cases, an invalidation notice is propagated
to the neighbors that have used this node
as the next hop. Each time a route is used
to forward a data packet, its route
expiration time is updated. When a node
detects that a route to a neighbor is no
longer valid, it removes the invalid entry
and sends a route error message to the
neighbors that are using the route. Nodes
that receive error messages will repeat
this process. Finally, the source requests a
new route if one is still needed to that
destination.
10, 20, 30, 40, 50, 60,
70, 80
Number of flows
Traffic type
Packet size
CBR (UDP)
512 bytes
Number of mesh
nodes
99
Number of
gateways
01
Topology
Random, Grid
4.2. Simulation results
To evaluate the efficiency of the IMP-
AODV routing protocol, the network
performance
parameters
used
for
evaluation including throughput and
relative routing overhead.
Throughput: This is defined as the
amount of data that is transmitted through
the network per unit time, (i.e., data bytes
delivered to their destinations per second).
4. PERFORMANCE EVALUATION
4.1. Simulation parameters
To evaluate the performance of the
proposed routing protocol, simulations
were performed using the NS-2 network
simulator [11,12]. A hybrid wireless mesh
network with 99 mesh nodes and 01
gateway deployed on an area of 2000m x
2000m. We evaluated for 02 topologies:
grid and random. For the grid topology,
nodes are distributed 200 m apart. For the
random topology, we generated using
setdest program in NS2.
Relative routing overhead: The ratio of
the number of routing control packets
over the number of delivered data packet.
Figures 4 and 5 compared the relative
routing overhead between AODV and
IMP-AODV protocols for a random and
grid topologies. The relative routing
overhead between two routing protocols
becomes to be more distinct as the
number of flows increases from 10 to 80
in HWMN. Under the heavy load, IMP-
AODV can significantly reduce the
routing overhead (by about 54% at 80
flows in grid topology) for traffic destined
to the gateway. This improvement is due
to the IMP-AODV protocol restricting the
broadcast area of route request to reduce
routing overhead in HWMN.
Table 1.Simulation Parameters
Routing Protocol
Simulation time
Simulation Area
AODV vs. IMP-AODV
250 seconds
2000 × 2000 m2
Transmission
range
250 m
90
Số 25
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
x 105
Grid topology
flows), compared with AODV, we note
3
2.5
2
Imp-AODV
that IMP-AODV can improve the
throughput by 20% for grid topology.
This throughput enhancement of IMP-
AODV is due to the significant reduction
of bandwidth wasted by route request
messages in the route discovery.
AODV
1.5
1
x 105
Grid Topology
2.4
2.2
2
0.5
0
10
20
30
40
50
60
70
80
1.8
1.6
1.4
1.2
1
Number of flows
Fig 4. Relative routing overhead vs. the number
of flows in grid topology
Imp-AODV
AODV
x 105
Random topology
2.5
Imp-AODV
10
20
30
40 50
Number of flows
60
70
80
AODV
2
1.5
1
Fig 6. Total throughput vs. the number
of flows in grid topology
x 105
Random topology
1.9
1.8
1.7
1.6
1.5
1.4
1.3
1.2
1.1
0.5
0
10
20
30
40
50
60
70
80
Number of flows
Fig 5. Relative routing overhead vs. the number
of flows in random the number of flows
in random
Imp-AODV
AODV
10
20
30
40
50
60
70
80
Figures 6 and 7 showed the comparison
results of data transmission efficiency
(throughput) of protocols IMP-AODV
and AODV by increasing the number of
flows. These figures show that at lower
traffic load, the throughput of two routing
protocols is similar, but as the number
of flows increases, the total throughput
of IMP-AODV outperforms AODV
significantly. Under heavy load (at 70
Number of flows
Fig 7. Total throughput vs. the number of flows
in random topology
5. CONCLUSIONS
In this paper, we proposed IMP-AODV
routing protocol which based on gateway
discovery using hello packet and
restricting the broadcast area of route
Số 25
91
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
request to reduce routing overhead in NS-2. Simulation results showed that
HWMN. We evaluated the network IMP-AODV could significantly reduce
performance of IMP-AODV and AODV routing overhead and enhance overall
through packet-level simulation using the throughput performance.
TÀI LIỆU THAM KHẢO
[1] Akyildiz I.F., Wang X. and Wang W. (2005), “Wireless Mesh Networks: A Survey”, Computer
Networks Journal (Elsevier), vol. 47, no. 4, pp. 445-487.
[2] Bruno R, Conti M, Gregori E. “Mesh networks: commodity multihop ad hoc networks",
Communications Magazine 2005; 43(3):123-131.
[3] Ammari, H.M.: A survey of current architectures for connecting wireless mobile adhoc networks
to the Internet. International Journal of Communication Systems, 943–968 (2007).
[4] Draves, R., Padhye, J., Zill, B.: Routing in multi-radio, multi-hop wireless mesh networks. In:
Proc. ACM MobiCom, Philadelphia, PA, U.S.A (2004).
[5] Johnson, D., Maltz, D.: Dynamic source routing in ad hoc wireless networks. In: Mobile
Computing, vol. 353. Kluwer Academic Publishers, Dordrecht (1996).
[6] 6. Perkins, C., Belding-Royer, E., Das, S.: Ad hoc on-demand distance vector (AODV) routing.
IETF RFC 3561 (July 2003).
[7] Perkins, C., Bhagwat, P.: Highly dynamic destination-sequenced distance vector (DSDV) routing
for mobile computers. In: Proc. ACM SIGCOMM, London, U.K (August 1994).
[8] Haas, Z., Pearlman, M., Samar, P.: The zone routing protocol (ZRP) for ad hoc networks. IETF
MANET: Internet Draft (July 2002).
[9] M. Rosenschon, T. Manz, J. Habermann, and V. Rakocevic, "Gateway discovery algorithm for ad-
hoc networks using HELLO messages," In Proc. of IWWAN, May 2005.
[10] J. Usmani, R. Kumar and J. Prakash, "A survey on secure gateway discovery in MANET," 2017 7th
International Conference on Cloud Computing, Data Science & Engineering - Confluence, pp. 362-
368, Noida, 2017.
[12] K. Fall and K. Varadhan, Eds., The ns Manual, The VINT Project, UC Berkeley, LBL, USC/ISI, and
Giới thiệu tác giả:
Tác giả Lê Anh Ngọc tốt nghiệp đại học ngành toán và tin học tại Trường Đại học
Vinh và Trường Đại học Khoa học tự nhiên - Đại học Quốc gia Hà Nội các năm
1996 và 1998. Năm 2001 nhận bằng Thạc sĩ ngành công nghệ thông tin tại
Trường Đại học Bách khoa Hà Nội và năm 2009 nhận bằng Tiến sĩ ngành kỹ thuật
thông tin và truyền thông tại Đại học Quốc gia Kyungpook – Hàn Quốc. Hiện nay
tác giả đang công tác tại Trường Đại học Điện lực.
Lĩnh vực nghiên cứu: hệ thống thời gian thực, mạng truyền thông, Internet of
Things, tính toán thông minh.
92
Số 25
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ NĂNG LƯỢNG - TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
(ISSN: 1859 - 4557)
Số 25
93
9 trang
19/04/2022
1360
Bạn đang xem tài liệu "A routing algorithm using the gateway location via broadcasting the hello packet in a hybrid wireless mesh network", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- a_routing_algorithm_using_the_gateway_location_via_broadcast.pdf
