Thuật toán định tuyến sử dụng vị trí gateway qua quảng bá gói tin hello trong mạng hình lưới không dây lai

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 Ad hoc routing protocols are promising 
node for a certain interval of time. When candidates for hybrid wireless mesh net-
the RREQ reaches the destination node or works, due to their capability to deal with 
any node that has a fresh route to the dynamic environments. However, the 
destination, a Route Reply (RREP) packet 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 
and destination node addresses, route mesh networks are not utilized. In hybrid 
lifetime, and hop count and control flags. wireless mesh networks, most of the 
Each intermediary node that receives the traffic is directed towards a gateway and 
RREP then increments the hop-count, thus all the source nodes require a route to 
establishes a Forward Route to the source a gateway node for data delivery beyond 
of the packet, and transmits the packet via the mesh. Reactive routing protocols [5, 
the Reverse Route. To preserve the 6] generate multiple requests towards a 
connectivity information, each node gateway, they increase the traffic and 
 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 
 routing protocol for HWMN, which is an 
gateway becomes significant, thereby 
 improvement of AODV routing protocol 
increasing the overall delay. Conversely, 
in the case of proactive routing protocols based on gateway discovery using hello 
[7], each node periodically sends updates packet and restricting the broadcast area 
of its routing table to maintain correct of route requests to reduce routing 
route information to all destinations, overhead in HWMN. 
which results in a large overhead. In 
 3.1. Gateway discovery 
particular, the high mobility of the mesh 
clients degrades the performance of The AODV uses periodical HELLO 
proactive routing, as the routing table messages to indicate the presence of a 
becomes quickly outdated and requires an mesh node to its neighbors. We utilized it 
enormous overhead to keep it up to date. for gateway discovery without any 
In addition, since ad hoc routing protocol overhead. HELLO message is 
protocols were originally designed for modified with I-flag to indicate that these 
homogeneous ad hoc networks, consisting packets were originated by a gateway 
of resource-constrained mobile devices, [9,10]. It also contains the gateway’s 
their performance is not optimal in hybrid address and the distance value of the 
wireless mesh networks, as they are broadcasted mesh node. 
unable to take full advantage of the mesh 
routers in hybrid wireless mesh networks. Each mesh node maintains a distance 
 value (HC) to indicate the distance 
3. PROPOSED ROUTING PROTOCOL (number of hops) to a gateway, which is 
FOR HYBRID WIRELESS MESH initially set to be infinite. Only a 
NETWORKS gateway’s HC value is set to 0. Mesh 
As mentioned in the previous section, the nodes periodically send HELLO message 
large amount of overhead needed in to update neighbor information, 
broadcasting RREQ messages is the main meanwhile, gateway node broadcasts 
drawback of the AODV in high load net- HELLO with gateway information 
works such as HWMN. The overhead (I-Flag) and distance value (HC+1) (Fig. 
mostly consists of route request messages. 2a). When mesh nodes within one-hop 
In the route discovery process, each away from the gateway receive a HELLO 
intermediate node can broadcast packets message with I-flag and smaller distance 
to all neighbors whereas most traffic is value (HCHELLO), they update gateway 
destined from mesh clients to the gateway information and set their HC value with 
in HWMN. These increase the number of the HC value in the HELLO message. 
redundant messages transmitted in the Mesh nodes later broadcast their HELLO 
network and reduce the network 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- route, it broadcasts the RREQ with an HC 
hop away from the gateway. In this set to its HC value as shown in Fig. 3(a). 
manner, every node discovers the When a mesh node receives a RREQ 
gateway’s information and learns their message with a smaller distance value 
distance (HC) to the gateway. Imp-AODV (HC), it discards RREQ message. 
also used sequence number in HELLO Otherwise, it replaces the HC value on the 
packet to determine the timeliness of each RREQ with its HC value and then re-
packet. broadcasts the RREQ to all neighbors in 
 the same manner in AODV (Fig. 3b). 
 Begin Begin
 Begin Begin
 Generate the Node i receives 
 HELLO packet
 HELLO packet Node i receives 
 Generate RREQ RREQ packet
 HCRREQ=HCS
 No
 No Node i has Packet has 
 Gateway ID Gateway ID Yes No
 HCRREQ<HCi
 Yes Yes
 HC =HC
 No Broadcast RREQ RREQ i
 HCHELLO=HCi+1 Discard 
 HC <HC
 GatewayID =GatewayID HELLO i RREQ packet
 HELLO i Forward RREQ 
 Yes packet
 End
 HCi=HCHELLO
 Broadcast GatewayIDi=GatewayIDHELLO
 HELLO packet
 End
 Update the neighbor 
 End information
 (a) Source mesh node; (b) Intermediate mesh nodes 
 End Fig 3. Route Request Forwarding 
 (a) Sending Hello (b) Receiving Hello When a mesh node receives the RREQ, it 
 with I-Flag with I-Flag 
 establishes a reverse route to the RREQ 
 Fig. 2. Gateway discovery algorithm source in its routing table, and it either 
3.2. Route discovery replies to the RREQ if it has an entry for 
 the gateway or it forwards the RREQ. 
The route discovery in IMP-AODV is 
 Finally, the RREQ reaches the gateway 
fundamentally similar with AODV. It 
 and it unicasts a RREP. The node 
only improves RREQ forwarding process 
 receiving a RREP sets up a forward route 
such that reduces the scope of 
 to the gateway and desirable routes can be 
broadcasting to the gateway. IMP-AODV 
 discovered. 
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 10, 20, 30, 40, 50, 60, 
 Number of flows 
specified time interval, or if the next hop 70, 80 
node is no longer reachable. In these Traffic type CBR (UDP) 
cases, an invalidation notice is propagated Packet size 512 bytes 
 Number of mesh 
to the neighbors that have used this node 99 
as the next hop. Each time a route is used nodes 
 Number of 
to forward a data packet, its route 01 
 gateways 
expiration time is updated. When a node 
 Topology Random, Grid 
detects that a route to a neighbor is no 
longer valid, it removes the invalid entry 4.2. Simulation results 
and sends a route error message to the 
 To evaluate the efficiency of the IMP-
neighbors that are using the route. Nodes AODV routing protocol, the network 
that receive error messages will repeat performance parameters used for 
this process. Finally, the source requests a evaluation including throughput and 
new route if one is still needed to that relative routing overhead. 
destination. 
 Throughput: This is defined as the 
4. PERFORMANCE EVALUATION amount of data that is transmitted through 
 the network per unit time, (i.e., data bytes 
4.1. Simulation parameters 
 delivered to their destinations per second). 
To evaluate the performance of the 
 Relative routing overhead: The ratio of 
proposed routing protocol, simulations the number of routing control packets 
were performed using the NS-2 network over the number of delivered data packet. 
simulator [11,12]. A hybrid wireless mesh Figures 4 and 5 compared the relative 
network with 99 mesh nodes and 01 routing overhead between AODV and 
gateway deployed on an area of 2000m x IMP-AODV protocols for a random and 
2000m. We evaluated for 02 topologies: grid topologies. The relative routing 
grid and random. For the grid topology, overhead between two routing protocols 
nodes are distributed 200 m apart. For the becomes to be more distinct as the 
random topology, we generated using number of flows increases from 10 to 80 
setdest program in NS2. in HWMN. Under the heavy load, IMP-
 AODV can significantly reduce the 
 Table 1.Simulation Parameters routing overhead (by about 54% at 80 
 Routing Protocol AODV vs. IMP-AODV flows in grid topology) for traffic destined 
 Simulation time 250 seconds to the gateway. This improvement is due 
 Simulation Area 2000 × 2000 m2 to the IMP-AODV protocol restricting the 
 Transmission broadcast area of route request to reduce 
 250 m 
 range routing overhead in HWMN. 
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) 
 5
 x 10 Grid topology flows), compared with AODV, we note 
 3
 ImpD-AODV-AODV that IMP-AODV can improve the 
 AODVAODV 
 2.5 throughput by 20% for grid topology. 
 This throughput enhancement of IMP-
 2 AODV is due to the significant reduction 
 of bandwidth wasted by route request 
 1.5
 messages in the route discovery. 
 5
 1 x 10 Grid Topology
 2.4
Routing Overhead (packets) Overhead Routing
 0.5 2.2
 2
 0
 10 20 30 40 50 60 70 80
 1.8
 Number of flows 
 1.6
Fig 4. Relative routing overhead vs. the number 
 Total throughput (bps) Total throughput
 of flows in grid topology 1.4
 ImpD-AODV-AODV 
 1.2 AODV 
 5 AODV
 x 10 Random topology
 2.5
 Imp-AODV 1
 D-AODV 10 20 30 40 50 60 70 80
 AODVAODV Number of flows 
 2
 Fig 6. Total throughput vs. the number 
 of flows in grid topology 
 1.5
 5
 x 10 Random topology
 1.9
 1
 1.8
 Routing Overhead (packets) Overhead Routing
 1.7
 0.5
 1.6
 0
 10 20 30 40 50 60 70 80 1.5
 Number of flows
 1.4
Fig 5. Relative routing overhead vs. the number (bps) Total throughput
 1.3
 of flows in random the number of flows 
 ImpD-AODV-AODV 
 in random 1.2 AODVAODV 
 1.1
 10 20 30 40 50 60 70 80
Figures 6 and 7 showed the comparison Number of flows
results of data transmission efficiency Fig 7. Total throughput vs. the number of flows 
(throughput) of protocols IMP-AODV in random topology 
and AODV by increasing the number of 
flows. These figures show that at lower 5. CONCLUSIONS 
traffic load, the throughput of two routing 
protocols is similar, but as the number In this paper, we proposed IMP-AODV 
of flows increases, the total throughput routing protocol which based on gateway 
of IMP-AODV outperforms AODV discovery using hello packet and 
significantly. Under heavy load (at 70 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. 
 [11] The Network Simulator-NS-2. Available:  
 [12] K. Fall and K. Varadhan, Eds., The ns Manual, The VINT Project, UC Berkeley, LBL, USC/ISI, and 
 Xerox PARC, Apr. 2002. available:  
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