Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015<br />
<br />
ĐÁNH GIÁ NĂNG LỰC GIAO THỨC ĐỊNH TUYẾN CỦA MẠNG<br />
KHÔNG DÂY TRONG HỆ THỐNG GIAO THÔNG THÔNG MINH<br />
Ths. Nguyễn Tuấn Anh1, TS. Đinh Văn Dũng1, KS. Đỗ Thế Chuẩn1, Ths. Ngô Mạnh Dũng1, Ths. Lê Ngọc Hưng2<br />
1<br />
<br />
Viện Công nghệ Thông tin, Đại học Quốc gia Hà Nội<br />
2<br />
<br />
Công ty VKX,Tập đoàn VNPT<br />
<br />
TÓM TẮT - Phương pháp định tuyến của mạng không dây trong hệ thống giao thông thông minh (ITS) là vấn đề được giới<br />
nghiên cứu quan tâm trong những năm gần đây. Sự hạn chế về tài nguyên của nút mạng là thách thức nhằm tìm ra các giải pháp<br />
nhằm giảm thiểu sự tiêu hao năng lượng, yêu cầu về bộ nhớ và độ phức tạp của chức năng định tuyến. Nhiều giải pháp định tuyến<br />
được đề xuất cho mạng truyền thông đặc thù này. Nhóm nghiên cứu đã xây dựng môi trường mô phỏng tích hợp các phần mềm mô<br />
phỏng như: NS-2, MOVE, SUMO để đánh giá năng lực các giao thức trên theo tiêu chí như thông lượng gói tin và trễ gói tin. Bài<br />
báo trình bày kết quả đánh giá một số giao thức định tuyến như AODV, DSR và DSDV bằng phương pháp mô phỏng theo 2 kịch<br />
bản: trong mạng không dây nói chung và áp dụng trong hệ thống giao thông thông minh. Kết quả mô phỏng đã làm rõ khả năng của<br />
các giao thức định tuyến này khi được sử dụng trong hệ thống giao thông thông minh.<br />
Từ khóa - AODV; DSDV; DSR; VANET; ITS.<br />
<br />
I. MẠNG KHÔNG DÂY VÀ HỆ THỐNG GIAO THÔNG THÔNG MINH<br />
Vehicular Ad Hoc Network (VANET) là mạng truyền thông trong hệ thống giao thông thông minh, kết nối các<br />
đầu cuối trên phương tiện giao thông qua mạng không dây như IEEE 802.11, 3G và 4G [1]. Mạng không dây được sử<br />
dụng trong hệ thống ITS như ở Hình 1. Với VANET, ITS sử dụng công nghệ cho phép thực hiện các ứng dụng liên<br />
quan đến xe cộ, phương tiện giao thông, người điều khiển, hành khách tham gia giao thông và cả người đi bộ. ITS với<br />
mục tiêu là điều phối, sắp xếp hoạt động của xe cộ, phương tiện giao thông, cung cấp và các thông tin giao thông cho<br />
người điều khiển xe cộ, cùng với các ứng dụng thuận tiện cho hành khách.<br />
Để phục vụ toàn bộ các ứng dụng cũng như các yêu cầu của hệ thống giao thông thông minh, cần có một hạ<br />
tầng mạng không dây kết nối với các phương tiện giao thông cũng như các giao thức định tuyến [2]. Kiến trúc mạng<br />
VANET bao gồm các thành phần sau:<br />
− Thiết bị đầu cuối được gắn trên phương tiện giao thông (OBE);<br />
− Trạm thu phát ở dọc đường (RSE);<br />
− Nút mạng cung cấp dịch vụ (SDN);<br />
− Trung tâm điều hành (ENOC).<br />
Ngoài ra còn có hạ tầng viễn thông được tích hợp và sử dụng cho các ứng dụng cụ thể.<br />
<br />
Hình 1. Mạng không dây trong hệ thống ITS. [3]<br />
<br />
ĐÁNH GIÁ NĂNG LỰC GIAO THỨC ĐỊNH TUYẾN CỦA MẠNG KHÔNG DÂY TRONG HỆ THỐNG GIAO THÔNG THÔNG MINH<br />
<br />
145<br />
<br />
II. GIAO THỨC ĐỊNH TUYẾN<br />
A. Giao thức DSDV<br />
DSDV (Destination-Sequenced Distance-Vector Routing) là dựa trên thuật toán Distance vector. Giao thức này<br />
được xây dựng dựa theo tiêu chí giữ nguyên sự đơn giản của giải thuật Bellman-Ford và loại bỏ vấn đề vòng lặp. [4]<br />
Truyền thông tin định tuyến: Thông tin định tuyến được gửi quảng bá (broadcast) tới tất cả các nút liền kề nó.<br />
Thông tin cập nhật được phát định kỳ hoặc ngay khi có các thay đổi xảy ra trong mạng. Để tránh lặp, định tuyến DSDV<br />
gắn số thứ tự chẵn cho mỗi đường. Số thứ tự được gắn bởi nút đích, được gửi trong gói tin cập nhập. Số thứ tự này cho<br />
thấy độ mới của mỗi đường, đường nào có số thứ tự cao hơn được xem là tốt hơn.<br />
Số thứ tự này sẽ tăng lên một đơn vị khi một nút mạng phát hiện đường đi tới đích có liên kết bị hỏng khi nó<br />
không nhận được cập nhật định kỳ. Khi ấy, trong gói tin cập nhật kế tiếp, sẽ quảng bá đường tới đích này có số chặng<br />
bằng vô hạn (Metric ~ ∞) và tăng thứ tự đường.<br />
Khi một nút nhận được thông tin mới về một tuyến đường, tuyến này sẽ được chọn nếu nó có số thứ tự lớn hơn<br />
các số thứ tự khác của cùng tuyến đó trong bảng định tuyến. Nếu nó có cùng số thứ tự, thì nó sẽ được chọn nếu có số<br />
chặng tốt hơn.<br />
Để làm giảm kích thước gói tin cập nhập, DSDV sử dụng hai loại bản tin cập nhật là:<br />
- Full dump: Cập nhật đầy đủ. Bản tin điệp này bao gồm toàn bộ thông tin định tuyến mà nút đó biết đến thời<br />
điểm đó.<br />
- Incremental dump: cập nhật bổ sung. Bản tin này chỉ bao gồm các thông tin về những thay đổi từ lần cập nhật<br />
đầy đủ gần nhất.<br />
Hai loại bản tin cập nhật này được lưu vào hai bảng khác nhau, một bảng để chuyển tiếp các gói tin đầy đủ, một<br />
để phát các gói tin cập nhật. Gói tin cập nhật đầy đủ chỉ được phát thường xuyên khi các nút thường xuyên di chuyển,<br />
khi mạng ít thay đổi, chủ yếu chỉ có gói tin cập nhật bổ sung được gửi đi.<br />
B. Giao thức định tuyến dựa vào Vector khoảng cách theo yêu cầu AODV<br />
AODV (Ad Hoc On-Demand Distance Vector) là giao thức dựa vào thuật toán Vector khoảng cách. AODV tối<br />
thiểu hoá số bản tin quảng bá cần thiết bằng cách tạo ra các tuyến trên cơ sở theo yêu cầu, ngược với việc duy trì một<br />
danh sách hoàn chỉnh các tuyến như ở thuật toán DSDV (xem Hình 2). [5]<br />
<br />
Hình 2. Quá trình khám phá tuyến trong AODV [6]<br />
Khi một nút nguồn muốn gởi một bản tin đến một nút đích nào đó và không biết rằng đã có một tuyến đúng đến<br />
đích đó, nó phải khởi đầu một quá trình khám phá đường truyền. Nó phát quảng bá một gói yêu cầu tuyến (RREQ) đến<br />
các nút lân cận. Các nút lân cận này sau đó sẽ chuyển tiếp gói yêu cầu đến nút lân cận khác của chúng. Quá trình cứ<br />
tiếp tục như vậy cho đến khi có một nút trung gian nào đó xác định được một tuyến “đủ tươi” để đạt đến đích. AODV<br />
sử dụng số thứ tự đích để đảm bảo rằng tất cả các tuyến không lặp và chứa hầu hết thông tin tuyến hiện tại. Mỗi nút<br />
duy trì số tuần tự của nó cùng với một ID quảng bá. ID quảng bá được tăng lên mỗi khi nút khởi đầu một RREQ, và<br />
cùng với địa chỉ IP của nút, xác định duy nhất một RREQ. Cùng với số tuần tự và ID quảng bá, nút nguồn bao gồm<br />
trong RREQ hầu hết số tuần tự hiện tại của đích mà nó có. Các nút trung gian có thể trả lời RREQ chỉ khi nào chúng có<br />
một tuyến đến đích mà số tuần tự đích tương ứng lớn hơn hoặc bằng số tuần tự chứa trong RREQ.<br />
Trong suốt quá trình chuyển tiếp RREQ, các nút trung gian ghi vào Bảng định tuyến của chúng địa chỉ của các<br />
nút lân cận từ khi nhận được bản sao đầu tiên của gói quảng bá, theo đó thiết lập được một đường dẫn theo thời gian.<br />
Nếu các bản sao của cùng một RREQ được nhận sau đó, các gói này sẽ bị huỷ bỏ. Một khi RREQ đã đạt đến đích hay<br />
một nút trung gian với tuyến “đủ tươi”, nút đích (hoặc nút trung gian) đáp ứng lại bằng cách phát đơn phương một gói<br />
đáp ứng tuyến (RREP) ngược về nút lân cận mà từ đó nó thu được RREQ. Khi RREP được định tuyến ngược theo<br />
đường dẫn, các nút trên đường dẫn đó thiết lập các thực thể tuyến chuyển tiếp trong Bảng định tuyến của chỉ nút mà nó<br />
nhận được RREP. Các thực thể tuyến chuyển tiếp này chỉ thị tuyến chuyển tiếp tích cực. Cùng với mỗi thực thể tuyến<br />
là một bộ định thời tuyến có nhiệm vụ xoá các thực thể nếu nó không được sử dụng trong một thời hạn xác định. Do<br />
một RREP chuyển tiếp trên đường dẫn được thiết lập bởi một RREQ nên AODV chỉ hỗ trợ việc sử dụng đường truyền<br />
đối xứng.<br />
<br />
146<br />
<br />
Ths. Nguyễn Tuấn Anh, TS. Đinh Văn Dũng, KS. Đỗ Thế Chuẩn, Ths. Ngô Mạnh Dũng<br />
<br />
Trong AODV, các tuyến được duy trì điều kiện như sau: Nếu một nút nguồn chuyển động, nó phải khởi động lại<br />
giao thức khám phá tuyến để tìm ra một tuyến mới đến đích. Nếu một nút trên tuyến chuyển động, nút lân cận luồng<br />
lên của nó chú ý đến chuyển động đó và truyền một bản tin “Khai báo sự cố đường thông” (một RREP không xác định)<br />
đến mỗi nút lân cận tích cực luồng lên để thông báo cho các nút này xoá phần tuyến đó. Các nút này thực chất truyền<br />
một “Thông báo sự cố đường thông” đến các nút lân cận luồng lên. Quá trình cứ tiếp tục như vậy cho đến khi đạt đến<br />
nút nguồn. Nút nguồn sau đó có thể chọn khởi động lại một quá trình khám phá tuyến cho đích đó nếu một tuyến vẫn<br />
cần thiết.<br />
Ngoài ra, giao thức này sử dụng bản tin HELLO được phát quảng bá định kỳ bởi một nút để thông báo cho tất<br />
cả các nút khác về những nút lân cận của nó. Các bản tin HELLO có thể được sử dụng để duy trì khả năng kết nối cục<br />
bộ của một nút. Tuy nhiên, việc sử dụng bản tin HELLO là không cần thiết. Các nút lắng nghe việc truyền lại gói dữ<br />
liệu để đảm bảo rằng vẫn đạt đến chặng kế tiếp. Nếu không nghe được việc truyền lại như thế, nút có thể sử dụng một<br />
trong số các kỹ thuật, kể cả việc tiếp nhận bản tin HELLO. Các bản tin HELLO có thể liệt kê các nút khác mà từ đó nút<br />
di động đã nghe tin báo, do đó tạo ra khả năng liên kết lớn hơn cho mạng.<br />
C. Giao thức định tuyến nguồn động DSR<br />
Giao thức DSR (Dynamic Source Routing) là một giao thức định tuyến phản ứng từ nút nguồn. Trong đó, các<br />
nút di động cần duy trì bộ nhớ đệm về tuyến chứa các nút nguồn mà nút di động nhận biết được. Các thực thể trong bộ<br />
nhớ đệm về tuyến được cập nhật liên tục (xem Hình 3). [7][8][9]<br />
<br />
Hình 3. Định tuyến nguồn động (DSR) [8]<br />
Giao thức này bao gồm 2 giai đoạn chính: a) Khám phá tuyến và b) Duy trì tuyến. Khi một nút di động gởi một<br />
gói đến một nút đích nào đó, trước hết nó phải tham vấn bộ nhớ đệm tuyến để xác định là nó đã có một tuyến để đến<br />
đích chưa. Nếu nó có một tuyến chưa hết hiệu lực để đến đích, nó sẽ sử dụng tuyến này để gởi gói đi. Trái lại, nếu<br />
không có một tuyến như thế, nó phải khởi đầu một quá trình khám phá tuyến bằng cách phát quảng bá một gói yêu cầu<br />
tuyến. Bản tin yêu cầu này chứa địa chỉ đích, cùng với địa chỉ nút nguồn và số nhận dạng duy nhất. Mỗi nút nhận được<br />
gói này sẽ tiến hành kiểm tra là nó có biết một tuyến nào để đến đích không. Nếu không, nó thêm địa chỉ của nó vào<br />
Bảng ghi định tuyến của gói và sau đó chuyển tiếp gói trên các đường truyền ngõ ra. Để giới hạn số yêu cầu tuyến phát<br />
trên các đường truyền ngõ ra của nút, một nút chỉ chuyển tiếp yêu cầu tuyến nếu nó chưa biết yêu cầu đó và nếu địa chỉ<br />
của nút di động chưa xuất hiện trong Bảng định tuyến. Một đáp ứng tuyến được tạo ra khi hoặc là yêu cầu tuyến đạt<br />
đến đích hoặc là khi nó đạt đến một nút trung gian chứa trong bộ nhớ đệm tuyến của nó một tuyến đến đích chưa hết<br />
hiệu lực. Đến lúc gói có thể đạt đến đích hay đến một nút trung gian như thế, nó chứa một bảng định tuyến cho biết số<br />
tuần tự chặng đã trải qua.<br />
Nếu nút tạo ra đáp ứng tuyến là đích thì nó đặt bảng định tuyến chứa trong yêu cầu tuyến vào đáp ứng tuyến.<br />
Nếu nút tương ứng là một nút trung gian, nó gắn thêm tuyến trong bộ nhớ đệm của nó vào bảng định tuyến và sau đó<br />
tạo ra một đáp ứng tuyến. Để trả về đáp ứng tuyến, nút tương ứng phải có một tuyến để khởi đầu. Nếu nó có một tuyến<br />
để khởi đầu trong bộ nhớ đệm tuyến của nó, nó có thể sử dụng tuyến đó. Trái lại, nếu các đường truyền đối xứng được<br />
hỗ trợ, nút có thể khởi đầu một quá trình khám phá tuyến của nó và tiếp tục gởi đi đáp ứng tuyến trên một yêu cầu<br />
tuyến mới.<br />
Việc duy trì tuyến được hoàn thành thông qua sử dụng các gói lỗi tuyến và các bản tin xác nhận. Các gói lỗi<br />
tuyến được tạo ra ở một nút khi lớp liên kết dữ liệu gặp sự cố đường truyền. Nút nguồn luôn luôn bị dừng khi một<br />
tuyến bị cắt đứt (có một liên kết trên tuyến bị lỗi). Khi nhận được một gói lỗi tuyến, chặng bị lỗi sẽ bị loại bỏ khỏi bộ<br />
nhớ đệm tuyến của nút và tất cả các tuyến chứa chặng này đều bị cắt ở điểm đó. Ngoài các bản tin lỗi tuyến, các bản tin<br />
xác nhận được sử dụng để xác minh sự hoạt động chính xác của các đường thông tuyến. Các bản tin xác nhận như thế<br />
bao gồm cả xác nhận thụ động (khi nút di động có thể theo dõi việc chuyển tiếp gói ở chặng kế tiếp trên tuyến)<br />
<br />
ĐÁNH GIÁ NĂNG LỰC GIAO THỨC ĐỊNH TUYẾN CỦA MẠNG KHÔNG DÂY TRONG HỆ THỐNG GIAO THÔNG THÔNG MINH<br />
<br />
147<br />
<br />
III. ĐÁNH GIÁ GIAO THỨC ĐỊNH TUYẾN DSDV, AODV VÀ DSR BẰNG MÔ PHỎNG<br />
A. Xây dựng môi trường mô phỏng<br />
Nhóm nghiên cứu đã xây dựng môi trường mô phỏng tích hợp các phần mềm mô phỏng MOVE, SUMO và NS2<br />
để đánh giá các giao thức định tuyến trong mạng giao thông thông minh (xem Hình 4).<br />
<br />
Hình 4. Quy trình mô phỏng mạng không dây trong ITS.<br />
• NS-2 (The Network Simulator): là phần mềm mô phỏng mạng được phát triển tại LBNL (Lawrence Berkeley<br />
National Laboratory). NS2 dùng để mô phỏng các giao thức mạng. Nó cung cấp hỗ trợ đáng kể cho mô phỏng giao<br />
thức TCP/IP, định tuyến và các giao thức Multicast trên mạng có dây và không dây.[10]<br />
• SUMO (Simulation of Urban Mobility): là phần mềm chuyên mô phỏng giao thông đường bộ trong thành phố,<br />
cho phép xây dựng một hệ thống giao thông tùy chỉnh hoặc nhập từ một bản đồ thực tế. Phần mềm sẽ đưa ra cái nhìn<br />
trực quan về hệ thống giao thông được mô phỏng. [11]<br />
• MOVE (MObility model generator for VEhicular networks): là công cụ sử dụng khá dễ dàng để nhanh chóng<br />
mô phỏng VANET. MOVE là phần mềm chạy trên nền Java và được xây dựng trên một mã nguồn mở. Bằng cách cung<br />
cấp một tập hợp các giao diện đồ họa, MOVE cho phép người dùng nhanh chóng tạo ra các kịch bản mô phỏng thực tế.<br />
Đầu ra của MOVE là một tập tin dạng TRACE chứa thông tin về giao thông và kịch bản giao thông xe. Từ tập tin<br />
TRACE có thể truy xuất ra để mô phỏng bẳng phần mềm NS-2 và SUMO. [12]<br />
<br />
B. Đánh giá giao thức DSDV, AODV và DSR trong mạng không dây.<br />
Nghiên cứu dưới đây đưa ra một phân tích định lượng thực tế so sánh hiệu suất của các loại giao thức định<br />
tuyến không dây khi áp dụng cho thông tin liên lạc. Nó cho thấy hiệu suất tương đối của ba giao thức định tuyến được<br />
đề xuất cho mạng không dây là: DSDV, AODV và DSR.<br />
Các giao thức này được đánh giá trong mạng không dây và kết quả mô phỏng được trình bày ở Hình 5 và Hình<br />
6. Kết quả mô phỏng cho thấy, khi mạng vào trạng thái ổn định, giao thức AODV có thông lượng cao nhất (tỷ lệ số gói<br />
tin nhận/ truyền) so với DSDV và DSR. So sánh về thời gian trễ trung bình, giao thức DSDV có thời gian trễ trung<br />
bình nhỏ hơn DSR và AODV.<br />
<br />
148<br />
<br />
Thời gian trễ trung bình (s)<br />
<br />
ĐÁNH GIÁ NĂNG LỰC GIAO THỨC ĐỊNH TUYẾN CỦA MẠNG KHÔNG DÂY TRONG HỆ THỐNG GIAO THÔNG THÔNG MINH<br />
<br />
Thời gian mô phỏng (s)<br />
<br />
Hình 6. Thời gian trễ trung bình của DSDV/AODV/DSR<br />
<br />
Hình 5. Tỉ lệ số gói tin nhận/truyền của<br />
DSDV/AODV/DSR<br />
C. Đánh giá giao thức AODV trong mạng VANET<br />
<br />
Kịch bản sẽ mô phỏng số lượng 100 xe chạy liên tiếp nhau trên đường và đánh giá khả năng truyền thông tin<br />
giữa các xe với nhau. Các thông số và giá trị mô phỏng được miêu tả ở Bảng 1.<br />
Bảng 1. Cấu hình mô phỏng<br />
Thông số<br />
Đường truyền<br />
Giao diện vật lý<br />
Giao thức định tuyến<br />
Kích thước mô phỏng<br />
Thời gian mô phỏng<br />
Giao thức truyền<br />
Số làn đường<br />
Tốc độ xe<br />
Tiêu chuẩn mạng không dây<br />
<br />
Giá trị<br />
Wireless<br />
Physical Wireless<br />
AODV<br />
1000 x 1000m2<br />
100 s<br />
TCP<br />
1<br />
40 m/s<br />
IEEE 802.11<br />
<br />
1) Kết quả mô phỏng khi không có các điểm thu phát bên đường.<br />
Thông lượng trung bình khi các xe cách nhau 300m là 550 gói/TIL (TIL là đơn vị thời gian mặc định). Với<br />
khoảng cách 500m, thông lượng trung bình xấp xỉ bằng 500 gói/TIL, song tại một số thời điểm thông lượng bị rớt đột<br />
ngột. Khi khoảng cách là 700m, thông lượng trung bình là 400 gói/TIL, song thông lượng không ổn định theo thời gian<br />
– đây là tình huống rớt đường truyền. (xem Hình 7, Hình 8 và Hình 9)<br />
<br />
Hình 7. Thông lượng với khoảng cách là 300m<br />
<br />
Hình 8. Thông lượng với khoảng cách là 500m<br />
<br />
Hình 9. Thông lượng với khoảng cách là 700m<br />
<br />