Định tuyến dựa vào vị trí của Gateway trong mạng hình lưới không dây lai
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (705.27 KB, 4 trang )
Định Tuyến Dựa Vào Vị Trí Của Gateway Trong
Mạng Hình Lưới Không Dây Lai
Đồng Duy Huy và Lê Anh Ngọc
Khoa Điện Tử Viễn Thơng, Đại Học Điện Lực
235 Hồng Quốc Việt, Hà nội
Email: ;
thì hiệu quả của giao thức này lại khơng cao do đặc tính quảng
bá trong q trình khám phá tuyến.
Abstract — Trong bài báo này, chúng tơi đề xuất giao thức định
tuyến IMP-AODV cho mạng hình lưới không dây lai (HMN). Ý
tưởng cơ bản của bài báo là đề xuất giải pháp nhằm giới hạn
phạm vi quảng bá của các thơng điệp tìm đường tới các nút mạng
gần với vị trí của gateway ở Lớp 1 trong HMN, điều này sẽ làm
giảm các thông điệp dư thừa và do vậy dẫn đến tăng hiệu năng
của mạng HMN. Kết quả mô phỏng sử dụng phần mềm NS-2 đã
cho thấy hiệu quả của giao thức IMP-AODV qua các độ đo hiệu
năng về dư thừa số bản tin định tuyến và hiệu quả truyền dữ liệu
(throughput).
Phần còn lại của bài báo được tổ chức như sau: Phần II giới
thiệu tổng quan về vấn đề định tuyến trong mạng HMN. Trong
phần III, chúng tôi đề xuất giải pháp cải tiến định tuyến IMPAODV cho mạng HMN. Phần IV cung cấp các kết quả đánh giá
hiệu năng của giao thức. Cuối cùng, chúng tôi kết luận bài báo
trong phần V.
TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG MẠNG
HÌNH LƯỚI KHƠNG DÂY
Vấn đề định tuyến trong mạng HMN gặp thách thức tương tự
như trong mạng tùy biến không dây MANET [3,4]: các nút
mạng mesh client, là các thiết bị người dùng như điện thoại
thông minh, laptop, … ln có xu hướng tự do chuyển động.
Các liên kết có thể bị phá vỡ hoặc khơi phục bất cứ lúc nào.
Ngồi ra, dải thơng trong mạng không dây là thấp, các nút bị
hạn chế bởi nguồn nuôi nên tổng lưu lượng dành cho định tuyến
cần phải nhỏ. Các giao thức định tuyến cho mạng MANET có
thể được áp dụng cho HMN, được phân thành 3 nhóm [4]: định
tuyến theo yêu cầu (Demand Driven), định tuyến theo bảng
(Table Driven), định tuyến lai ghép (Hybrid Driven):
II.
Keywords – Hybrid WMN, AODV, routing
I.
GIỚI THIỆU
Mạng hình lưới khơng dây lai (HMN - Hybrid Mesh Networks)
là một mơ hình truyền thơng mới được thiết lập bởi các nút
mạng không dây kết nối với nhau theo dạng lưới [1,2]: Lớp 1
bao gồm mạng lưới các gateway cung cấp các kết nối tới mạng
Internet hoặc các mạng khác. Lớp 2 bao gồm mạng lưới các các
thiết bị định tuyến khơng dây (mesh router) có thể cố định hoặc
ít di chuyển thực hiện chức năng chuyển tiếp tới các gateway ở
lớp 1. Lớp 3 là mạng lưới các thiết bị người dùng di động
(mesh client) có nhu cầu kết nối Internet hoặc các mạng khác
thơng qua lớp 2 và lớp 3 (Hình 1).
Định tuyến theo yêu cầu: Trong phương pháp định tuyến
theo yêu cầu, các đường dẫn được tìm kiếm chỉ khi cần thiết,
hoạt động tìm tuyến bao gồm cả thủ tục xác định tuyến. Thủ tục
tìm tuyến kết thúc khi một tuyến khơng được tìm thấy hoặc
khơng có tuyến khả dụng sau khi xác minh tồn bộ tập hốn vị
tuyến. Trong mạng MANET, các tuyến hoạt động có thể ngừng
do tính di động của node. Vì vậy, thơng tin duy trì tuyến là tối
quan trọng đối với các giao thức định tuyến theo yêu cầu. So
với các giao thức định tuyến theo bảng, các giao thức định
tuyến theo yêu cầu thường có tiêu đề trao đổi thơng tin định
tuyến nhỏ hơn. Vì vậy, về mặt nguyên tắc, các giao thức này có
khả năng mở rộng tốt hơn đối với các giao thức định tuyến theo
bảng. Tuy nhiên, vấn đề lớn nhất của các giao thức định tuyến
theo yêu cầu là trễ do tìm kiếm tuyến trước khi chuyển tiếp
thông tin dữ liệu. Một số giao thức định tuyến theo yêu cầu
gồm: giao thức định tuyến nguồn động DSR (Dynamic Source
Routing) [4], giao thức định tuyến vector khoảng cách theo yêu
cầu AODV (Ad hoc On-demand Distance Vector routing) [5]
và giao thức định tuyến theo thứ tự tạm thời TORA
(Temporally Ordered Routing Algorithm) [6].
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
Hình 1. Mạng hình lưới khơng dây lai (HMN)
Các mesh client và mesh router có thể liên kết khơng dây đa
chặng với nhau sử dụng các giao thức định tuyến tương tự như
trong mạng tùy biến không dây MANET [3,4]. Trong đó giao
thức AODV [5] là một giao thức định tuyến theo yêu cầu đã
được nghiên cứu và phát triển rộng rãi. Tuy nhiên, giao thức
AODV được thiết kế cho mạng có tính di động cao, trong
trường hợp mạng HMN là mạng có tính di động thấp (các mesh
router ít thay đổi) và có kết nối tới Internet hoặc các mạng khác
Định tuyến theo bảng: Trong phương pháp định tuyến theo
bảng, các node trong mạng MANET liên tục đánh giá các tuyến
tới các node để duy trì tính tương thích, cập nhật của thơng tin
định tuyến. Vì vậy, một node nguồn có thể đưa ra một đường
dẫn định tuyến ngay lập tức khi cần. Trong các giao thức định
tuyến theo bảng, tất cả các node cần duy trì thơng tin về cấu
hình mạng. Khi cấu hình mạng thay đổi, các cập nhật được
truyền lan trong mạng nhằm thông báo sự thay đổi. Hầu hết các
199
giao thức định tuyến theo bảng đều kế thừa và sửa đổi đặc tính
tương thích từ các thuật tốn chọn đường dẫn ngắn nhất trong
các mạng hữu tuyến truyền thống. Các thuật toán định tuyến
theo bảng được sử dụng cho các node cập nhật trạng thái mạng
và duy trì tuyến bất kể có lưu lượng hay khơng. Vì vậy, tiêu đề
thơng tin để duy trì cấu hình mạng đối với các giao thức này
thường là lớn. Một số giao thức định tuyến điển hình theo bảng
trong MANET gồm: định tuyến vector khoảng cách tuần tự
đích DSDV (Destination Sequence Distance Vector) [7], định
tuyến trạng thái tối ưu liên kết OLSR (Optimized Link State
Routing) [8]…
tới các nút mạng trong HMN (hình 2). Mỗi nút mạng sẽ duy trì
một biến HC để lưu trữ giá trị khoảng cách tới gateway, riêng
nút Gateway sẽ có giá trị HC bằng 0.
Begin
Begin
Node i receives
HELLO packet
Generate the
HELLO packet
No
No
Định tuyến lai ghép: Các giao thức định tuyến lai ghép
được đề xuất để kết hợp các đặc tính ưu điểm của các giao thức
định tuyến theo bảng và theo yêu cầu. Thông thường, các giao
thức định tuyến lai ghép MANET được sử dụng trong kiến trúc
phân cấp. Các giao thức định tuyến theo bảng và theo yêu cầu
được triển khai trong các cấp thích hợp. Một số ví dụ về giao
thức định tuyến lai ghép: giao thức định tuyến vùng ZRP (Zone
Routing Protocol) [9], giao thức định tuyến trạng thái liên kết
dựa trên vùng ZHLS (Zone-based Hierarchical Link State
routing) [10] …
Packet has
Gateway ID
Node i has
Gateway ID
Yes
No
Yes
HCHELLO
HCHELLO=HCi+1
Yes
GatewayIDHELLO=GatewayIDi
III. GIẢI PHÁP ĐỊNH TUYẾN IMP-AODV CHO MẠNG
HÌNH LƯỚI KHƠNG DÂY LAI
HCi=HCHELLO
GatewayIDi=GatewayIDHELLO
Broadcast
HELLO packet
Update the neighbor
information
End
End
(a) Gửi thơng điệp thăm dị
(b) Nhận thơng điệp thăm dị
Hình 3. Thuật tốn khám phá gateway và khoảng cách
của các nút mạng HMN
Trong rất nhiều các giao thức định tuyến đã được phát triển
cho mạng HMN, AODV là giao thức định tuyến được nghiên
cứu, phát triển và triển khai rộng rãi trong các ứng dụng thực tế
[5]. Giao thức định tuyến AODV (Ad hoc Ondemand Distance
Vector) là giao thức được phát triển và ứng dụng cho mạng
MANET tự trị với topology mạng thay đổi thường xuyên.
Trong môi trường mạng HMN với topology ít thay đổi (các
mesh router tương đối cố định) và kết nối với Internet hoặc các
mạng khác qua các gateway, hiệu quả của giao thức AODV
tương đối thấp do phạm vi quảng bá của các thông điệp tìm
đường là trên phạm vi tồn mạng. Ý tưởng cơ bản của bài báo
là đề xuất phương pháp nhằm giới hạn phạm vi quảng bá của
các thơng điệp tìm đường (Route Request), dựa trên cơ chế chỉ
quảng bá các thông điệp tìm đường tới các nút mạng gần với
gateway, điều này sẽ làm giảm các thông điệp dư thừa trong
mạng (overhead) và do vậy dẫn đến tăng hiệu năng của mạng.
Khởi đầu, gateway sẽ quảng bá thơng điệp thăm dị (Hello) sửa
đổi trong đó có giá trị cờ I-Flag dùng để đánh dấu thông điệp
chứa thông tin từ gateway và giá trị biến HC của gateway dùng
để xác định khoảng cách từ gateway tới các nút mạng. Khi các
nút lân cận gateway nhận được thơng điệp thăm dị này, dựa
vào tính cập nhật thơng tin dựa trên số thứ tự (sequence
number) của thơng điệp thăm dị, các nút đó sẽ tăng giá trị HC
trong thông điệp nhận được lên 1 và lưu trữ vào giá trị biến HC
của các nút (khoảng cách tới gateway). Sau đó các nút này lại
tiếp tục quảng bá thơng điệp thăm dị với giá trị HC của chúng
và giá trị cờ I-flag. Theo cách trên tất cả các nút trong mạng sẽ
nhận được các thông tin từ gateway và khoảng cách tới
gateway (hình 3).
Begin
Begin
Giao thức Imp-AODV cải tiến giao thức định tuyến AODV với
việc bổ sung thêm pha khám phá gateway và khoảng cách từ
các nút tới gateway. Bên cạnh đó, thuật tốn khám phá tuyến
sẽ chỉ quảng bá các thơng điệp tìm đường tới các nút gần (theo
khoảng cách) với gateway hơn, các nút có khoảng cách xa hơn
sẽ loại bỏ các thơng điệp tìm đường nhận được, do vậy phạm
vi quảng bá sẽ được thu hẹp lại.
Node i receives
RREQ packet
Generate RREQ
HCRREQ=HCS
Yes
HCRREQ
No
HCRREQ=HCi
Broadcast RREQ
Discard
RREQ packet
Forward RREQ
packet
End
End
(a) Nút nguồn quảng bá
thơng điệp RREQ
Hình 2. Q trình khám phá gateway và khoảng cách từ gateway
(b) Nút nhận được thơng điệp
RREQ
Hình 4. Thuật tốn xử lý các thơng điệp RREQ tại các nút mạng
HMN
a. Khám phá gateway và khoảng cách các nút tới gateway
b. Khám phá tuyến
Giao thức AODV sử dụng các thơng điệp thăm dị (Hello
message) để xác định sự có mặt của các nút mạng lân cận.
Trong Imp-AODV, các thông điệp này sẽ được sử dụng để
quảng bá các thông tin của gateway và khoảng cách từ gateway
Thuật toán khám phá tuyến của Imp-AODV cơ bản tương tự
như đối với AODV, tuy nhiên các thông điệp tìm đường
RREQ được sửa đổi để chứa giá trị khoảng cách HC (số
chặng) tới gateway. Thuật toán sửa đổi được chỉ ra như trong
200
hình 4. Theo đó, khi một nút trong HMN có nhu cầu khám phá
tuyến (on demand) tới gateway, nút đó sẽ quảng bá thơng điệp
tìm đường RREQ với trường HC được gán là giá trị khoảng
cách HC của nút đó. Khi các nút lân cận nhận được thông điệp
RREQ này, nếu giá trị HC trong thông điệp RREQ lớn hơn giá
trị HC tại nút nhận, chúng sẽ thay thế giá trị HC của RREQ
bằng giá trị HC của nút nhận và quảng bá thông điệp RREQ
sau khi sửa đổi này.
IV. ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC IMP-AODV
Phần mềm mô phỏng mạng NS-2 [11,12] được lựa chọn để
đánh giá tính hiệu quả của giao thức cải tiến. Các mô phỏng
được tiến hành cho 100 nút mạng với các sơ đồ mạng HMN
dạng lưới (grid topology) và dạng ngẫu nhiên (random
topology) trên diện tích 2000 m x 2000 m. Trong sơ đồ dạng
lưới các nút mạng cách nhau khoảng cách 200m. Trong sơ đồ
mạng ngẫu nhiên, 1 nút mạng được chọn làm nút gateway và
99 nút mạng còn lại được triển khai ngẫu nhiên trên diện tích
đã cho. Các nút mạng HMN đều sử dụng giao thức MAC
802.11b với cự ly truyền tối đa 250m. Ngoài ra, để giả lập các
kết nối Internet qua gateway, mô phỏng này sử dụng các kết
nối CBR (constant bit rate) với kích thước gói dữ liệu 512
bytes, trong đó số lượng các nguồn phát được thay đổi từ 10
đến 80 và tất cả đều có chung đích là nút gateway. Tốc độ phát
của các kết nối này là 4 packets/giây. Thời gian mô phỏng
được thực hiện trong 150 giây.
Ngược lại, nếu giá trị HC trong thông điệp RREQ bé hơn hoặc
bằng giá trị HC tại nút nhận chúng sẽ hủy bỏ thông điệp RREQ
nhận được, để tránh dư thừa các thơng điệp quảng bá. Chính
điều này cho phép giới hạn phạm vi quảng bá, thay vì quảng bá
ra toàn mạng, Imp-AODV chỉ quảng bá trong phạm vi nhỏ về
phía gateway.
Để thiết lập tuyến cho việc chuyển dữ liệu, q trình hồn tồn
tương tự như trong giao thức AODV. Khi một nút nhận được
RREQ, nó sẽ thiết lập tuyến ngược (reverse route) tới nút đã
gửi RREQ và gửi lại một thơng điệp phản hồi tuyến RREP nếu
nó có sẵn tuyến tới đích trong bảng định tuyến, ngược lại nó sẽ
tiếp tục quảng bá thơng điệp RREQ đã sửa đổi theo cách như
đã trình bày ở trên. Nếu gateway nhận được RREQ thì nó sẽ
gửi một thơng điệp phản hồi tuyến RREP cho nút nguồn gửi
RREQ và thiết lập tuyến dùng để chuyển dữ liệu từ nút nguồn
tới gateway.
Hình 5 và hình 6 so sánh số lượng các gói tin điều khiển do
định tuyến gây ra (routing overhead) giữa hai giao thức AODV
và Imp-AODV cho sơ đồ mạng ngẫu nhiên và dạng lưới. Kết
quả cho thấy khi tăng tải trong mạng HMN – số lượng các kết
nối tăng từ 10 đến 80 kết nối dữ liệu, lượng dư thừa do ImpAODV giảm đi rất nhiều, khoảng 54% tương ứng với số kết
nối là 80 trong trường hợp sơ đồ mạng HMN dạng lưới. Có
được sự cải thiện này là do giao thức Imp-AODV đã hạn chế
vùng quảng bá do quá trình khám phá tuyến gây ra như trong
AODV.
Phương pháp duy trì tuyến hồn tồn tương tự như đối với
AODV, một tuyến nào tại một nút có thể bị thay đổi sau một
thời gian, nút đó sẽ thơng báo cho các nút lân cận mà có tuyến
qua nút hiện tại bằng thông điệp báo lỗi. Thông báo lỗi sẽ được
chuyển tiếp tới nút nguồn và nó sẽ khởi tạo lại quá trình khám
phá tuyến.
5
Random topology
x 10
2
Imp-AODV
D-AODV
AODV
AODV
2
Routing Overhead (packets)
Grid Topology
x 10
2.2
Total throughput (bps)
2.5
5
2.4
1.5
1.8
1.6
1.4
Imp-AODV
D-AODV
1.2
1
AODV
AODV
1
10
0.5
0
10
20
30
40
50
Number of flows
60
70
20
30
5
5
1.9
80
Random topology
x 10
1.7
Imp-AODV
D-AODV
Total throughput (bps)
AODV
AODV
2.5
Routing Overhead (packets)
70
1.8
Grid topology
x 10
60
Hình 7. So sánh hiệu quả truyền dữ liệu trong trường hợp
sơ đồ HMN dạng lưới
80
Hình 5. So sánh số lượng các gói tin điều khiển trong trường hợp sơ
đồ HMN ngẫu nhiên
3
40
50
Number of flows
2
1.5
1.6
1.5
1.4
1.3
Imp-AODV
D-AODV
1
1.1
10
0.5
0
10
AODV
AODV
1.2
20
30
40
50
Number of flows
60
70
20
30
40
50
Number of flows
60
70
80
Hình 8. So sánh hiệu quả truyền dữ liệu trong trường hợp
sơ đồ HMN ngẫu nhiên
80
Hình 6. So sánh số lượng các gói tin điều khiển trong trường hợp
sơ đồ HMN dạng lưới
201
Hình 7 và hình 8 chỉ ra kết quả so sánh về hiệu quả truyền dữ
liệu (throughput) của hai giao thức Imp-AODV và AODV. Kết
quả mô phỏng cho thấy, khi tải trong HMN tăng lên dung
lượng truyền của cả hai giao thức đều tăng lên, tuy nhiên giao
thức Imp-AODV cho thấy hiệu quả hơn hẳn, cải tiến khoảng
20% dung lượng truyền tương ứng với số kết nối là 70 trong
trường hợp sơ đồ mạng HMN dạng lưới.. Sự cải thiện đáng kể
này là do số lượng các thông điệp quảng bá giảm xng, đặc
biệt là thơng điệp tìm đường RREQ, dẫn đến làm giảm sự tiêu
tốn băng thông cho các thông điệp điều khiển và giảm sự xung
đột trong mạng HMN.
V.
KẾT LUẬN
Trong bài báo này, chúng tôi đã nghiên cứu về mơ hình mạng
hình lưới khơng dây lai HMN, các cơ chế định tuyến trong
mạng này và đề xuất giao thức định tuyến cải tiến IMP-AODV.
Kết quả phân tích cho thấy giao thức cải tiến IMP-AODV đã
làm giảm đáng kế lượng dư thừa dữ liệu và góp phần cải thiện
hiệu năng của mạng HMN. Trong tương lai, chúng tôi sẽ tiếp
tục khảo sát hiệu quả của giao thức IMP-AODV trong HMN
với nhiều nút gateway, cũng như khả năng triển khai thực tế
cho các thiết bị HMN.
TÀI LIỆU THAM KHẢO
Akyildiz I,Wang X,Wang W. Wireless mesh works: a survey. Computer
Networks Journal 2005; 47(4):445-487.
[2] Bruno R, Conti M, Gregori E. Mesh networks: commodity multihop ad
hoc networks. Communications Magazine 2005; 43(3):123-131.
[3] S.S.Dhenakaran and A.Parvathavarthini, “An Overview of Routing
protocols in Mobile Ad-Hoc Network”, International Journal of
Advanced Research in Computer Science and Software Engineering,
Vol. 3, pp. 251-259, Feb. 2013.
[4] E. M. Royer, and C. K. Toh, "A review of current routing protocols for
ad hoc mobile wireless networks," IEEE Personal Communications
Magazine, vol.6, pp. 46-55, Apr. 1999.
[5] C. E. Perkins, and E. M. Royer, "Ad hoc on-demand distance vector
routing," in Proc. of the 2nd IEEE workshop on Mobile Computing
Systems and Applications, pp. 90–100, 1999.
[6] Park and MS Corson "A highly adaptive distributed routing algorithm for
mobile wireless networks", in Proc. of INFOCOM'97, Apr. 1997.
[7] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers," ACM
SIGCOMM Computer Communication Review, vol. 24, pp. 234-244,
1994.
[8] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L.
Viennot, "Optimized Link State Routing Protocol for Ad hoc Networks,"
in Proc. of IEEE INMIC, 2001.
[9] Z. J. Haas, "A New Routing Protocol for the Reconfigurable Wireless
Networks," in Proc. of IEEE ICUPC, 1997.
[10] M Joa-Ng and I.-T. Lu, "A Peer-to-Peer zone-based two-level link state
routing for mobile Ad Hoc Networks", IEEE Journal on Selected Areas
in Communications, Special Issue on Ad-Hoc Networks, pp.1415-25.
[11] The Network Simulator-NS-2. Available: />[12] K. Fall and K. Varadhan, Eds., The ns Manual, The VINT Project, UC
LBL, USC/ISI, and Xerox PARC, Apr. 2002.
Berkeley,
available: />[1]
202
