CHƯƠNG 1. Giới thiệu MANET MANET (Mobile Ad hoc Network) là một tập hợp các thiết bị di động tự hành có thể liên lạc thông qua các kết nối không dây có băng thông hạn chế mà không cần thông qua một trung tâm điều khiển nào. Bởi vì các nút mạng (node) là di động, sơ đồ mạng có thể thay đổi nhanh chóng và không thể dự đoán được theo thời gian. Các hoạt động trong mạng bao gồm phát hiện (discovering) sơ đồ mạng, chuyển phát (transfering) thông tin phải được thực hiện bởi chính các nút mạng.
Mỗi MANET có thông số khác nhau và không thể đoán trước về số lượng nút, mật độ, cách thức bố trí, tầm phủ sóng, xu hướng thay đổi,… MANET còn nhiều vấn đề cần giải quyết, có thể kể tới như vấn đề về định tuyến, vấn đề quản lý broadcast, vấn đề bảo đảm chất lượng dịch vụ mạng, vấn đề stream video, vấn đề cache dữ liệu trong mạng, vấn đề bảo mật, vấn đề tiết kiệm năng lượng,. Khi mạng liên tục thay đổi, các vấn đề trên đều gặp nhiều khó khăn hơn, so với mạng hữu tuyến, hay các mạng vô tuyến có hạ tầng cố định như mạng 2G, 3G, 4G, mà ở đó, các thiết bị kết nối đến các BTS cố định. Định vị trong MANET Việc có được thông tin về vị trí địa lý tuyệt đối gần đúng, hoặc ít nhất là vị trí tương đối của các thiết bị trong mạng sẽ giúp ích cho cho các giao thức định tuyến dựa trên vị trí địa lý, cũng như giúp giải quyết các vấn đề kỹ thuật khác của mạng dễ dàng hơn, giúp nâng cao chất lượng phục vụ của mạng. Về ứng dụng thực tế, việc xác định vị trí địa lý còn có thể hỗ trợ các công tác cứu nạn, du lịch, bản đồ, tìm đường,… Mặc dù hệ thống định vị toàn cầu GPS đã có thể giải quyết được hầu hết các vấn đề về định vị tổng quát, tuy nhiên việc áp dụng GPS ở mọi nơi vẫn gặp một số trở ngại.
Sau 18 đây là một số ví dụ cho các tình huống mà việc sử dụng hệ thống định vị GPS là không khả thi: Ngoài trời, nhưng tín hiệu GPS bị che chắn do có nhiều nhà cao tầng, núi cao. Nơi thoáng đãng như trong thời tiết mưa, bão, tuyết thì tín hiệu GPS nhiều lúc không khả dụng. Bên trong đường hầm. Trong nhà, ví dụ bên trong tòa nhà, hội trường, triển lãm, hội chợ, siêu thị, tín hiệu GPS bị che chắn hoàn toàn.
Mạng cảm biến cần tiết kiệm chi phí nên không trang bị phần cứng cho GPS. Ngoài ra, trong trường hợp có thể sử dụng được GPS thì khi bắt đầu sử dụng, thiết bị cũng sẽ mất một khoảng thời gian mới có thể fix được tọa độ ban đầu, thời gian này có thể mất đến nhiều phút. Ứng dụng Việc phát triển một phương pháp định vị sử dụng kết nối Wifi sẵn có thể mang lại các ứng dụng sau: Định vị ở nơi mà sử dụng GPS là không khả thi như trong các tòa nhà, trong các hội chợ, triển lãm, viện bảo tàng, ứng dụng vào thương mại. Mang đến khả năng định vị nhanh cho các thiết bị hoạt động trong mạng wifi nhưng không được trang bị sẵn GPS, như Laptop, Desktop, các cảm biến trong mạng sensor, các thiết bị công nghiệp, quản lý kho bãi.
Sử dụng như một phương pháp định vị hỗ trợ cho thiết bị di động (vai trò tương tự như các phương pháp định vị dựa trên tọa độ BTS, tọa độ Wifi của Accesspoint) nhằm giúp người dùng nhận được một tọa độ chấp nhận được trong khi GPS thực hiện quá trình fix tọa độ đầu. Lí do chọn đề tài Ngày nay, việc phát triển nhanh nhóng về số lượng các thiết bị di động có hỗ trợ kết nối Wifi và khả năng xử lý mạnh mẽ như máy tính laptop, điện thoại thông minh,… đã khiến cho MANET phổ biến hơn, điều này làm phát sinh các ứng dụng trong MANET, bao gồm các ứng dụng Multimedia, truyền dữ liệu, định tuyến,… Khi đó nhu cầu định vị trong MANET trở nên cần thiết, quan trọng. Đó là lí do cho việc lựa chọn đề tài “Nghiên cứu các phương pháp định vị trong MANET - Cải tiến phương pháp DV-Hop”. Mục đích luận văn Luận văn mong muốn có thể đưa ra cái nhìn tổng quan về các vấn đề về định vị trong mạng MANET, khảo sát một số cách thức định vị mà các tác giả trên thế giới đã thực hiện trong thời gian qua, trong đó, luận văn chú trọng nghiên cứu phương pháp DV-Hop, một phương pháp định vị chủ đạo trong MANET.
Đồng thời, luận văn sẽ đề xuất một phương thức cải tiến phương pháp định vị DV-Hop, sử dụng tính di động của các cột mốc. Luận văn bao gồm các nội dung chính sau: 1. Giới thiệu sơ lược. Tình hình nghiên cứu.
Trình bày các vấn đề trong định vị trong MANET. Trình bày một số phương pháp định vị cơ bản 5. Đề xuất hướng cải tiến giải thuật DV-Hop, phương pháp ISCIMP. Mô tả cách thức thực hiện các mô phỏng và trình bày kết quả.
Kết luận và đánh giá. TÌNH HÌNH NGHIÊN CỨU HIỆN NAY Có nhiều nghiên cứu về định vị trong mạng ad hoc và MANET đã được thực hiện, nhìn chung, có thể chia làm hai nhóm chính: (1) Dựa vào đo đạc (range-based) và (2) Không dựa vào đo đạc (range-free). Trong mạng thường có những nút đã biết được tọa độ chính xác, nhờ vào GPS hoặc nhờ vào cấu hình đặc biệt, ta gọi chúng là các cột mốc (anchor, landmark), mật độ, cách sắp xếp của các nút cột mốc này khác nhau với mỗi mạng; từ tọa độ của các nút cột mốc này, tọa độ của các nút còn lại cần phải được xác định. Các phương pháp định vị thuộc vào nhóm Dựa vào đo đạc cần thiết bị có thêm khả năng đo được khoảng cách hoặc góc đến các nút lân cận, điều này làm phát sinh thêm yêu cầu hỗ trợ từ phía phần cứng.
Các thông số này có thể được tính dựa vào thời gian sóng đến (TOA – Time Of Arrival) [1], chênh lệch thời gian sóng đến (TDOA – Time Difference Of Arrival) [2], góc sóng đến (AOA – Angle Of Arrival) [3], và độ mạnh của tín hiệu (RSSI – Received Signal Strength Indicator) [4]. Các phương pháp này thường cho kết quả chính xác hơn, tuy nhiên việc yêu cầu thêm phần cứng hỗ trợ khiến chi phí tăng lên nhiều. Nhóm phương pháp thứ hai, không dựa vào khả năng đo khoảng cách hay đo góc khi định vị. Mặc dù các phương pháp này thường sẽ mang lại kết quả kém chính xác hơn các phương pháp Range-based, nhưng nó lại hiệu quả về mặt kinh tế và tiết kiệm năng lượng.
Bởi vì tính chất MANET là mạng của các thiết bị di động và mạng cảm biến, giá thành cũng như mức độ tiêu thụ năng lượng được quan tâm rất nhiều, do đó, các phương pháp Không dựa vào đo đạc trở thành lựa chọn khả thi hơn khi cần định vị các nút. Phương pháp dựa vào đo đạc Các cơ chế định vị dựa vào đo đạc khai thác các thông tin khoảng cách, góc để định vị, các thông số này được xác định bằng cách sử dụng các phương pháp RSSI, TOA, TDOA, AOA. Sử dụng thông tin về khoảng cách, các node sử dụng phép tính Trilateration để tính ra tọa độ của nút. Cùng với phương pháp Triangulation (sử dụng thông số về góc), phép tính Trilateration (sử dụng thông số về khoảng cách) được sử dụng trong hầu hết các phương pháp định vị, bất kể phương pháp đó có dựa vào đo đạc hay không, chi tiết về hai phương thức tính toán này sẽ được trình bày ở phần sau (trang 27 và 28).
Bergamo và Mazzin đề xuất một cơ chế Trilateration sử dụng các khoảng cách ước lượng bằng công suất thu được và nghiên cứu các ảnh hưởng đến giải thuật bởi hiệu ứng fading và tính di động của cảm biến [5]. Các phương pháp này dễ bị ảnh hưởng bởi môi trường khi có vật cản xuất hiện, hiệu ứng fading, hiệu ứng shadow, đồng thời yêu cầu số cột mốc phải nhiều, phải che phủ được hết các node. Nhiều phương pháp được áp dụng để phát hiện ra môi trường che chắn, đường truyền sóng không thẳng hàng, cũng như giảm sai số trong vấn đề đo đạc, tính toán.1 – Hiệu ứng fading khiến cho việc đo đạc khoảng cách bị sai 22 Hình 2.2 – Định vị range-based ở mạng điện thoại Tình huống các trạm BTS được trang trị phần cứng chuyên dụng nên dễ dàng phát hiện được hướng sóng đến thiết bị, từ đó gửi về trung tâm, cùng với tọa độ của mỗi BTS, từ đó có thể tính toán tọa độ chính xác của thiết bị Nhìn chung, các phương pháp này cho phép đạt được mức sai số thấp, dưới 5 mét, nhưng nhược điểm là cần phần cứng hỗ trợ, điều này làm tăng chi phí thiết bị. Phương pháp không dựa vào đo đạc Để phù hợp với tính chất đặc trưng của mạng MANET, nhiều tác giả đã đề xuất các phương pháp định vị không cần thông số khoảng cách hay góc.
Không có được khoảng cách đo trực tiếp, các phương pháp này thường dựa vào tọa độ của các cột mốc và sơ đồ kết nối của mạng để ước lượng một khoảng cách gần đúng đến các cột mốc rồi tính toán tọa độ dựa vào phương pháp Triangulation hoặc Trilateration. Belusu và Heidemann đã giới thiệu công thức Centriod để tính vị trí Node dựa trên tọa độ của các gói tin tìm đường chứa thông tin tọa độ của các cột mốc. Phương pháp DV-Hop, được đề xuất bởi Dragos và Nath, xác định khoảng cách hop giữa các nút đến các cột mốc, sau đó ước lượng khoảng cách đến các cột mốc này và tự xác định tọa độ bằng phương pháp Trilateration [6]. Phương pháp DV-Hop là một phương pháp tốt và được nhiều tác giả 23 chọn để cải tiến.
Các cải tiến này có thể áp dụng thêm RSSI, thay đổi cách thức ước lượng khoảng cách và tọa độ. Một phương pháp dựa vào diện tích (APIT – Approximate Point-in trigulation) đã được phát triển để làm hẹp lại khoảng tọa độ có thể của nút. Các phương pháp này nhìn chung còn nhiều sai số và cần cải thiện thêm. Định vị trong MANET Bên cạnh định vị trong điều kiện mạng tĩnh, tức là các nút không di động, một số tác giả đã nghiên cứu các vấn đề xoay quanh các phương pháp định vị có quan tâm đến tính di động của nút.
