Định tuyến dựa vào vị trí của Gateway trong mạng hình lưới không dây lai

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

31
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề 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). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Định tuyến dựa vào vị trí của Gateway trong mạng hình lưới không dây lai

Đị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 Hoàng Quốc Việt, Hà nội Email: duyhuy2906@gmail.com; anhngoc@epu.edu.vn thì hiệu quả của giao thức này lại không cao do đặc tính quảng Abstract — Trong bài báo này, chúng tôi đề xuất giao thức định bá trong quá trình khám phá tuyến. 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ần còn lại của bài báo được tổ chức như sau: Phần II giới 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 thiệu tổng quan về vấn đề định tuyến trong mạng HMN. Trong gần với vị trí của gateway ở Lớp 1 trong HMN, điều này sẽ làm phần III, chúng tôi đề xuất giải pháp cải tiến định tuyến IMP- giảm các thông điệp dư thừa và do vậy dẫn đến tăng hiệu năng AODV cho mạng HMN. Phần IV cung cấp các kết quả đánh giá của mạng HMN. Kết quả mô phỏng sử dụng phần mềm NS-2 đã 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 cho thấy hiệu quả của giao thức IMP-AODV qua các độ đo hiệu trong phần V. năng về dư thừa số bản tin định tuyến và hiệu quả truyền dữ liệu (throughput). II. TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG MẠNG Keywords – Hybrid WMN, AODV, routing 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ự I. GIỚI THIỆU như trong mạng tùy biến không dây MANET [3,4]: các nút Mạng hình lưới không dây lai (HMN - Hybrid Mesh Networks) mạng mesh client, là các thiết bị người dùng như điện thoại là một mô hình truyền thông mới được thiết lập bởi các nút thông minh, laptop, … luôn có xu hướng tự do chuyển động. mạng không dây kết nối với nhau theo dạng lưới [1,2]: Lớp 1 Các liên kết có thể bị phá vỡ hoặc khôi phục bất cứ lúc nào. bao gồm mạng lưới các gateway cung cấp các kết nối tới mạng Ngoà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 Internet hoặc các mạng khác. Lớp 2 bao gồm mạng lưới các các cần phải nhỏ. Các giao thức định tuyến cho mạng MANET có thiết bị định tuyến không dây (mesh router) có thể cố định hoặc thể được áp dụng cho HMN, được phân thành 3 nhóm [4]: định ít di chuyển thực hiện chức năng chuyển tiếp tới các gateway ở tuyến theo yêu cầu (Demand Driven), định tuyến theo bảng lớp 1. Lớp 3 là mạng lưới các thiết bị người dùng di động (Table Driven), định tuyến lai ghép (Hybrid Driven): (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, Internet 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 toàn bộ tập hoán vị Level 1 gateways IGW tuyến. Trong mạng MANET, các tuyến hoạt động có thể ngừng IGW IGW 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 Level 2 backbone of mesh tuyến theo yêu cầu thường có tiêu đề trao đổi thông tin định routers Mesh router 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 Mesh client bảng. Tuy nhiên, vấn đề lớn nhất của các giao thức định tuyến Level 3 mesh clients 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 Mesh client gồm: giao thức định tuyến nguồn động DSR (Dynamic Source Mesh clients connected in multi-hop 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] Hình 1. Mạng hình lưới không dây lai (HMN) và giao thức định tuyến theo thứ tự tạm thời TORA (Temporally Ordered Routing Algorithm) [6]. 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ư Định tuyến theo bảng: Trong phương pháp định tuyến theo trong mạng tùy biến không dây MANET [3,4]. Trong đó giao bảng, các node trong mạng MANET liên tục đánh giá các tuyến thức AODV [5] là một giao thức định tuyến theo yêu cầu đã 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 được nghiên cứu và phát triển rộng rãi. Tuy nhiên, giao thức dẫn định tuyến ngay lập tức khi cần. Trong các giao thức định AODV được thiết kế cho mạng có tính di động cao, trong tuyến theo bảng, tất cả các node cần duy trì thông tin về cấu trường hợp mạng HMN là mạng có tính di động thấp (các mesh hình mạng. Khi cấu hình mạng thay đổi, các cập nhật được router ít thay đổi) và có kết nối tới Internet hoặc các mạng khá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ới các nút mạng trong HMN (hình 2). Mỗi nút mạng sẽ duy trì tương thích từ các thuật toán chọn đường dẫn ngắn nhất trong một biến HC để lưu trữ giá trị khoảng cách tới gateway, riêng các mạng hữu tuyến truyền thống. Các thuật toán định tuyến nút Gateway sẽ có giá trị HC bằng 0. 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 đề Begin thông tin để duy trì cấu hình mạng đối với các giao thức này Begin thường là lớn. Một số giao thức định tuyến điển hình theo bảng Node i receives HELLO packet trong MANET gồm: định tuyến vector khoảng cách tuần tự Generate the đích DSDV (Destination Sequence Distance Vector) [7], định HELLO packet tuyến trạng thái tối ưu liên kết OLSR (Optimized Link State No Packet has Routing) [8]… Gateway ID No Node i has Định tuyến lai ghép: Các giao thức định tuyến lai ghép Gateway ID Yes được đề xuất để kết hợp các đặc tính ưu điểm của các giao thức No Yes định tuyến theo bảng và theo yêu cầu. Thông thường, các giao HCHELLO
hình 4. Theo đó, khi một nút trong HMN có nhu cầu khám phá IV. ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC IMP-AODV tuyến (on demand) tới gateway, nút đó sẽ quảng bá thông điệp Phần mềm mô phỏng mạng NS-2 [11,12] được lựa chọn để tìm đường RREQ với trường HC được gán là giá trị khoảng đánh giá tính hiệu quả của giao thức cải tiến. Các mô phỏng cách HC của nút đó. Khi các nút lân cận nhận được thông điệp được tiến hành cho 100 nút mạng với các sơ đồ mạng HMN RREQ này, nếu giá trị HC trong thông điệp RREQ lớn hơn giá dạng lưới (grid topology) và dạng ngẫu nhiên (random trị HC tại nút nhận, chúng sẽ thay thế giá trị HC của RREQ topology) trên diện tích 2000 m x 2000 m. Trong sơ đồ dạng bằng giá trị HC của nút nhận và quảng bá thông điệp RREQ lưới các nút mạng cách nhau khoảng cách 200m. Trong sơ đồ sau khi sửa đổi này. mạng ngẫu nhiên, 1 nút mạng được chọn làm nút gateway và Ngược lại, nếu giá trị HC trong thông điệp RREQ bé hơn hoặc 99 nút mạng còn lại được triển khai ngẫu nhiên trên diện tích bằng giá trị HC tại nút nhận chúng sẽ hủy bỏ thông điệp RREQ đã cho. Các nút mạng HMN đều sử dụng giao thức MAC nhận được, để tránh dư thừa các thông điệp quảng bá. Chính 802.11b với cự ly truyền tối đa 250m. Ngoài ra, để giả lập các điều này cho phép giới hạn phạm vi quảng bá, thay vì quảng bá kết nối Internet qua gateway, mô phỏng này sử dụng các kết ra toàn mạng, Imp-AODV chỉ quảng bá trong phạm vi nhỏ về nối CBR (constant bit rate) với kích thước gói dữ liệu 512 phía gateway. 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 Để thiết lập tuyến cho việc chuyển dữ liệu, quá trình hoàn toàn của các kết nối này là 4 packets/giây. Thời gian mô phỏng tương tự như trong giao thức AODV. Khi một nút nhận được được thực hiện trong 150 giây. 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 Hình 5 và hình 6 so sánh số lượng các gói tin điều khiển do nó có sẵn tuyến tới đích trong bảng định tuyến, ngược lại nó sẽ định tuyến gây ra (routing overhead) giữa hai giao thức AODV tiếp tục quảng bá thông điệp RREQ đã sửa đổi theo cách như và Imp-AODV cho sơ đồ mạng ngẫu nhiên và dạng lưới. Kết đã trình bày ở trên. Nếu gateway nhận được RREQ thì nó sẽ quả cho thấy khi tăng tải trong mạng HMN – số lượng các kết gửi một thông điệp phản hồi tuyến RREP cho nút nguồn gửi nối tăng từ 10 đến 80 kết nối dữ liệu, lượng dư thừa do Imp- RREQ và thiết lập tuyến dùng để chuyển dữ liệu từ nút nguồn AODV giảm đi rất nhiều, khoảng 54% tương ứng với số kết tới gateway. 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ế Phương pháp duy trì tuyến hoàn toàn tương tự như đối với vùng quảng bá do quá trình khám phá tuyến gây ra như trong AODV, một tuyến nào tại một nút có thể bị thay đổi sau một AODV. 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 2.4 5 x 10 Grid Topology 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. 2.2 5 x 10 Random topology 2.5 2 Total throughput (bps) D-AODV Imp-AODV AODV AODV 1.8 2 Routing Overhead (packets) 1.6 1.5 1.4 Imp-AODV D-AODV 1 1.2 AODV AODV 1 10 20 30 40 50 60 70 80 0.5 Number of flows 0 Hình 7. So sánh hiệu quả truyền dữ liệu trong trường hợp 10 20 30 40 50 60 70 80 Number of flows sơ đồ HMN dạng lưới 5 Random topology x 10 Hình 5. So sánh số lượng các gói tin điều khiển trong trường hợp sơ 1.9 đồ HMN ngẫu nhiên 1.8 5 Grid topology x 10 3 D-AODV Imp-AODV 1.7 AODV AODV Total throughput (bps) 2.5 1.6 Routing Overhead (packets) 1.5 2 1.4 1.5 1.3 Imp-AODV D-AODV 1 1.2 AODV AODV 0.5 1.1 10 20 30 40 50 60 70 80 Number of flows 0 10 20 30 40 50 60 70 80 Hình 8. So sánh hiệu quả truyền dữ liệu trong trường hợp Number of flows sơ đồ HMN ngẫu nhiên 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 xuông, đặ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 [1] 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: http://www.isi.edu/nsnam/ns [12] K. Fall and K. Varadhan, Eds., The ns Manual, The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, Apr. 2002. available: http://www.isi.edu/nsnam/ns/ 202