ĐẠI HỌC QUỐC GIA TP HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA FOG BÁO CÁO TỔNG KẾT KẾT QUẢ ĐỀ TÀI KHCN CẤP TRƯỜNG Tên đề tài: Nghiên cứu và hiện thực giao thức định tuyến proactive hữu hiệu ở link layer cho mạng ad hoc không dây Mã số đề tài: T-KHMT-2011-29 Thời gian thực hiện: 15/3/2011 đến 15/3/2012 và được gia hạn 6 tháng Chủ nhiệm đề tài: TS Lê Ngọc Minh Cán bộ tham gia đề tài: 1. TS Lê Ngọc Minh 2. ThS Trịnh Minh Đức 3. KS Phạm Sỹ Nam Thành phố Hồ Chí Minh – Tháng 10/2012 1 Danh sách các cán bộ tham gia thực hiện đề tài (Ghi rõ học hàm, học vị, đơn vị công tác gồm bộ môn, Khoa/Trung tâm) 1.
TS Lê Ngọc Minh, BM Hệ thống và Mạng máy tính, Khoa KH&KT MT 2. ThS Trịnh Minh Đức 3. KS Phạm Sỹ Nam, BM Hệ thống và Mạng máy tính, Khoa KH&KT MT 2 Mục Lục 1 Phát biểu vấn đề .1 Giới thiệu wireless mesh network (WMN).2 Hướng thực hiện.10 3 Kỹ thuật flooding trong định tuyến proactive .11 4 Giải thuật XL.1 Giới thiệu giải thuật XL .2 Ý tưởng của giải thuật XL.4 Hiện thực giải thuật XL.1 Chi phí kết nối .5 Các tính chất của giải thuật XL.18 5 Thiết kế giao thức định tuyến DLL-XL .1 Định dạng và chuyển tiếp gói .2 Cơ sở dữ liệu .1 Tập hợp kết nối.2 Tập hợp các nút kề .3 Tập hợp thông tin mạng của một nút chia sẻ với một nút kề .4 Tập hợp thông tin mạng của nút.5 Bảng định tuyến.6 Định dạng thông điệp TC .3 Định dạng, gửi và xử lý thông điệp HELLO .1 Định dạng thông điệp HELLO .2 Gửi thông điệp HELLO.3 Xử lý thông điệp HELLO.4 Định dạng, gửi và xử lý thông điệp TC .1 Định dạng thông điệp TC .2 Gửi thông điệp TC.3 Xử lý thông điệp TC.5 Tính toán bảng định tuyến.6 Số thứ tự .7 Quá trình khởi động một nút .27 6 Hiện thực DLL-XL trong link layer.1 Driver không dây nguyên thủy.2 Tích hợp routing protocol machine vào trình điều khiển RT2570 .3 Thiết kế và hiện thực giao diện người dùng.31 7 Đo đạc đánh giá hiệu năng của DLL-XL .1 Đóng góp của đề tài.2 Hướng phát triển .37 Tài liệu tham khảo .39 4 1 Phát biểu vấn đề Mục tiêu của đề tài là • Nghiên cứu thiết kế và hiện thực một giao thức proactive định tuyến hữu hiệu ở link layer cho mạng không dây. • Tiếp tục khảo sát nắm bắt các hướng nghiên cứu và phát triển tương lai trong lĩnh vực mạng không dây, nhất là các nội dung liên quan đến định tuyến trong link layer của mô hình OSI.
Đề tài này tiếp tục nghiên cứu công nghệ đã bắt đầu từ một đề tài NC cấp trường trong lĩnh vực định tuyến cho mạng ad-hoc không dây. Tuy nhiên trong đề tài trước đây trọng tâm đặt ở các giao thức thuộc họ on-demand. • Phát triển phần mềm mạng không dây gần với phần cứng: giao thức định tuyến proactive nhúng trong trình điều khiển thiết bị (thiết bị ở đây là usb wireless card) của lõi hệ điều hành Linux.1 Giới thiệu wireless mesh network (WMN) Mạng ad-hoc là mạng không dây không có sự điều khiển tập trung mà các nút sẽ thực hiện việc chuyển tiếp dữ liệu cho các nút khác. Việc xác định nút nào sẽ chuyển tiếp dữ liệu được xác định động dựa vào cấu trúc mạng lúc đó.
Mỗi nút cũng sẽ đóng vai trò một router và việc định tuyến cho nó là rất quan trọng. WMN có thể được ứng dụng cho nhiều kiểu hạ tầng mạng không dây khác nhau và một trong số đó là mạng không dây cục bộ WLAN. WMN có khả năng thiết lập nhanh, phủ sóng trong những khu vực khó thực hiện việc đi dây, có khả năng mở rộng và tự cấu hình để đảm bảo hiệu suất. Ngoài ra WMN còn có khả năng tăng tầm phủ sóng nhờ dùng nhiều nút để chuyển tiếp dữ liệu, giảm năng lượng sử dụng nhờ truyền với năng lượng thấp Do đó WMN thường được dùng trong những trường hợp khẩn cấp như thiên tai, chữa cháy, chống khủng bố và trong quân đội.
WMN cũng được dùng trong những trường hợp cần tiết kiệm chi phí như công ty, trường đại học. Các loại giải thuật định tuyến chính cho mạng WMN gồm có: • Định tuyến proactive Định tuyến proactive thực hiện định tuyến bằng cách định kỳ gửi thông điệp định tuyến và bảo trì đường đi trong mạng. Mỗi nút luôn giữ một danh sách các đích đến cũng như các đường đi hợp lệ. Giải thuật cần một lượng lớn thông điệp để bảo trì đường đi và tốn nhiều thời gian để tính toán lại bảng đường đi khi mạng có biến động.
Các giao thức định tuyến proactive tiêu biểu cho WMN là OLSR (Optimized Link State Routing Protocol) [3], BATMAN (The Better Approach To Mobile Ad- hoc Networking) [20] và DSDV (Destination Sequenced Distance Vector Routing) [16]. 5 • Định tuyến reactive Định tuyến reactive thực hiện định tuyến bằng cách flooding thông điệp yêu cầu định tuyến (Route Request) trong mạng. Khi một nút cần một đường đi nó sẽ gửi broadcast thông điệp RREQ đến các nút kề. Các nút kề này sau khi nhận được thông điệp RREQ sẽ broadcast tiếp thông điệp đến các nút lân cận của nó.
Quá trình này tiếp tục cho đến khi nút đích (hoặc nút trung gian có giữ đường đi đến đích) nhận được RREQ thì sẽ sinh ra thông điệp RREP trả lời và gửi ngược về cho nút có yêu cầu. Giải thuật sẽ có thời gian đáp ứng chậm khi mạng lớn và sẽ gây ra nghẽn khi có quá nhiều yêu cầu định tuyến. Các giao thức định tuyến reactive tiêu biểu cho WMN là AODV (Ad-hoc Ondemand Distance Vector) [17], và DSR (Dynamic Source Routing) [10]. • Định tuyến lai Định tuyến lai là giải thuật định tuyến kết hợp định tuyến reactive và định tuyến proactive.
Giao thức định tuyến lai tiêu biểu là HWMP (Hybrid Wireless Mesh Protocol), đây là giao tuyến định tuyến mặc định tromg mạng 802.11s và được đặc tả trong draft 802.2 Hướng thực hiện Định tuyến được hiện thực chủ yếu ở lớp ba của mô hình mạng OSI. Tuy nhiên hiện thực định tuyến ở lớp ba có một số điểm hạn chế chưa giải quyết được tốt [2]. Thực hiện định tuyến ở lớp hai của mô hình OSI có thể giải quyết được những nhược điểm trên và tăng hiệu quả việc truyền nhận. Việc thực hiện tất cả các dịch vụ của WMN ở lớp hai cũng sẽ giúp cho WMN có khả năng làm nền cho các dịch vụ ở các lớp cao hơn và kết nối với các mạng khác dễ dàng mà không cần hiện thực thêm.
Hơn nữa, qua việc hiện thực định tuyến ở lớp hai người ta còn có thể can thiệp được các thông số của mạng không dây (điều này khá quan trọng trong việc quản lý mạng không dây). Tuy nhiên, việc hiện thực định tuyến ở lớp hai sẽ khó khăn và phức tạp hơn do phải thực hiện trên nền địa chỉ vật lý và không có phân cấp địa chỉ IP như lớp ba. Ta sẽ tiến hành thiết kế một giao thức định tuyến proactive ở lớp hai của mô hình OSI cho WMN. Giải thuật XL (Approximate Link-state) [12] là một giải thuật định tuyến thuộc họ giải thuật định tuyến link-state.
Giải thuật giúp tăng hiệu quả định tuyến bằng cách giới hạn số lượng thông điệp cập nhật thông qua việc flooding có lựa chọn. Qua các kết quả mô phỏng, tác giả đã cho thấy XL hiệu quả hơn những giải thuật định tuyến thuộc họ định tuyến link-state hiện tại về thời gian đáp ứng cũng như tổng chi phí định tuyến. Tuy nhiên việc mô phỏng chỉ mới thực hiện ở mức các nút trao đổi thông điệp và tính toán bảng định tuyến. Theo chúng tôi biết, hiện vẫn chưa có hiện thực nào để kiểm tra tính hiệu quả của giải thuật XL.
WMN có những tính chất đặc trưng của mạng không dây như kết nối không ổn định, chuyển tiếp gói có lỗi đường truyền và các nút có khả năng di chuyển. Ngoài ra mỗi nút WMN có thể kết nối với nhiều nút khác mà không làm tăng chi phí kết nối nhờ sử dụng 6 sóng radio chứ không cần phải đi dây. Đây là các tính chất mà khi thiết kế giao thức định tuyến cho WMN ta cần chú ý đến. Dựa trên ý tưởng của giải thuật định tuyến XL, đề tài này thiết kế và hiện thực một giao thức định tuyến proactive hữu hiệu ở lớp hai của mô hình OSI, gọi là giao thức định tuyến DLL-XL.
Giao thức định tuyến proactive này phải phù hợp với các tính chất đặc trưng của mạng không dây và đảm bảo • Cung cấp thông tin về đường đi tối ưu ngay khi có yêu cầu (proactive). • Số lượng thông điệp cũng như kích thước thông điệp dùng để định tuyến là thấp. • Thiết kế giao thức ở lớp hai của mô hình OSI.11s [11] là bản phác thảo của một nhóm nghiên cứu thuộc tổ chức IEEE thành lập từ tháng 9 năm 2003 nhằm thiết kế một chuẩn giao tiếp cho WMN phát triển trên nền hardware 802. Bản phác thảo này đã được IEEE phê duyệt vào cuối năm 2011 [22].
Do không có sự khác biệt lớn giữa chuẩn chính thức và draft 802.11s, hơn nữa tài liệu chính thức không là miễn phí, nên trong báo cáo này chúng tôi tiếp tục dựa trên draft 802. WMN được mô tả trong draft 802.11s gồm có các thành phần sau. • Mesh Point (MP): bất kỳ thiết bị nào của chuẩn 802.11 có lớp MAC và lớp giao tiếp vật lý trong WMN và hỗ trợ các dịch vụ của WMN. • Mesh Access Point (MAP): bất kỳ một Mesh Point nào mà nó cũng là một Access Point theo chuẩn 802.
• Station (STA): các máy trạm có thiết bị giao tiếp theo chuẩn 802.11s • Mesh Link: một kết nối hai chiều theo chuẩn 802.11 giữa hai Mesh Point. • Mesh Path: một tập hợp các Mesh Link kết nối từ Mesh Point nguồn đến Mesh Point đích • Link Metric: một tiêu chuẩn dùng để đánh giá hiệu suất và chất lượng của một Mesh Link trong một Mesh Path. • Mesh Service: tập hợp các dịch vụ được cung cấp bởi WMN nhằm hỗ trợ điều khiển, quản lý và thao tác trong WMN. Hình 1 chỉ cho ta thấy các thành phần và tương tác giữa các thành phần trong WMN theo draft 802.
7 wired infrastructure MAP MP STA MAP STA MAP MP STA STA STA STA radio link mesh radio link Hình 1: Các thành phần cơ bản trong WMN theo draft 802.org/802_tutorials/06-November/802.11s_Tutorial_r5 page 19) Phạm vi thiết kế của draft 802.11s là tích hợp dịch vụ và giao thức của WMN với chuẩn không dây 802. Hình 2 cho ta thấy kiến trúc các khối chức năng của 802.
