Định tuyến theo vị trí trong mạng VANET s

Nội dung text: Định tuyến theo vị trí trong mạng VANET s

1. ĐỊNH TUYẾN THEO VỊ TRÍ TRONG MẠNG VANETS LOCATION AWARE ROUTING IN THE NETWORK VANETS 1 2 Dương Thời Thế , TS. Phan Văn Ca Khoa Điện – Điện tử, Trường đại học Sư phạm Kỹ thuật TP.HCM TÓM TẮT Định tuyến theo vị trí trong mạng VANET như thế nào? (câu hỏi). Bài báo này sử dụng hệ thống VANET để giải quyết vấn đề hệ thống liên lạc bằng xe có thể tăng sự chủ động an toàn, cảnh báo về sự cố giao thông đường bộ. Mục đích cụ thể của đề tài là xây dựng mở rộng giao thức GPSR chạy trên chuẩn IEEE 802.11 cho các nút thu phát di động đồng thời khắc phục các vùng tối mạng, vật cản và sự phát vỡ liên kết trong mạng VANET. Phương pháp mô hình hóa và mô phỏng, sử dụng lớp MAC 802.11 (WiFi) với 2 giao thức định tuyến AODV, GPSR và phần mềm NS để mô phỏng, kết quả là so sánh độ trễ, tỉ lệ nhận gói tin, thông lượng đường truyền. Kết luận, định tuyến GPSR là kỹ thuật định tuyến tích hợp cho các mạng di động như VANET so với các kỹ thuật định tuyến khác. Một trong những nhược điểm của GPSR là định tuyến qua các vùng tối mạng có thể khắc phục bằng cách sử dung LANDMARK. Trường hợp khi nút đích di chuyển nhanh có thể tăng overhead, giải pháp là định tuyến theo vòng tròn đích. Hướng phát triển là phân tích đánh giá kỹ thuật định tuyến GPSR trên chuẩn 802.11g. Tuy nhiên vẫn còn một số tồn tại hạn chế là mạng VANET vẫn còn là một công nghệ mới trong vài năm gần đây ở Việt Nam và chưa có nhiều kết quả thử nghiệm, đánh giá về nó. Do đó, việc tham gia rất hạn chế, với người nghiên cứu chỉ có cách dùng mô phỏng. Từ khóa: Câu hỏi, Mục đích, Phương pháp, Kết quả, Kết luận. ABSTRACT How to route in location of VANET network? (question). This report uses VANET system to solve the problem of communications systems by car that can increase proactive safety, warning of road traffic incidents. The specific purpose of the project is to build extended GPSR running on IEEE 802.11 standard for mobile transceiver nodes and simultaneous to overcome dark networks areas, obstructions and broken links in the VANET network. Methods of modeling and simulation, using 802.11 MAC (WiFi) with two routing protocols AODV, GPSR, and NS software to simulation. Results is compare the latency, authentication packet rate, transmission throughput. Conclusion, GPSR router is integrated routing mechanism for mobile networks as VANET than other routing techniques. One of the disadvantages of GPSR is routed through the dark network areas can be overcome by using LANDMARK. In case the destination node can quickly move increased overhead, the solution is in a circular routing destination. Development is a analysis and evaluation of technical for GPSR route on 802.11g. However there are still some limitations that are VANET network is still a new technology in recent years in Vietnam and not test results yet, assessment of it. Therefore, participation is very limited, with only research using simulation. Keywords: Question, Purpose, Method, Results, Conclusion 1. GIỚI THIỆU Mạng VANET (Vehicular Ad Hoc Network) là một công nghệ sử dụng các xe di chuyển như các nút trong một mạng để tạo nên một mạng di động. VANET biến mỗi xe tham gia giao thông thành một router hay một nút không dây, cho phép các xe này có thể kết nối với các xe khác trong phạm vi bán kính từ 100 đến 300 mét, từ đó tạo nên một mạng với Hình 1. Mô hình mạng VANET vùng phủ sóng rộng. Do các xe có thể đi ra 1
2. khỏi vùng phủ sóng và thoát khỏi mạng, trong Lớp MAC (kiểm soát truy cập trung khi những xe khác có thể tham gia, kết nối bình): Một giao thức xử lý các thông điệp với các phương tiện khác trên một mạng truyền đi và cố gắng tránh va chạm tin nhắn Internet di động được tạo nên. Trong thực tế, (gửi tất cả các thông tin xe được sử dụng hệ thống đầu tiên được tích hợp công nghệ trong các ứng dụng). này là các xe của cảnh sát và lính cứu hỏa Lớp routing (lớp định tuyến): Để di nhằm liên lạc trao đổi thông tin với nhau phục chuyển một gói dữ liệu từ nguồn tới đích. vụ cho công tác cứu hộ, đảm bảo an ninh trật tự. Lớp communication regimes (chế độ truyền thông): Truyền thông tin đến các xe. 1.1 Mục tiêu và phương pháp nghiên cứu 2.2. Ứng dụng của hệ thống vanet 1.1.1 Mục tiêu Mục tiêu cụ thể của đề tài là xây dựng mở rộng giao thức GPSR chạy trên chuẩn IEEE 802.11 cho các nút thu phát di động (thu phát) đồng thời khắc phục các vùng tối, vật cản và sự phát vỡ liên kết trong mạng VANET. Sử dung công cụ NS mô phỏng hai giao thức AODV và GPSR trên chuẩn IEEE 802.11 và giao thức AODV trên chuẩn 802.15.4. Trong đề tài nghiên cứu chỉ quan Hình 3. Yêu cầu kỹ thuật phương tiện tâm đến thay đổi tốc độ nút và mật độ nút để 2.3. Mô tả chung đặc điểm của GPSR: đánh giá các tiêu chí như: Độ trễ, thông lượng và tỷ lệ nhận gói tin, sau đó đánh giá, so sánh Định tuyến dựa trên vị trí là truyền dữ kết quả và đưa ra hướng đề xuất nghiên cứu liệu tới vị trí đã được biết trước của nút mục trong tương lai. tiêu. Nếu thông tin vị trí đủ chính xác, nút mục tiêu sẽ nằm trong vị trí của khoảng vô 1.2 Khách thể và đối tượng nghiên cứu tuyến vị trí dựa trên vị trí của mục tiêu từ Khách thể: Giao thức định tuyến trong chính vị trí của nút chuyển tiếp và định tuyến mạng VANET. các nút hàng xóm của nó. Đối tượng: Sử dụng công cụ NS GPSR là một giao thức định tuyến (chu (network simulation) để mô phỏng hai giao vi phi trạng thái tham lam) và đáp ứng hiệu thức AODV và GPSR trên chuẩn IEEE quả cho điện thoại di động và mạng không 802.11 và giao thức AODV trên chuẩn IEEE dây. GPSR có thể được áp dụng cho các 802.15.4. mạng: Sensor networks, Rooftop networks, 2. MÔ HÌNH HỆ THỐNG Vehicular networks và ad-hoc networks. 2.1. Kiến trúc layers GPSR cho phép các nút để tìm ra những người hàng xóm gần nhất của nó được (sử dụng beacon) mà cũng là gần đến đích cuối Hệ thống giao tiếp xe cùng là thông tin được cho là để truyền đi. Ứng dụng Để tính toán một con đường, GPSR sử Chế độ giao tiếp dụng một thuật toán chuyển tiếp Greedy sẽ t gửi các thông tin đến đích cuối cùng bằng ậ Lớp định tuyến (Routing) n vá ậ cách sử dụng con đường hiệu quả nhất có thể. Lớp kiểm soát truy nhập m o ả Nếu việc chuyển tiếp Greedy không giao B phương tiện (MAC) đánhgiá nhận, sẽ được sử dụng các tuyến đường xung Lớp vật lý (PHY) nh Xác quanh chu vi của khu vực. Một nút chỉ phải nhớ vị trí của các nút Hình 2. Kiến trúc theo lớp mạng VANET láng giềng theo one-hop. Lớp PHY (vật lý): Để truyền tin nhắn Định tuyến có thể tự động quyết định trong mạng lưới xe với dải tần số dành riêng thực hiện. 2
3. Hình 4. Chuyển tiếp Greedy (x muốn gửi một gói tin đến D và nó sẽ chuyển tiếp một Greedy đến y) Nếu mạng đủ các nút láng giềng bên trong phạm vi góc 2Π/ 3, chuyển tiếp Greedy sẽ luôn luôn thành công. Tuy nhiên, thuật toán chuyển tiếp Greedy có thể thất bại: Hình 7. Định tuyến vòng theo vùng tối Khi một nút ở rìa của lỗ nhận các gói tin chuyển tiếp bằng cách sử dụng chu vi chuyển tiếp nó kiểm tra xem các chuyển tiếp Greedy có thể được phục hồi tại nút này hay không. Nếu có thì nó tính khoảng cách D từ chính nó vào dòng kết nối giữa các nút gốc và các điểm Hình 5. Chuyển tiếp Greedy thất bại đến ký hiệu là (l). Khi thuật toán chuyển tiếp Greedy (x x )( y y ) ( x x )( y y ) không thành, các thuật toán chuyển tiếp chu D(,) F l d b b b d b (1) 22 vi sẽ được sử dụng. ()()xd x b y d y b Áp dụng quy tắc bàn tay phải để đi qua Trong đó S (xd, yd), R (xb, yb), và F các cạnh trống và tìm thấy một con đường (x, y) là vị trí của các điểm đến, nút ROOT và bằng chu vi của cấu trúc liên kết. nút chuyển tiếp ở rìa của lỗ tương ứng. Bắt đầu Nhận gói dữu liệu (P) (P) Chế độ chuyển tiếp = Greedy Hình 6. Chuyển tiếp chu vi Y Các thuật toán chuyển tiếp chu vi sử Chuyển sang chế Greedy lỗi Độ chuyển tiếp Geendy dụng một con đường dài hơn các điểm đến vì vậy các thuật toán chu vi chuyển tiếp kém Y Thiết lập một vành đai nút Greedy chuyển Tính khoảng cách D ( F, l ) Chu vi hiệu quả và không được sử dụng một mình. gốc chuyển tiếp đ ến (P) tiếp đế n (P) chuy ển tiếp Greendy đến chuyển tiếp (P) đến (P) 3. ĐỊNH TUYẾN GPSR CHO MẠNG D>ngưỡng VANETS Y 3.1. Định tuyến vòng theo vùng tối mạng Tạo ra lỗ thăm dò (Hp) Đặt Hp.L trái = chính Hp.R phải = gốc Các gói dữ liệu từ nút nguồn được Chu vi chuyển chuyển tiếp đến nút thu phát bằng cách sử tiếp đến (Hp) dụng các thuật toán chuyển tiếp địa lý: Greedy chuyển tiếp nếu có thể và chu vi Kết thúc chuyển tiếp để đi qua các cạnh của một lỗ. Hình 8. Lược đồ giải thuật Các thăm dò lỗ chứa các các trường sau: Hp.ROOT: Trường gốc Hp.L: Trường mốc trái 3
4. Hp.R: Trường mốc phải Thăm dò này được tiếp tục đi qua cho đến khi nó đạt đến nút gốc. Khi nút gốc nhận đầu dò Trường gốc chứa ID và vị trí của nút gốc lỗ được tạo ra bởi chính nó, nó phổ biến các trong khi mốc còn lại và trường chứa các vị vị trí của các mốc vào các nút xung quanh lỗ. trí mốc trái và mốc phải. Khi thăm dò lỗ đã được tạo ra, các mốc còn lại và các mốc phải 3.2. Định tuyến thích nghi theo đối tượng được thiết lập như là vị trí của các nút chuyển di động tiếp hiện tại và nút gốc, tương ứng. Trong suốt quá trình thăm dò lỗ, những địa danh này được cập nhật bằng cách kiểm tra khoảng cách D (F, l) và S (F, L, l). Các chức năng đăng nhập S (F, L, l) được sử dụng để xác định liệu các nút chuyển tiếp thuộc về phía bên trái của lỗ hoặc bên phải của lỗ được xác định như sau: S(,,) F L l sign  ( xd x b )( y b y )( x b x )( y d y b ) (2)  (xd x b )( y b y l ) ( x b x l )( y d y b ) Trong đó L (xl, yl) là vị trí của cột mốc trái tạm thời chỉ định trong các thăm dò lỗ. Hàm đăng nhập (x) được định nghĩa như sau: Hình 10. Chọn mốc trái và gởi thẳng đến nút đến thu phát 1, x 0 sign() x Trước khi chuyển tiếp một gói tin đến 1, x 0 Dựa trên nghiên cứu tương tự như bắn Tính D ( F,l ) và D ( R,l ) một con chim bay. Ở đây, những con chim Tính D ( F, l ) Và D ( L, l ) bay tương ứng với thu phát di động, trong khi người bắn súng là nguồn. Một chiến lược khả D ( F, l ) > D ( R, l ) D ( F, I ) > D ( L,l ) thi cho người bắn súng được theo dõi chuyển Y Y Đ ặ t Hp. R = F động của các loài chim và sau đó bắn nhiều Đặt Hp. L = F đạn xung quanh chim. Khái niệm này cũng được minh họa trong hình 11 Chu vi chuy ển tiếp ( Hp) Chu vi chuyển tiếp ( Hp) Kết thúc Hình 9. Lược đồ giải thuật 4
5. ID gói thứ tự vị trí phát sóng  Các mã giả từ thu phát di động R1 R2 Hình 11. Một kịch bản cho một giải thuật R3 LAR hành trình như thế nào Thành phần chính của ý tưởng này bao gồm: Hình 14. Mã giả từ thu phát di động Một thuật toán cho việc theo dõi chuyển Tại nút cảm biến, khi một gói beacon từ động của thu phát di động; nút thu phát nhận được, kiểm tra nút cảm biến cho dù đó là các gói beacon mới. Nếu có, nó Một thuật toán để tính toán vị trí của thực hiện các thủ tục sau đây: thu phát di động; Tại mỗi nút cảm biến, một bảng đích Một chiến lược để chuyển tiếp một gói được xây dựng và duy trì. Các định dạng của tin đến thu phát di động. bảng đích được mô tả như sau: Thu Đích Vị trí Vị trí Vị trí phát tạm thời VC1 VC2 VC3 ID  Xây dựng danh sách láng giềng Hình 12. Thành phần chính của thuật Khi mạng được triển khai, mỗi node toán đề xuất thay đổi vị trí của nó và xây dựng một bảng láng giềng bằng cách sử dụng các gói tin  Xây dựng các vòng tròn xung quanh Hello để phát vị trí của nó cho nhau. Định node thu phát dạng của gói beacon được mô tả như sau: Node ID Loại gói Vị trí  Một chiến lược để chuyển tiếp gói tin đến thu phát di động Hình 13. Phát sóng thông tin vị trí của nút thu phát Các nút thu phát sử dụng gói beacon để phát sóng thông tin vị trí vào nút cảm biến. Bên cạnh những thông tin vị trí, một cờ cho biết các khu vực phát sóng nằm trong các gói Hình 15. Chuyển tiếp gói tin đến nút thu phát beacon của các nút thu phát. Định dạng của di động gói beacon được mô tả như sau: Nút Loại Số Thông tin Bán kính 5
6.  Các mã giả cho thuật toán chuyển 4.1.1.1. Độ trễ AODV tiếp Các đích tạm thời được điều chỉnh dựa trên chế độ gói và vị trí của nút cảm biến. Khi một nút nhận được một gói tin mới, nó sẽ kiểm tra xem tình trạng của đích tạm thời trong các gói tin là cũ hơn các đích tạm thời được lưu trữ trong bảng đích. Nếu có, đích tạm thời của các gói tin được cập nhật bởi các đích tạm thời được lưu trữ trong bảng đích. Nếu không, các nút chỉ chuyển tiếp các gói tin tới đích tạm thời trong tiêu đề gói tin. Chuyển tiếp Greedy tới đích tạm thời có hai thủ tục: Tìm người láng giềng càng gần đến Hình 17. Độ trễ của giao thức AODV đích; với chuẩn IEEE 802.11 Chuyển tiếp gói tin đến những người 4.1.1.2. Thông lượng AODV hàng xóm gần nhất đến đích. Mật độ node tăng thông lượng cũng tăng 3.4. Công cụ mô phỏng theo, khi thay đổi tốc độ di chuyển không làm ảnh hưởng đến thông lượng, tốc độ tăng đến 5 m/s thì thông lương của 5 node, 10 node, 15 node, 20 node gần như bằng nhau, Hình 16. Tổng quan về NS dưới góc độ người dùng 4. KẾT QUẢ Qua kết quả mô phỏng cho chúng ta thấy, ở cùng một tốc độ và thay đổi mật độ node thì độ trễ thay đổi không đáng kể và ngược lại ở cùng mật độ node, tốc độ node càng tăng thì độ trễ cũng tăng theo, điều này cho ta thấy có sự tranh chấp giữa các gói tin nên độ trễ tăng lên rõ rệt. Được thể hiện ở Hình 18.: Thông lượng của giao thức AODV hình 17 với chuẩn IEEE 802.11 4.1. Mô phỏng hai giao thức AODV và 4.1.1.3. Tỷ lệ nhận gói tin AODV GPSR với IEEE 802.11 Ở mật độ 5 node tỷ lệ nhận gói tin cao 4.1.1. Ảnh hưởng của tốc độ và mật độ node có thể ở mật độ thấp ít phá vỡ liên kết và mất giao thức định tuyến AODV gói tin, khi ở mật độ 10 node, 15 node, 20 node tỷ lệ nhận gói tin thấp hơn chênh lệch không đáng kể được thể hiện ở hình 19. 6
7. Hình 19. Tỷ lệ nhận gói tin của giao thức AODV với chuẩn IEEE 802.11 Hình 21. Thông lượng của giao thức GPSR với chuẩn IEEE 802.11 4.1.2. Ảnh hưởng của tốc độ và mật độ node giao thức định tuyến GPSR 4.1.2.3. Tỷ lệ nhận gói tin GPSR Tuy lưu lượng của giao thức GPSR thấp 4.1.2.1. Độ trễ GPSR hơn nhiều nhưng tỷ lệ nhận gói tin tương Ở giao thức GPSR khi thay đổi mật độ đương với giao thức AODV. Tranh chấp giữ node và tốc độ di chuyển node không làm ảnh các gói ít hơn. hưởng đến độ trể gói tin thể hiện ở hình 20. Hình 22. Tỷ lệ nhận gói tin của giao thức Hình 10. Độ trễ của giao thức GPSR với GPSR với chuẩn IEEE 802.11 chuẩn IEEE 802.11 Tương tự như giao thức AODV thay đổi 4.1.2.2. Thông lượng GPSR mật độ node và tốc độ di chuyển không làm Kết quả mô phỏng cho thấy thông ảnh hưởng đến thông lượng hình 4.5, tỷ lệ lượng của giao thức GPSR nhỏ hơn so với nhận gói tin lớn khi mật độ node thấp và giao thức AODV, là vì ở giao thức AODV ngược lai được thể hiện ở hình 22. thường xuyên cập nhật bảng định tuyến điều 4.2. Đánh giá kết quả mô phỏng này có nghĩa là cần một thông lượng rất lớn, Qua kết quả mô phỏng trong cùng thời còn ở GPSR khắc phục điều này thông qua gian của hai giao thức AODV và GPSR trên giải thuật phân cấp trì quản tràn ngập phát chuẩn IEEE 802.11 là 1.000 giây, kích thước sóng. gói tin 60 bytes, tốc độ dữ liệu 10 bps được lập lại 10 lần ta thấy độ trễ, thông lượng gói tin của giao thức AODV cao hơn so với GPSR. Độ trễ và thông lượng cao có thể liên kết mạng bị phá vỡ hoặc có sự tranh chấp gói 7
8. tin nhiều hơn, tỷ lệ nhận gói tin của hai giao 5.2. Hướng phát tiếp theo của đề tài thức tương đương nhau điều này có nghĩa là Ngoài việc nghiên cứu lý thuyết, sẽ tìm khi liên kết bị thất bại hoặc mất gói tin thì hiểu sâu hơn về công cụ mô phỏng ns2 để có GPSR sẽ hình thành lại định tuyến mới rất kết quả mô phỏng chính xác và đầy đủ. Đồng nhanh. thời tôi sẽ đi sâu tìm hiểu phân tích, đánh giá kỹ thuật định tuyến GPSR trên chuẩn 802.11g 5. KẾT LUẬN về khả năng triển khai mạng Vanet vào thực Định tuyến GPSR là kỹ thuật định tiễn tại Việt Nam. Trong tương lai, tôi mong tuyến tích hợp cho các mạng di động như muốn sẽ tiếp tục nghiên cứu về vấn đề này vanet so với các kỹ thuật định tuyến khác. cũng như phát triển mở rộng nó. Một trong những nhược điểm của GPSR là định tuyến qua các vùng tối có thể LỜI CẢM ƠN khắc phục bằng cách sử dung Landmark. Với lòng biết ơn sâu sắc nhất, em xin Trường hợp khi nút đích di chuyển gửi đến quý Thầy Cô ở Khoa Điện-Điện tử - nhanh có thể tăng Overhead, giải pháp là định Trường đại học sư phạm kỹ thuật thành phố tuyến theo vòng tròn đích. Hồ Chí Minh đã cùng với tri thức và tâm 5.1. Hạn chế huyết của mình để truyền đạt vốn kiến thức Mạng VANET vẫn còn là một công quý báu cho em trong suốt thời gian thực hiện nghệ mới trong vài năm gần đây ở Việt Nam đề tài. Đặc biệt, nếu không có sự hướng dẫn và chưa có nhiều kết quả thử nghiệm, đánh tận tình của thầy Tiến sĩ Phan Văn Ca thì em giá về nó. Do đó, việc tham gia rất hạn chế, nghĩ luận văn tốt nghiệp của em rất khó có với người nghiên cứu chỉ có cách dùng mô thể hoàn thiện được. phỏng. Xin chân thành cảm ơn! TÀI LIỆU THAM KHẢO [1] GPSR: Greedy Perimeter Stateless Routing for Wireless Networks of Brad Karp Harvard University / ACIRI [2] J'erome Haerri, Fethi Filali, and Christian Bonnet, "Performance Comparison of AODV and OLSR in VANETs Urban Environments under Realistic Mobility Patterns", 5th IFIP Mediterranean Ad-Hoc [3] GPSR-MV: A routing protocol based on motion vector for VANET [4] Scenario Based Performance Analysis of AODV and GPSR Routing Protocols in a VANET [5] AODV-PNT: An improved version of AODV routing protocol with predicting node trend in VANET [6] S. S. Manvi, M. S. Kakkasageri, C. V. Mahapurush, "Performance Analysis of AODV and Swarm Intelligence Routing Protocols In Vehicular Ad hoc Network Environment", 2009 International Conference on Future Computer and Communication. [7] Paul Meeneghan and Declan Delaney. “An Introduction to NS, Nam and OTcl Scripting”. National University of Ireland, Maynooth, Co. Kildare, Ireland DEPARTMENT OF COMPUTER SCIENCE. April 2004. [8] Mạng xe cộ (VANET) “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” luận văn thạc sĩ của Nguyễn Hồ Bá Hải.” Thông tin liên hệ tác giả chính (người chịu trách nhiệm bài viết): Họ tên: Dương Thời Thế Đơn vị: Sở Thông tin và Truyền thông Điện thoại: 0982300111 Email: thektvt.111@gmail.com 8
9. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2017-2018 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.