Thuật toán định tuyến cho giao tiếp V2V trong môi trường đô thị sử dụng thông tin vị trí và dự đoán chuyển động

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 17 THUẬT TOÁN ĐỊNH TUYẾN CHO GIAO TIẾP V2V TRONG MÔI TRƯỜNG ĐÔ THỊ SỬ DỤNG THÔNG TIN VỊ TRÍ VÀ DỰ ĐOÁN CHUYỂN ĐỘNG Trần Văn Hưng*, Hồ Thành Trung Tóm tắt: Định tuyến trong mạng VANET là một bài toán khó do các các nút mạng là các xe luôn di chuyển với tốc độ cao làm cấu hình mạng thay đổi liên tục. Do vậy, vấn đề quan trọng nhất là phải dự đoán được chuyển động của xe khi quyết định chọn xe đó làm nút chuyển tiếp bản tin. Bài báo này đề xuất thuật toán định tuyến cho giao tiếp V2V trong môi trường đô thị sử dụng thông tin vị trí và dự đoán chuyển động, thực hiện chọn tuyến và nút chuyển tiếp phù hợp làm nâng cao hiệu quả định tuyến. Qua phân tích lý thuyết và đánh giá bằng mô phỏng đều chứng tỏ thuật toán đưa ra đã làm tăng tỉ lệ chuyển tiếp bản tin thành công, giảm thời gian trễ trung bình đầu-cuối và làm giảm số chặng chuyển tiếp trung bình khi so sánh với một số thuật toán định tuyến đã có. Từ khóa: ITS, VANET, V2V, GMPR. 1. GIỚI THIỆU Mạng di động tùy biến các phương tiện giao thông VANET (Vehicular Ad-hoc Network) [1] là mạng vô tuyến Ad-hoc được triển khai trong môi trường giao thông với hai loại truyền thông chủ yếu đó là: giao tiếp xe-xe (V2V - Vehicle to Vehicle) và giao tiếp xe-hạ tầng (V2I - Vehicle to Infrastructure), với các kỹ thuật để đảm bảo cho các giao tiếp này đã được đề xuất và tiêu chuẩn hóa như trong IEEE 802.11 và WAVE (Wireless Access in Vehicle Environments) [2]. Việc triển khai các ứng dụng trên VANET gặp nhiều khó khăn thách thức do các nút mạng là các phương tiện luôn di chuyển với tốc độ cao, dẫn tới cấu trúc mạng thay đổi không ngừng và luôn xảy ra các hiệu ứng không mong muốn trong thông tin như: fading, doppler, trễ truyền dẫn, v.v... nhất là trong môi trường đô thị khi đường truyền vô tuyến thường xuyên bị gián đoạn do hiệu ứng che chắn bởi các tòa nhà. Chức năng chính của giao thức định tuyến ở môi trường này là tìm, chọn đường tối ưu và chuyển bản tin đến đúng đích thông qua các nút mạng trung gian trong điều kiện topo mạng biến đổi liên tục. Nhiều nghiên cứu đã khẳng định, các giao thức định tuyến truyền thống hoạt động dựa trên bảng định tuyến hoàn toàn không phù hợp với môi trường VANET. Các giao thức định tuyến theo yêu cầu mà điển hình như AODV (Ad-hoc On Demand Distance Vector Routing) [3] hay DSR (Dynamic Source Routing) [4] không thể phát huy được hiệu quả do trễ lớn. Các giao thức định tuyến dựa trên thông tin vị trí như GPSR (Greedy Perimeter Stateless Routing) [5], LAR (Location Aided Routing) [6] hay GSR (Geographic Source Routing) [7] đã khắc phục được một số nhược điểm cơ bản của giao thức dựa trên bảng định tuyến, tuy nhiên, cũng chưa có cơ chế dự đoán chuyển động của các xe lân cận khi chọn nút trung gian chuyển tiếp bản tin. Bài báo này đề xuất thuật toán định tuyến cho giao tiếp V2V trong môi trường đô thị, sử dụng thông tin vị trí kết hợp với dự đoán hướng chuyển động của phương tiện GMPR (Geography-Movement Prediction based Routing Algorithm). Kỹ thuật điều khiển & Điện tử T. V. Hưng, H. T. Trung, “Thuật toán định tuyến cho giao tiếp V2V chuyển động.” 18 Thuật toán đã cải thiện được các hạn chế của thuật toán định tuyến dựa trên thông tin vị trí, cụ thể: xác định được quãng đường đến đích ngắn nhất cho bản tin sự kiện trong mối tương quan với yếu tố mật độ phương tiện trên đường; dự đoán chuyển động của các xe lân cận trong vùng phủ sóng để chọn ra xe đóng vai trò là nút chuyển tiếp trung gian có lợi nhất về thời gian khi chuyển tiếp bản tin. Các giả định về hệ thống bao gồm: tất cả các phương tiện đều được trang bị thiết bị thu phát vô tuyến phù hợp tiêu chuẩn IEEE 802.11(p) DSRC/WAVE, thiết bị định vị (GPS) và thiết bị cảm biến để sẵn sàng cung cấp các dữ liệu về trạng thái phương tiện như vị trí, tốc độ và hướng di chuyển. Phần 2 của bài báo phân tích chi tiết về thuật toán GMPR. Cách thức thử nghiệm và đánh giá thuật toán đưa ra được trình bày trong phần 3 và cuối cùng là phần kết luận. 2. GIAO THỨC GMPR TRONG MÔI TRƯỜNG ĐÔ THỊ 2.1. Xác định vị trí xe thông qua bản tin cập nhật trạng thái Trong VANET có hai loại bản tin, đó là: bản tin an toàn thông thường và bản tin sự kiện. Bản tin an toàn thông thường hay còn gọi là bản tin cập nhật trạng thái cung cấp các thông tin về trạng thái của phương tiện như vị trí, tốc độ, hướng di chuyển, v.v, được quảng bá với tần suất từ 2~10 lần/giây. Bản tin sự kiện hay còn gọi là bản tin cảnh báo khẩn cấp nhằm cảnh báo các nguy cơ có thể dẫn đến tai nạn giao thông như sự cố động cơ, phanh gấp, chuyển làn đột ngột, v.v. Bản tin sự kiện chỉ được phát đi khi phương tiện rơi vào trạng thái nguy hiểm. Trong bài báo này, bản tin cập nhật trạng thái được sử dụng để xác định vị trí và dự đoán chuyển động của các nút mạng là các phương tiện phục vụ cho thao tác định tuyến. Gọi S={sj|j=1,2,3,...,k} là tập các nút gửi, Nj={ni|i=1,2,3,...,m} là tập các nút lân cận trong vùng phủ của nút gửi sj tương ứng. Nút sj định kỳ nhận được bản tin trạng thái đến từ các nút lân cận, bản tin này chứa các thông tin về các nút lân cận ni ở thời điểm hiện tại (tcur) như: vị trí ur ur ur( , ) i i in n n c c cP x y , tốc độ ur in cv , gia tốc ur in ca và góc hướng ur in c . Nút gửi sj di chuyển với vận tốc ur is cv , gia tốc ur is ca với góc hướng ur is c ở tại vị trí ur ur ur( , ) i i is s s c c cP x y có thể tính được vị trí của ni tại thời điểm tương lai tpred (tpred= tcur+Δt) là ( , )i i i n n n pred pred predP x y với các tọa độ được xác định: 2 ur 2 ur 1 2 1 2 i i i i i i i i n n n n pred c x x n n n n pred c y y x x v t a t y y v t a t           (1) Với ur ur max0 , i in s c cv v v  , ur ur max0 , i in s c ca a a  và ur ur max0 , i in s c c a   . Các giá trị vận tốc và gia tốc được tính: ur ur ur ur cos( ); sin( ) cos( ); sin( ) i i i i i i i i n n n n x c ij y c ij n n n n x c ij y c ij v v v v a a a a             (2) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 19 Như thể hiện trong hình 1, sau khi quảng bá bản tin trạng thái thì trạng thái của xe si được các xe ni, ni+1, ni+2 và ni+3 cập nhật. Đồng thời, trạng thái của các xe ni, ni+1, ni+2 và ni+3 cũng được cập nhật bởi xe si. Bằng cách này mỗi xe đều duy trì và cập nhật danh sách các xe đơn chặng lân cận. Chu kỳ cập nhật danh sách các nút mạng lân cận chính là chu kỳ quảng bá của bản tin trạng thái. Hình 1. Cập nhật danh sách các xe lân cận. 2.2. Lựa chọn nút giao thông kế tiếp tối ưu Chọn nút giao thông kế tiếp về bản chất chính là chọn đoạn đường kế tiếp mà bản tin sẽ đi qua để đến đích. Thuật toán chọn nút giao thông kế tiếp căn cứ vào hiện trạng giao thông thực tế trên đường, gồm hai yếu tố là: mật độ phương tiện trên đoạn đường mà bản tin có thể đi qua, và khoảng cách từ các nút giao thông có khả năng được chọn đến đích, từ đó xác định được nút giao thông kế tiếp có lợi nhất cho chuyển tiếp bản tin. Đây là phương pháp tìm đường tối ưu trong trạng thái động, dựa trên cơ sở đánh giá về cả khả năng kết nối giữa các xe qua giao tiếp vô tuyến và khoảng cách đến đích. Nếu quãng đường được chọn có khoảng cách đến đích ngắn nhưng mật độ phương tiện quá thấp, khi đó phương tiện mang bản tin sẽ không chọn được nút quảng bá kế tiếp, nó phải lưu giữ bản tin đến khi có thể tiếp tục chuyển. Điều này sẽ làm tăng thời gian trễ đơn chặng và làm giảm hiệu suất định tuyến. Các thông tin về đoạn đường liên quan được xác định từ cơ sở dữ liệu bản đồ số của tuyến đường và thông tin từ bản tin trạng thái. Hình 2. Lựa chọn nút giao thông kế tiếp tối ưu. Như mô tả trên hình 2, xe gửi si là phương tiện đang cần truyền bản tin sự kiện. Nút giao thông hiện tại là I, bản tin có thể đến đích D thông qua các nút giao thông kế tiếp là J1 hoặc J2. Khi đó, với mỗi xe si sẽ xác định hàm ưu tiên F(IJk)i cho mỗi đoạn đường i trong tập các đoạn đường có liên quan trực tiếp đến I như sau: Kỹ thuật điều khiển & Điện tử T. V. Hưng, H. T. Trung, “Thuật toán định tuyến cho giao tiếp V2V chuyển động.” 20 ( ) 1 i i J D i i IJ ID d F IJ d              (3) Trong đó: IDd là khoảng cách từ I đến xe đích D; DJi d là khoảng cách từ Ji đến xe đích D; iIJ  là mật độ xe trung bình trên tuyến giữa hai nút giao thông I và Ji; α, β lần lượt là hệ số ảnh hưởng của yếu tố khoảng cách và yếu tố mật độ xe, với α + β = 1. Ta coi các đoạn đường được mô tả bằng đồ thị G=(V,E) với các nút giao thông là tập các đỉnh V và các đoạn đường là tập các cạnh E. Trên đồ thị tĩnh này, đường đi từ nguồn đến đích được xác định thông qua thuật toán tìm đường ngắn nhất Dijkstra. Trong công thức (3), thành phần thứ nhất mô tả khả năng liên kết giữa các phương tiện qua giao tiếp vô tuyến, và thành phần thứ hai là ảnh hưởng của khoảng cách đến việc chuyển tiếp bản tin tới đích, có nghĩa là khi mật độ xe trên đường đủ lớn thì xác suất tìm được nút trung gian chuyển tiếp bản tin cao và khoảng cách đến đích càng ngắn thì trễ truyền dẫn càng nhỏ. Vì thế, nút giao thông kế tiếp tối ưu được chọn là nút có hàm ưu tiên F(IJk)i lớn nhất, tức là với mỗi cặp α, β thì đoạn đường nữa 2 nút giao thông được chọn là đoạn có mật độ xe lớn nhất và khoảng cách đến đích ngắn nhất. 2.3. Chuyển tiếp bản tin trên đoạn đường đã chọn Khi đã xác định được nút giao thông kế tiếp, tức là đã chọn được nhóm các xe trên đoạn đường có thể chuyển tiếp bản tin đến đích. Bước tiếp theo của thuật toán là cần xác định nên chọn xe nào để chuyển tiếp bản tin cho chặng kế tiếp là có lợi nhất. Các xe trung gian được chọn để chuyển tiếp bản tin dựa trên nguyên tắc ưu tiên về khoảng cách và cùng hướng di chuyển. Khi một xe nhận được bản tin cần chuyển, nó tính và so sánh khoảng cách từ tất cả các xe cùng hướng di chuyển trong vùng phủ đến đích. Xe được chọn có khoảng cách đến nút giao kế tiếp (hoặc đích D nếu không còn nút giao) ngắn nhất, và được gọi là xe “đội trưởng”. Ở mỗi nhóm kế tiếp, thuật toán lại tìm ra được xe “đội trưởng” cho nhóm tiếp theo. Giả sử tọa độ tại tâm nút giao đã chọn được xác định là ( , ) opt opt optJ J J P x y . Khoảng cách từ xe i jn N đến nút giao được tính: 2 2 2( ) i i i opt opt opt n n n J pred J pred JD x x y y     (4) Thay giá trị inpredx và in predy từ công thứ (1) và (4) ta có: 2 2 2 2 ur ur 1 1 2 2 i i i i i i i opt n n n n n n n J c x x c y yD x v t a t y v t a t           (5) Xe trung gian nk được chọn có khoảng cách thỏa mãn: min k opt i optn J n J D D     (6) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 21 Khi đó xe nk được chọn làm xe “đội trưởng” và làm nút trung chuyển kế tiếp do có khoảng cách đến đích nhỏ nhất. Nếu xe “đội trưởng” nk không thay đổi hướng di chuyển, bản tin sẽ được chuyển đi qua các nút trung gian khác theo cách tương tự. Khi chưa chọn được nút “đội trưởng” kế tiếp, nút “đội trưởng” hiện tại mang bản tin thực hiện nguyên tắc lưu và chuyển, cứ tiếp tục như vậy cho đến khi bản tin đến đích. 2.4. Dự đoán chuyển động tương đối của phương tiện Các nút mạng trong VANET được đặc trưng bởi yếu tố vận tốc và hướng di chuyển. Khi đang truyền dữ liệu trên mạng thì các nút mạng vẫn chuyển động với vận tốc lớn. Nếu chỉ áp dụng thuật toán tìm đường đơn giản theo thông tin vị trí được cung cấp mà không có cơ chế dự đoán chuyển động thì gói tin sau khi gửi đi có thể không tới đích do nút đích đã chuyển động khá xa so với vị trí khi cung cấp thông tin cho nút nguồn. Hơn nữa, chuyển động tương đối giữa nút trung gian và nút đích cũng là một thông số quan trọng để lựa chọn đường đi của bản tin trong giao thức định tuyến. Nếu nút trung gian có chuyển động hướng về phía đích sẽ có mức độ ưu tiên khi chọn tuyến cao hơn so với nút gần đích nhưng có hướng chuyển động ngược lại. Mỗi xe luôn biết được vị trí tương đối của nó đối với nút giao thông phía trước bằng cách tự kiểm tra hoặc cập nhật vị trí xe phía trước thông qua bản tin trạng thái. Khi xe di chuyển trong khu vực nút giao thông, nó phát ra bản tin cập nhật vị trí. Nhận được bản tin này, các xe lân cận chuyển sang chế độ dự đoán để dự đoán chuyển động của các xe lân cận nhằm chọn ra xe phù hợp nhất tiếp tục chuyển tiếp bản tin. Hình 3. Xe B dự đoán chuyển động để chọn xe K. Ở hình 3, khi xe ni đến giữa nút giao thông, nó thông báo để các xe lân cận của ni chuyển sang chế độ dự đoán chuyển động. Do vậy, sau khi xe si nhận được bản tin đến từ xe ni-1, xe si dự đoán chuyển động của các xe lân cận với nó và chọn được xe nk phù hợp nhất làm nút chuyển tiếp trung gian để chuyển tiếp bản tin đến đích D. Hình 4. Góc hướng chuyển động tương đối giữa hai xe. Vị trí ở thời điểm hiện tại của ni và D lần lượt là ur ur ur( , ) i i in n n c c cP x y ; ur ur ur( , ) D D D c c cP x y . Sau khoảng thời gian Δt vị trí mới được xác định tương ứng là ( , )i i in n npred pred predP x y ; Kỹ thuật điều khiển & Điện tử T. V. Hưng, H. T. Trung, “Thuật toán định tuyến cho giao tiếp V2V chuyển động.” 22 ( , )D D Dpred pred predP x y . Góc hướng i giữa xe i jn N với xe D sau khoảng thời gian Δt được xác định theo công thức (7). ur ur 2 2 2 2 ur ur ( )( ) ( )( ) cos( ) cos( , ) ( ) ( ) ( ) ( ) i i i i i n nD D D D D D pred pred pred c pred pred pred c i n D n nD D D D D D pred pred pred pred pred c pred c x x x x y y y y V V x x y y x x y y                  (7) Một xe nk bất kỳ có góc hướng k càng nhỏ thì độ ưu tiên khi chọn tuyến càng cao, khi đó, góc hướng của xe được chọn nk với xe đích thỏa mãn:  min min | ( , ), 1, 2,3,...,ik i i n Dtheta V V i m        (8) 2.5. Các bước trong thuật toán GMPR Thuật toán thực hiện việc định tuyến cho giao tiếp xe – xe trong môi trường đô thị. Các bước cơ bản của thuật toán như sau: Bước 1: Xác định vị trí các xe lân cận trong vùng phủ của xe gửi thông qua bản tin trạng thái, bao gồm vị trí hiện tại và vị trí dự đoán sau một khoảng thời gian Δt của chu kỳ bản tin trạng thái. Bước 2: Căn cứ vào khoảng cách từ xe gửi đến đích và mật độ phương tiện trên từng đoạn đường để chọn ra đoạn đường có lợi nhất cho đường đi của bản tin. Bước này chọn được nút giao thông kế tiếp tối ưu. Bước 3: Chọn nút chuyển tiếp trung gian: nút chuyển tiếp trung gian được xác định trên cơ sở kết hợp giữa dự đoán chuyển động và khoảng cách đến đích gần nhất. Nút được chọn đóng vai trò là xe “đội trưởng” có nhiệm vụ trung chuyển bản tin với chi phí thời gian nhỏ nhất. Các bước chính trong thuật toán GMPR được mô tả như sau: Bảng 1. Các bước chính trong thuật toán GMPR. Algorithm: GMPR 1 Input: thông tin về chuyển động của tập nút gửi, nút nhận lân cận tại tcur 2 Output: Nút giao kế tiếp + nút chuyển tiếp trung gian 3 S={sj|j=1,2,3,...,k} 4 Nj={ni|i=1,2,3,...,m} 5 Initialize(); /*Khởi tạo các tham số của thuật toán*/ 6 Received(message); 7 FOR i ← 1 to |Nj| do 8 . ( , )i i in n ni pred pred preds P x y ← ( )ifunctionPos n /*Cập nhật vị trí theo công thức (1)*/ 9 Jopt = Max{F(IJi)} /*Xác định hàm ưu tiên theo công thức (3)*/ 10 Junctioncur = Next_Junction(Jopt) 11 IF . ( , ) .i i in n ni pred pred pred is P x y s TxRange than 12  ( , ); i i optn D n J Calculated V V D    /*Theo công thức (5),(7)*/ 13  min min ( , )in Dtheta V V   ;  min min i optn JD D  /*Dmin theo Dijkstra*/ 14 Next_Hop = Min_distance(ni,J) && Min_theta(ni,D) 15 nk = CaptionVehicleSelect({Nj}) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 23 16 Forward(nk,Next_Hop) 17 ELSE 18 Carry_and_Forward(message) /*Phương thức lưu và chuyển tiếp bản tin*/ 19 Wait_for_Neighbours() 20 Update_List{si}; Quay về bước 8 đến khi bản tin đến đích 21 END 3. MÔ PHỎNG VÀ ĐÁNH GIÁ Phần này thực hiện mô phỏng để đánh giá thuật toán GMPR cho giao thức định tuyến V2V trong môi trường đô thị sử dụng công cụ mô phỏng NCTUns 6.0 [9] trên nền Feroda12. Đây là phần mềm mô phỏng được phát triển bởi Trường đại học Giao thông Đài Loan, tích hợp công cụ mô phỏng ITS với tiêu chuẩn IEEE 802.11(p)/1609. Các tham số cho mô phỏng được thiết lập như trong bảng 2. Bảng 2. Các tham số trong mô phỏng. Tham số Giá trị Tham số Giá trị Thời gian mô phỏng 200s MAC protocol IEEE 802.11(p) Số nút giao thông 16 Dung lượng kênh 2 Mbps Số tuyến đường 26 Chu kỳ bản tin sự kiện 0,2s~0,8s Số lượng xe 50-200 Kích thước bản tin 128 bytes Vận tốc trung bình 30-50 km/h Bán kính vùng phủ 250m 3.1. Các chỉ tiêu đánh giá Để đánh giá tính năng của thuật toán GMPR, tác giả đã tiến hành so sánh thuật toán đề xuất trong bài báo với một số thuật toán định tuyến đã có như GPSR [5], LAR [6], GSR [7]. Thuật toán LAR[6] được thực hiện trong mạng Manet (Mobile Ad-hoc Network), trong thuật toán này chỉ sử dụng thuần túy thông tin vị trí để xác định tuyến mới với mục tiêu là làm giảm số lượng bản tin định tuyến khi các nút di chuyển. Trong khi đó, thuật toán GPSR[5] không thực hiện tính toán để thiết lập bất kỳ tuyến nào giữa nguồn và đích, mỗi nút gửi chỉ thực hiện chèn địa chỉ đích vào phần header của gói tin, sau đó, chuyển gói tin cho nút lân cận đơn chặng có khoảng cách gần đích nhất và gói tin đến đích theo chế độ “greedy” hoặc “perimeter”. Trong khi đó, GSR[7] đã lựa chọn đường tới đích ngắn nhất bằng thuật toán Dijkstra từ tọa độ GPS. Bản tin được chuyển đến các nút giao thông trên đường rồi chuyển đến đích như cơ chế trong thuật toán GPSR[5], tuy nhiên, cũng chưa có cơ chế dự đoán chuyển động khi chọn nút chuyển tiếp trung gian. So sánh được thực hiện trên cơ sở khảo sát 3 yếu tố: tỉ tệ chuyển tiếp gói tin thành công, trễ trung bình đầu-cuối và số chặng chuyển tiếp trung bình. Quá trình mô phỏng được thực hiện 5 lần và lấy giá trị trung bình của các kết quả. Các chỉ tiêu đánh giá được định nghĩa như sau: a) Tỉ lệ chuyển tiếp gói tin thành công: Là tỉ số giữa số gói tin nhận được tại nút đích với số gói tin được gửi đi bởi nút nguồn. Tỉ lệ này thể hiện độ tin cậy của giao thức khi chuyển tiếp gói tin: send received pkt pkt success n n pkt  (9) Kỹ thuật điều khiển & Điện tử T. V. Hưng, H. T. Trung, “Thuật toán định tuyến cho giao tiếp V2V chuyển động.” 24 b) Trễ trung bình đầu-cuối: Thời gian trễ của từng gói tin là chênh lệch giữa thời gian nhận được tại đích và thời gian gửi tại nguồn. Thời gian trễ trung bình đầu-cuối gồm trễ truyền dẫn trên mạng, trễ xếp hàng và trễ xử lý tại các nút trung gian. received i received pkt i sendpkt i received avg n tt )( each for    (10) c) Số chặng chuyển tiếp trung bình: Sử dụng đại lượng Hopi để thể hiện số chặng chuyển tiếp khi chuyển mỗi gói tin i từ nguồn đến đích. received i received pkt pkt i avg n Hop Hop   each for (11) 3.2. Kết quả mô phỏng và đánh giá Trên hình 5 là so sánh tỉ lệ chuyển tiếp bản tin thành công của 4 thuật toán với số lượng phương tiện khác nhau. Khi số lượng xe tăng thì tỉ lệ chuyển tiếp bản tin thành công của GMPR chiếm ưu thế hơn các thuật toán còn lại. Đây chính là ưu điểm của GMPR khi thuật toán này đã khảo sát đến ảnh hưởng của mật độ phương tiện đến chọn đường đi tối ưu của bản tin. Bởi vì, khi mật độ phương tiện đủ lớn thì xác suất chuyển tiếp thành công bản tin tăng lên do giao tiếp vô tuyến không bị gián đoạn. Hình 5. Tỉ lệ chuyển tiếp bản tin thành công. Hình 6. Số chặng chuyển tiếp trung bình. Hình 7. Trễ trung bình đầu-cuối (5pkts/sec). Hình 8. Trễ trung bình đầu cuối (200 xe). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 25 Hình 6 so sánh số chặng chuyển tiếp trung bình của các thuật toán. Do có sự kết hợp giữa thông tin vị trí và dự đoán chuyển động của xe nên chặng trung chuyển kế tiếp ở GMPR luôn chọn được nút chuyển tiếp phù hợp. Các thuật toán còn lại chưa có cơ chế dự đoán chuyển động của xe nên chặng kế tiếp chưa phải là lựa chọn tốt nhất. Vì vậy, số chặng chuyển tiếp trung bình đều cao hơn đối với GMPR. Hình 7 và 8 là so sánh trễ trung bình đầu-cuối với hai kịch bản là số lượng xe thay đổi khi tần số phát bản tin sự kiện là 5 bản tin/giây và kịch bản mô phỏng với 200 xe, chu kỳ phát bản tin sự kiện thay đổi từ 0.2 giây đến 0.8 giây. Ở cả hai trường hợp thuật toán GMPR đều cho thời gian trễ thấp hơn các thuật toán còn lại. Điều này có thể giải thích: thứ nhất là trong GMPR có số chặng chuyển tiếp trung gian giảm dẫn tới thời gian trễ tổng giảm; Thứ hai, do GMPR chọn quãng đường tiếp theo có hàm ưu tiên F(IJk)i lớn nhất kết hợp với dự đoán chuyển động của xe nên xác suất mất liên kết vô tuyến giữa các phương tiện khi truyền tin là thấp nhất. Khi đường truyền lỗi, xe gửi không nhận được khung báo nhận ACK từ các xe lân cận, sau một khoảng thời gian xe gửi sẽ lặp lại việc truyền bản tin và cứ tiếp tục như vậy khi số lần truyền lại đạt ngưỡng thì quá trình bị khởi động lại làm thời gian trễ tăng lên. Ở thuật toán GMPR đã xét đến những yếu tố này nên đã giảm thiểu được số lần truyền lại bản tin của cùng một sự kiện nên trễ trung bình đầu cuối giảm. 4. KẾT LUẬN Bài báo đã đưa ra thuật toán định tuyến cho giao tiếp V2V trong môi trường đô thị, sử dụng thông tin vị trí kết hợp với dự đoán chuyển động của các phương tiện. Thuật toán đề xuất đã cải thiện được những hạn chế của các cơ chế định tuyến chỉ dựa trên thông tin vị trí, nâng cao hiệu suất định tuyến. Qua phân tích lý thuyết và đánh giá bằng mô phỏng đều chứng tỏ thuật toán đưa ra đã làm tăng tỉ lệ chuyển tiếp bản tin thành công, giảm thời gian trễ trung bình đầu-cuối và làm giảm số chặng chuyển tiếp trung bình khi so sánh với một số thuật toán đã có. Tuy nhiên, môi trường thông tin thực tế trong đô thị rất phức tạp, bài báo chưa khảo sát đến các nhân tố ảnh hưởng tới quá trình giao tiếp V2V. Các giá trị α và β cũng cần được khảo sát và đánh giá chi tiết qua thực nghiệm. Đây cũng là công việc nghiên cứu tiếp theo của tác giả. TÀI LIỆU THAM KHẢO [1]. Li F, Yu W, “Routing in Vehicular Ad-hoc Networks: A Survey”, IEEE Vehicular Technology Magzine, 2007, 2(2), pp. 12-22. [2]. D. Jiang and L. Delgrossi, “IEEE 802.11p: Towards an international standard for wireless access in vehicular environments” in Proc. of the IEEE Vehicular Technology Conference. IEEE, 2008, pp. 2036-2040. [3]. C.E. Perkins, E. Royer, “Ad-hoc On-Demand Distance Vector Routing”, in: Proceedings of the Second IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, USA, 1999, pp. 90-100. [4]. David B. Johnson David A. Maltz Josh Broch, “DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks”, pp.1-25. [5]. Brad Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks”, ACM IEEE MOBICOM 2000, New York, pp. 243-254. Kỹ thuật điều khiển & Điện tử T. V. Hưng, H. T. Trung, “Thuật toán định tuyến cho giao tiếp V2V chuyển động.” 26 [6]. KO Y, VAIDYA N, “Locaton-Aided Routing in Mobile Ad-hoc Networks”, ACM, IEEE MOBICOM’98. Dallas, 1998, pp.66-75． [7]. C. Lochert, H. Hartenstein, J. Tian, D. Herrmann, H. Füßler, M. Mauve, "A Routing Strategy for Vehicular Ad Hoc Networks in City Environments", IEEE Intelligent Vehicles Symposium (IV2003), pp. 156-161, Columbus, OH, USA, June 2003 [8]. C.-F. Wang et al.,“Nexthop selection mechanism for nodes with heterogeneous transmission range in VANETs”, Computer Communications 55, 2015, pp. 22. [9]. Prof. Shie-Yuan Wang, Chih-Liang Chou, and Chih-Che Lin, “The GUI User Manual for the NCTUns 6.0 Network Simulator and Emulator”, Department of Computer Science, National Chiao Tung University, Taiwan. [10]. Ryosuke Akamatsu, Keiji Obara, Hiroshi Shigeno, “Road-Oriented Geographic Routing Protocol for Urban Vehicular Ad Hoc Networks”, 29th WAINA.2015, IEEE, pp.721-726. [11]. K.D. Park et al., “Mobility State Based Routing Method in Vehicular Adhoc Network”, 2015 IEEE International Conference on Mobile Services, pp.472-474 [12]. J.P.Jeong et al., “TPD: Travel Prediction-based Data Forwarding for light- trac vehicular networks”, 2015 Elsevier Computer Networks, pp.166-182 [13]. Trần Văn Hưng, Vũ Trọng Tuân, “Thuật toán cho giao thức truyền thông cảnh báo va chạm trên đường cao tốc”, Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 – 2015,pp.42-49 ABSTRACT A GEOGRAPHY-MOVEMENT PREDICTION BASED ON THE ROUTING ALGORITHM FOR V2V COMMUNICATION IN CITY ENVIRONMENT In VANET, the routing is a difficult problem due to unpredictable nodes as vehicles movement and frequent network topology change. Therefore, the most important issue is to predict correctly the future movements of vehicles when selecting intermediate nodes. In this paper, a Geography-Movement Prediction based on the Routing Algorithm for V2V Communications in City Environment that selects reliable road segments and intermediate nodes to improve the routing efficiency was proposed. Both theory analysis and experiments show that the proposed algorithm has more packets delivery rate, has less average end-to-end delay time and average number of hops than traditional routing algorithms had. Keywords: ITS, VANET, V2V, GMPR. Nhận bài ngày 09 tháng 02 năm 2017 Hoàn thiện ngày 27 tháng 02 năm 2017 Chấp nhận đăng ngày 05 tháng 4 năm 2017 Địa chỉ: Khoa Điện – Điện tử, Trường Đại học Giao thông Vận tải *Email: hungtv_ktdt@utc.edu.vn