- NGUYỄN HỒ BÁ HẢI NGUYỄN NGHIÊN CỨU GIAO THỨ THỨC C ĐỊNH TUYẾN DỰA TRÊN HƯỚNG DI CHUYỂN CỦA PHƯƠNG TIỆN CH CHO O MẠNG VANET CHUYÊN NGÀNH: KỸ THUẬT VIỄN THÔNG MÃ SỐ CHUYÊN NGÀNH: 13460526 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ GIÁO VIÊN HƯỚNG DẪN KHOA HỌC TS. - VÕ QUẾ SƠN H HỒ Ồ CHÍ MINH – 2014 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ MỤC LỤC NGHIÊN CỨU GIAO THỨC ĐỊNH TUYẾN DỰA TRÊN HƯỚNG DI CHUYỂN CỦA PHƯƠNG TIỆN CHO MẠNG VANET. - MÔ HÌNH GIAO THỨC ĐỊNH TUYẾN DỰA TRÊN HƯỚNG DI CHUYỂN CỦA PHƯƠNG TIỆN. - THỰC HIỆN ĐỀ TÀI. - 15 2 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ NGHIÊN CỨU GIAO THỨC ĐỊNH TUYẾN DỰA TRÊN HƯỚNG DI CHUYỂN CỦA PHƯƠNG TIỆN CHO MẠNG VANET I. - MỞ ĐẦU Ngày nay, một số lượng lớn các loại xe ô tô tham gia giao thông đã làm tăng lên sự quan tâm trong việc phát triển các kỹ thuật truyền thông dành cho các phương tiện xe cộ. - Với những lý do này, truyền thông vô tuyến dành cho phương tiện giao thông đã trở thành một công nghệ rất quan trọng. - Bên cạnh các kỹ thuật đã kể trên, truyền thông khoảng cách ngắn (Dedicated Short Range Communications - DSRC) đã làm cho 3 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ việc thông tin liên phương tiện (Inter-Vehicular Communications - IVC) và thông tin phương tiện – tuyến đường (Road-Vehicle Communications – RVC) trở nên khả thi trong các mạng MANET. - Chúng giống với mạng MANET với sơ đồ mạng (topology) biến đổi nhanh vì sự di chuyển ở tốc độ cao của các phương tiện. - Tuy nhiên, không giống như MANET, tính di động của các phương tiện trong VANET bị ràng buộc chung bởi các tuyến đường được định trước. - Vận tốc của phương tiện cũng được ràng buộc theo các giới hạn tốc độ, mức độ tắc nghẽn trên tuyến đường, và các cơ chế điều khiển lưu lượng (như đèn giao thông). - Thêm vào đó, các phương tiện giao thông có thể được trang bị thiết bị phát sóng khoảng cách xa hơn, nguồn năng lượng có khả năng phục hồi, và khả năng lưu trữ cao hơn. - Cùng với sự phát triển hiện tại trong lĩnh vực VANET, một số lượng các ứng dụng cho việc bố trí phương tiện đã được đưa ra. - Các hệ thống an toàn có thể phổ biến thông tin tuyến đường một cách thông minh, như các sự cố, tắc nghẽn lưu lượng thời gian thực, việc thu phí đường cao tốc, hay điều kiện mặt đường đến các phương tiện trong lân cận vị trí được đề cập. - Điều này giúp tránh việc các phương tiện bị dồn ứ và theo đó cải thiện hiệu suất sử dụng các tuyến đường. - Bên cạnh các ứng dụng an toàn đã được đề cập, việc truyền thông liên phương tiện IVC có thể được sử dụng để cung cấp các ứng dụng tiện ích, chẳng hạn như thông tin thời tiết, vị trí các trạm xăng hay nhà hàng, và các ứng dụng truyền thông tương tác như truy cập Internet, tải nhạc, và phân phối nội dung. - Mục đích của đề tài nhằm nghiên cứu về một cơ chế định tuyến dựa trên hướng di chuyển của các phương tiện giao thông để tránh việc các liên kết bị cắt đứt dẫn đến sự gián đoạn trong khi truyền thông tin. - Phạm vi của đề tài nghiên cứu áp dụng cơ chế đinh tuyến dựa trên hướng di chuyển của phương tiện vào một giao thức định tuyến hoạt động trong mạng VANET. - Phương pháp nghiên cứu của đề tài là sử dụng các công cụ mô 4 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ phỏng để thực hiện và đánh giá khả năng thi hành của giao thức định tuyến áp dụng cơ chế được đề xuất. - Một trong những vấn đề cấp thiết là việc thiết kế các giải thuật định tuyến có khả năng mở rộng, các giải thuật đó phải đủ mạnh để thích ứng với sự gián đoạn thường xuyên của các đường truyền gây ra bởi sự di chuyển của các phương tiện. - Các giao thức định tuyến được thiết kế cho MANET không phù hợp với các đặc tính riêng biệt của VANET và việc thông tin phương tiện đến phương tiện (Vehicle to Vehicle - V2V) qua mạng VANET. - Có nhiều cải tiến đáng chú ý có thể đạt được bởi việc điều chỉnh các giao thức định tuyến đó để phản ánh cấu trúc mạng biến đổi động của VANET khi bao gồm các thông tin về sự di chuyển của phương tiện như vị trí, hướng di chuyển, tốc độ, và lập bản đồ số của các tuyến đường. - Chính vì vậy, ý tưởng cơ bản của luận văn này là sử dụng thông tin trên vector vận tốc của phương tiện để tránh việc phá vỡ các tuyến thông tin và theo đó thêm vào các điều chỉnh tương ứng đến giao thức định tuyến được sử dụng. - Cụ thể trong luận văn sẽ xem xét đến trường hợp của giao thức định tuyến Destination-Sequenced Distance Vector (DSDV) [3]. - Các phương tiện được nhóm vào một số các tập hợp theo hướng di chuyển của chúng. - Các đường truyền thông được duy trì giữa các phương tiện thuộc về cùng nhóm. - Nếu một nút định tuyến trung gian thây đổi hướng di chuyển và thuộc về một nhóm khác. - Để tránh sự gián đoạn các kết nối và để thiết lập các tuyến tin cậy, giải thuật định tuyến tìm kiếm tuyến ổn định nhất gồm chỉ các nút thuộc về cùng một nhóm. - Cơ chế này được gọi là Giao Thức Định Tuyến Dựa Trên Hướng Di Chuyển Của Phương Tiện (Vehicle-Heading based Routing Protocol - VHRP). - Cấu trúc của luận văn sẽ gồm 5 phần, phần đầu tiên sẽ đưa ra cho người đọc một số nền tảng kiến thức về kỹ thuật thông tin vô tuyến và mạng VANET, phần thứ 2 sẽ đề cập đến các giao thức định tuyến sử dụng trong mạng VANET và cách thức hoạt động. - Phần thứ 3 thảo luận chi tiết về giao thức định tuyến dựa trên hướng di chuyển của phương 5 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ tiện. - Phần thứ 4 sẽ tập trung vào kết quả mô phỏng, so sánh những cải tiến của giao thức định tuyến dựa trên hướng di chuyển của phương tiện trong việc giúp làm giảm khả năng phá vỡ các liên kết và làm tăng thông lượng. - Việc thiết kế sự truyền thông giữa các phương tiện một cách hiệu quả đặt ra nhiều thách thức về kỹ thuật. - Việc đảm bảo một cơ chế định tuyến ổn định và tin cậy qua mạng VANET là một bước quan trọng hướng đến thực hiện truyền thông giữa các phương tiện một cách hiệu quả. - Các nỗ lực hiện nay là nhằm áp dụng các giao thức định tuyến trong MANET đến mạng VANET. - Hiện nay, một số lượng lớn các giao thức định tuyến đã được đề xuất trong phạm vi làm việc của tổ chức “Internet Engineering Task Force” (IETF) cho việc thi hành định tuyến trong mạng MANET. - Chúng có thể được phân ra thành các loại là giao thức phản ứng (reactive), giao thức chủ động (proactive), và giao thức lai (hybrid) [4]. - Trong các giao thức định tuyến phản ứng (Reactive Routing Protocols – RRPs), việc xác định tuyến được thực hiện theo yêu cầu hoặc theo sự cần thiết cơ bản. - Các giao thức phản ứng sau đó sẽ trở nên thụ động cho đến khi các tuyến được thiết lập trở nên không còn hiệu lực hoặc bị phá vỡ. - Một vài giao thức thuộc về loại này, chẳng hạn như “Ad hoc On-Demand Distance Vector” (AODV) [5] và “Dynamic Source Routing” (DSR) [6]. - Các giao thức phản ứng phải chịu một lưu lượng điều khiển đáng kể và được ưu tiên sử dụng cho các môi trường thây đổi động trong đó mỗi nút có một vài tuyến thông tin 6 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ hoạt động. - Trong khi lưu lượng điều khiển phát sinh có thể được giảm bớt một cách thích hợp thì độ trễ thêm vào ban đầu bởi quá trình tìm kiếm tuyến thông tin đặt ra các thách thức lớn cho các giao thức phản ứng. - Vì lý do này, các giao thức phản ứng không phù hợp cho các ứng dụng nghiêm ngặt về thời gian chẳng hạn như ứng dụng hợp tác tránh va chạm (Cooperative Collision Avoidance – CCA). - Các giao thức định tuyến chủ động (Proactive Routing Protocols – PRPs), đối lập với các giao thức phản ứng, duy trì và cập nhập thông tin định tuyến giữa tất cả các nút của một mạng được đưa ra tại mọi thời điểm. - Thông tin định tuyến được lưu trữ trong các bảng khác nhau và được dựa trên lưu lượng điều khiển nhận được. - Việc tạo ra các bản tin điều khiển và tính toán các tuyến thông tin được đưa ra bởi các bảng định tuyến. - Đặc tính chính của các giao thức chủ động đó là các nút duy trì sự hiểu biết sơ đồ mạng được cập nhập định kỳ. - Trong khi việc cập nhập định kỳ các bảng định tuyến dẫn đến phí tổn điều khiển báo hiệu đáng kể, sự phục hồi ngay lập tức của các tuyến thông tin khắc phục vấn đề trễ thiết lập tuyến ban đầu trong trường hợp của các giao thức phản ứng. - Một vài giao thức tiêu biểu trong loại giao thức chủ động bao gồm Optimized Link State Routing (OLSR) [7], Hazy Sighted Link State Routing (HSLSR) [8], Topology Broadcast based on Reverse Path Forwarding (TBRPF) [9], và Destination-Sequenced Distance Vector (DSDV). - So sánh với các giao thức phản ứng, các giao thức chủ động dễ dàng thi hành hơn và đưa ra sự ổn định tương đối. - Việc áp dụng các giao thức chủ động đến môi trường có tính di động cao, một cơn bão các bản tin điều khiển được yêu cầu để duy trì một cách nhìn chính xác về sơ đồ mạng. - Do đó, các giao thức chủ động phù hợp tốt nhất cho môi trường có tính di động không cao. - Các giao thức định tuyến lai (Hybrid Routing Protocols - HRPs) kết hợp cả hai cách tiếp cận chủ động và phản ứng. - Giao thức định tuyến vùng (Zone Routing Protocol - ZRP)[10] là một ví dụ đáng chú ý. - Định tuyến bên trong các vùng (intra-zone routing) được thi hành bởi một giao 7 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ thức chủ động. - Do đó, việc định tuyến giữa các nút trong cùng một vùng sẽ không có trễ ban đầu. - Mặt khác, để tăng khả năng mở rộng của hệ thống, định tuyến giữa các vùng (inter-zone routing) được thực hiện bởi giao thức phản ứng. - Trong khi cách tiếp cận hỗn hợp đưa ra một chiến lược định tuyến hiệu quả và có khả năng mở rộng, một số lượng các vấn đề vẫn chưa được giải quyết và việc thi hành chúng không đạt được nhiều sự phổ biến trong cộng đồng nghiên cứu. - Dựa trên các khái niệm định tuyến được đề cập ở trên, một bộ các giao thức đã được đề xuất cho việc truyền thông giữa các phương tiện trong mạng VANET. - CarNet đề xuất một hệ thống định tuyến có khả năng mở rộng sử dụng chuyển tiếp địa lý và dịch vụ xác định vị trí phân tán có khả năng mở rộng để định tuyến các gói tin từ phương tiện đến phương tiện mà không tràn ngập mạng [12]. - Để tránh sự gián đoạn liên kết trong khi truyền dữ liệu, một giao thức định tuyến dựa trên dự đoán sự di chuyển (Movement Prediction based Routing - MOPR) đã được đề xuất trong [13]. - MOPR dự đoán vị trí tương lai của phương tiện và ước lượng thời gian cần cho việc truyền dữ liệu để quyết định xem một tuyến truyền dẫn có bị phá vỡ hay không trong suốt thời gian truyền dữ liệu. - Việc thi hành cơ chế này phụ thuộc rất lớn vào sự dự đoán chính xác và ước lượng thời gian truyền mà theo đó phụ thuộc vào một vài hệ số như tình trạng nghẽn mạng, cách xử lý của tài xế, và các giao thức truyền dẫn được sử dụng. - Hiện tại trong các giao thức định tuyến, các bản tin điều khiển trong các giao thức chủ động và phản ứng không được sử dụng để dự đoán sự phá vỡ liên kết. - Quá trình duy trì một tuyến trong cả hai kiểu giao thức được bắt đầu chỉ sau khi một sự phá vỡ liên kết đã xảy ra. - Trong khi luận văn này sẽ đề cập đến việc sử dụng thông tin về hướng di chuyển của phương tiện để dự đoán khả năng xuất hiện sự phá vỡ liên kết trước khi nó xảy ra. - Các phương tiện lưu thông trên các tuyến đường được phân thành các nhóm dựa trên hướng di chuyển của chúng. - Các phương tiện có khả năng tự nhận biết nhóm mà chúng thuộc về. - Do đó, các phương tiện lưu thông trên một khu vực có thể tự hình thành các nhóm di chuyển, điều này giúp cho các giao thức định tuyến có thể thích nghi với sự thây đổi nhanh của sơ đồ mạng. - 8 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ Phương tiện sẽ liên tục cập nhập nhóm mà nó thuộc về đến các phương tiện xung quanh. - Một liên kết giữa hai phương tiện thuộc về hai nhóm khác nhau đươc xem xét là không ổn định. - Một giao thức định tuyến Ad-hoc sẽ được điều chỉnh để thực hiện các cơ chế đã đề cập ở trên. - Trong trường hợp của luận văn này sẽ xem xét đến giao thức DSDV. - MÔ HÌNH GIAO THỨC ĐỊNH TUYẾN DỰA TRÊN HƯỚNG DI CHUYỂN CỦA PHƯƠNG TIỆN Trong phần này mô tả thiết kế then chốt và các đặc tính riêng biệt được kết hợp trong cơ chế được đề xuất. - Trong khi VHRP có thể được thực hiện trên một giao thức định tuyến bất kỳ, trong luận văn này giao thức được chọn là DSDV. - Hình 1 diễn tả tình huống của năm phương tiện tại một giao lộ nơi xe B rẽ vào một con đường mới và bốn xe còn lại tiếp tục đi thẳng trên cùng một tuyến đường. - Phần tiếp theo của đề cương sẽ giải thích cách thức lựa chọn có thể được thực hiện sử dụng thông tin trên vector vận tốc của phương tiện. - Trong cơ chế được đề xuất, các phương tiện được nhóm vào trong bốn nhóm khác nhau dựa trên vector vận tốc của chúng. - Phân nhóm các phương tiện dựa trên vector vận tốc. - Các phương tiện được được giả định được trang bị hệ thống định vị toàn cầu GPS để xác định vị trí địa lý của chúng. - Giả sử vector vận tốc của phương tiện được biểu diễn trong hệ trục tọa độ Cartesian là (vx, vy). - Thực hiện nhân vector vận tốc với bốn vector đơn vị, nếu kết quả phép nhận với vector đơn vị nào đạt giá trị cực đại thì phương tiện sẽ được quyết định thuộc về nhóm đó. - Trong các mạng Ad-hoc, việc định tuyến được dựa trên thông tin chứa đựng trong bản tin “Route Update” được trao đổi định kỳ giữa các nút kế cận. - Khi một phương tiện nhận được một bản tin điều khiển từ một phương tiện khác. - Phương tiện đó sẽ so sánh ID của nhóm của phương tiện gửi bản tin đó với nhóm của chính nó. - Nếu hai phương tiện thuộc về hai nhóm khác nhau, liên kết giữa chúng sẽ được xem xét là không 10 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ ổn định. - Khi đó một hệ số đánh giá sẽ được thêm vào metric định tuyến giữa hai phương tiện và các tuyến được cập nhập. - Theo cách thức này, hệ số đánh giá được thêm vào có thể phản ánh thông tin của các nhóm trong quá trình định tuyến. - Sơ đồ giải thuật quá trình cập nhập bảng định tuyến. - Sử dụng công cụ mô phỏng Veins [14] là một chương trình khung (framework) cho mô phỏng truyền thông liên phương tiện IVC mã nguồn mở. - 11 ĐỀ CƯƠNG LUẬN VĂN THẠC SĨ Các chuyển động của phương tiện được thực hiện trên SUMO và được phản ánh thành chuyển động của các nút trong một mô phỏng OMNeT. - Ngôn ngữ XML được sử dụng để khai báo các luồng giao thông trên SUMO và ngôn ngữ lập trình C++ được dùng để thực hiện các giải thuật định tuyến cho các nút trên OMNeT. - Các phương tiện đang di chuyển sẽ thực hiện thông tin liên lạc với các trạm phát sóng được bố trí tại các vị trí trên sơ đồ mạng. - Quá trình mô phỏng nhằm đánh giá thông lượng mạng và tỉ lệ mất gói tương ứng với các tốc độ tối đa của các luồng xe khi sử dụng cơ chế được đề xuất so với khi sử dụng giao thức DSDV không hỗ trợ cơ chế VHRP. - KẾT LUẬN Luận văn này nhằm nghiên cứu giao thức định tuyến dựa trên hướng di chuyển của phương tiện cho mạng VANET. - Ý tưởng cơ bản trong cơ chế được đề xuất là nhóm các phương tiện tương ứng theo các vector vận tốc. - Hệ thống có thể dự đoán khả năng phá vỡ của một tuyến thông tin khi nó được thiết lập giữa hai phương tiện từ hai nhóm khác nhau. - Để tránh sự gián đoạn liên kết và theo đó đảm bảo các tuyến ổn định cho truyền thông, các tuyến thông tin giữa các phương tiện từ cùng một nhóm được ưu tiên lựa chọn. - Đối với mục đích này, các hệ số đánh giá được thêm vào các số đo định tuyến (metrics) của các liên kết được thiết lập giữa các phương tiện giữa các nhóm khác nhau. - Việc thi hành của cơ chế được đề xuất được đánh giá thông qua mô phỏng và được so sánh với cơ chế định tuyến chủ động là DSDV