Nghiên Cứu Các Phương Pháp Định Vị Trong MANET - Cải Tiến Phương Pháp DV-HOP

Nghiên cứu phương pháp định vị trong MANET, tập trung cải tiến DV-Hop. Luận văn Đỗ Nguyễn Minh Tuấn phân tích, đề xuất giải pháp nâng cao độ chính xác định vị.

• Tác giả: Đỗ Nguyễn Minh Tuấn
• Người hướng dẫn: Tiến Sĩ Nguyễn Minh Hoàng
• Trường học: Trường Đại học Bách Khoa – ĐHQG – HCM
• Chuyên ngành: Kỹ thuật điện tử
• Đề 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
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN CỦA TÁC GIẢ LUẬN VĂN
• DANH SÁCH BẢNG BIỂU
• DANH SÁCH HÌNH ẢNH
• DANH SÁCH CÁC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU MANET
• 1.1. ĐỊNH VỊ TRONG MANET
• 1.2. LÍ DO CHỌN ĐỀ TÀI
• 1.3. MỤC ĐÍCH LUẬN VĂN
• 2. CHƯƠNG 2: TÌNH HÌNH NGHIÊN CỨU HIỆN NAY
• 2.1. PHƯƠNG PHÁP DỰA VÀO ĐO ĐẠC
• 2.2. PHƯƠNG PHÁP KHÔNG DỰA VÀO ĐO ĐẠC
• 3. CHƯƠNG 3: ĐỊNH VỊ TRONG MANET
• 3.1. CÁC KHÁI NIỆM HAY DÙNG
• 3.2. PHƯƠNG PHÁP ĐỊNH VỊ
• 3.2.1. Giới thiệu sơ lược về GPS
• 3.2.2. Phương pháp Trilateration
• 3.2.3. Phương pháp Triangulation
• 3.3. PHƯƠNG PHÁP GIẢI HỆ PHƯƠNG TRÌNH LEAST SQUARE METHOD
• 3.4. PHƯƠNG PHÁP XÁC ĐỊNH KHOẢNG CÁCH HOP GIỮA HAI NÚT
• 3.5. MÔ HÌNH DI CHUYỂN
• 3.6. CÁCH THỨC ĐÁNH GIÁ KẾT QUẢ
• 4. CHƯƠNG 4: KHẢO SÁT MỘT SỐ PHƯƠNG PHÁP ĐỊNH VỊ
• 4.1. PHƯƠNG PHÁP DV-HOP
• 4.1.1. Nguồn gốc của lỗi định vị
• 4.2. PHƯƠNG PHÁP DV-DISTANCE
• 4.3. CẢI TIẾN PHƯƠNG PHÁP DV-HOP BẰNG CÁCH THAY ĐỔI CÔNG THỨC TÍNH KÍCH THƯỚC HOP TRUNG BÌNH
• 5. CHƯƠNG 5: ĐỀ XUẤT CẢI TIẾN PHƯƠNG PHÁP DV-HOP SỬ DỤNG TÍNH DI ĐỘNG CỦA CÁC CỘT MỐC
• 5.1. PHƯƠNG PHÁP CẢI TIẾN ĐỀ XUẤT
• 5.2. ĐỀ XUẤT CÁC MÔ HÌNH DI CHUYỂN CỦA CỘT MỐC
• 5.2.1. Di chuyển hỗn loạn (Chaos Move)
• 5.2.2. Đi thẳng theo một hướng ngẫu nhiên (RDW - Random Direction Walk)
• 5.2.3. Di chuyển đều dọc theo cạnh (Edge move)
• 5.2.4. Di chuyển đều dọc theo cạnh lặp lại (Tile Move)
• 6. CHƯƠNG 6: CÁCH THỨC MÔ PHỎNG
• 6.1. ĐIỀU KIỆN BÀI TOÁN MÔ PHỎNG
• 6.1.1. Các điều kiện chung
• 6.1.2. Các điều kiện trong trường hợp cột mốc di động
• 6.2. TRÌNH BÀY KẾT QUẢ
• 6.3. CHI TIẾT CÁC MÔ PHỎNG VÀ KẾT QUẢ
• 6.3.1. Giải thuật DV-Distance
• 6.3.2. Giải thuật DV-Hop cơ bản
• 6.3.3. Khảo sát ảnh hưởng lên giải thuật DV-Hop khi thay đổi về số cột mốc sử dụng để định vị mỗi thiết bị
• 6.3.4. Khảo sát ảnh hưởng lên giải thuật dv-hop khi thay đổi mật độ số thiết bị có gps trong mạng
• 6.3.5. Cải tiến DV-Hop bằng cách thay đổi công thức tính kích thước Hop trung bình
• 6.3.6. Cải tiến bằng phương pháp ISCIMP: các cột mốc di chuyển hỗn loạn
• 6.3.7. Cải tiến bằng phương pháp ISCIMP: các cột mốc đi thẳng hướng ngẫu nhiên
• 6.3.8. Cải tiến bằng phương pháp ISCIMP: các cột mốc di chuyển tuyến tính dọc biên
• 6.3.9. Cải tiến bằng phương pháp ISCIMP: các cột mốc di chuyển tuyến tính dọc biên lặp lại (Tile Move)
• 6.3.10. Cải tiến bằng phương pháp ISCIMP: tất cả thiết bị di chuyển hỗn loạn
• 6.3.11. Cải tiến bằng phương pháp ISCIMP: tất cả các thiết bị đi theo hướng ngẫu nhiên (randomwalk)
• 7. CHƯƠNG 7: ĐÁNH GIÁ CÁC KẾT QUẢ VÀ KẾT LUẬN
• 7.1. HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO
• MÃ NGUỒN MATLAB CỦA MÔ PHỎNG
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng Quan Mạng MANET và Bài Toán Định Vị DV Hop 55

Mạng MANET (Mobile Ad hoc Network) là một tập hợp các thiết bị di động tự hành, kết nối không dây băng thông hạn chế mà không cần trung tâm điều khiển. Các nút mạng di động khiến sơ đồ mạng thay đổi nhanh chóng, khó dự đoán. Mọi hoạt động mạng, từ phát hiện sơ đồ đến chuyển phát thông tin, đều do chính các nút thực hiện. Mỗi MANET khác nhau về số lượng nút, mật độ, bố trí, tầm phủ sóng, và xu hướng thay đổi. Các vấn đề cần giải quyết bao gồm định tuyến, quản lý broadcast, đảm bảo chất lượng dịch vụ mạng, stream video, cache dữ liệu, bảo mật, tiết kiệm năng lượng, và nhiều hơn nữa. Đặc biệt, việc có thông tin vị trí địa lý gần đúng của các thiết bị trong mạng giúp ích cho các giao thức định tuyến dựa trên vị trí, cũng như nâng cao chất lượng mạng. Ứng dụng thực tế hỗ trợ cứu nạn, du lịch, bản đồ, tìm đường, và nhiều lĩnh vực khác. Dù GPS hữu ích, việc áp dụng GPS ở mọi nơi vẫn gặp trở ngại.

1.1. MANET Khái niệm và các đặc điểm cơ bản cần nắm 53

MANET hoạt động dựa trên kết nối trực tiếp giữa các thiết bị, tạo thành một mạng lưới linh hoạt. Điều này khác biệt so với mạng di động truyền thống, nơi thiết bị kết nối thông qua trạm gốc. Khả năng tự cấu hình, tự phục hồi và khả năng mở rộng cao là những ưu điểm nổi bật của MANET. Tuy nhiên, sự biến động về cấu trúc mạng, băng thông hạn chế và vấn đề bảo mật là những thách thức cần giải quyết. Việc nghiên cứu và phát triển các giải pháp hiệu quả cho những thách thức này là rất quan trọng để tận dụng tối đa tiềm năng của MANET. MANET rất tiềm năng để ứng dụng vào nhiều lĩnh vực.

1.2. Ứng dụng thực tiễn của định vị trong mạng MANET 57

Thông tin vị trí chính xác trong MANET mở ra nhiều ứng dụng tiềm năng. Trong lĩnh vực quân sự, việc định vị giúp theo dõi và điều phối lực lượng một cách hiệu quả. Trong lĩnh vực cứu hộ, định vị giúp tìm kiếm và giải cứu nạn nhân trong các khu vực khó khăn. Các ứng dụng khác bao gồm theo dõi tài sản, quản lý giao thông thông minh và các dịch vụ dựa trên vị trí. Việc phát triển các thuật toán định vị chính xác và hiệu quả sẽ đóng góp quan trọng vào việc mở rộng các ứng dụng của MANET.

II. Vì Sao Nghiên Cứu Cải Tiến DV Hop Trong MANET Quan Trọng 57

Dù hệ thống GPS giải quyết hầu hết vấn đề định vị tổng quát, việc áp dụng GPS ở mọi nơi gặp trở ngại. Tín hiệu GPS bị che chắn bởi nhà cao tầng, núi cao, hoặc không khả dụng trong thời tiết xấu. Bên trong đường hầm, tòa nhà, hội chợ, triển lãm, siêu thị, tín hiệu GPS bị 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ị GPS. Ngay cả khi GPS sử dụng được, thiết bị mất thời gian để 'fix' tọa độ ban đầu. Việc phát triển phương pháp định vị dùng Wifi có thể mang lại ứng dụng quan trọng. Định vị ở nơi GPS không khả thi, cung cấp khả năng định vị nhanh cho thiết bị không có GPS, hỗ trợ định vị cho thiết bị di động trong khi GPS fix tọa độ.

2.1. Hạn chế của GPS và sự cần thiết của các giải pháp thay thế 59

Sự phụ thuộc vào GPS mang lại những rủi ro nhất định. Tín hiệu GPS có thể bị can thiệp, gây ra sai lệch vị trí hoặc mất tín hiệu hoàn toàn. Trong môi trường đô thị, tín hiệu GPS thường bị phản xạ và nhiễu, làm giảm độ chính xác. Ngoài ra, việc sử dụng GPS tiêu tốn năng lượng, ảnh hưởng đến thời lượng pin của thiết bị di động. Do đó, việc nghiên cứu và phát triển các giải pháp định vị thay thế là rất quan trọng để đảm bảo tính tin cậy và khả dụng của dịch vụ định vị.

2.2. Tiềm năng của DV Hop trong môi trường MANET đặc thù 54

Thuật toán DV-Hop không yêu cầu thiết bị phải trang bị GPS, giảm chi phí và năng lượng tiêu thụ. Nó hoạt động dựa trên thông tin khoảng cách giữa các nút, phù hợp với môi trường MANET phân tán và không có cơ sở hạ tầng trung tâm. Độ phức tạp tính toán của DV-Hop tương đối thấp, cho phép triển khai trên các thiết bị có tài nguyên hạn chế. Nhờ những ưu điểm này, DV-Hop là một lựa chọn tiềm năng cho việc định vị trong MANET, đặc biệt trong các ứng dụng không yêu cầu độ chính xác quá cao.

III. Nghiên Cứu Phương Pháp Định Vị DV Hop Tổng Quan và Phân Tích 58

Ngày nay, số lượng thiết bị di động hỗ trợ Wifi và khả năng xử lý mạnh mẽ như laptop, điện thoại thông minh, khiến MANET phổ biến hơn, tạo ra các ứng dụng Multimedia, truyền dữ liệu, định tuyến. Nhu cầu định vị trong MANET trở nên cần thiết và quan trọng. Các phương pháp định vị trong MANET: Phương pháp dựa vào đo đạc (Range-based) sử dụng thông tin khoảng cách hoặc góc để ước tính vị trí. Phương pháp không dựa vào đo đạc (Range-free) tận dụng thông tin kết nối giữa các nút mạng. Bài viết tập trung vào phân tích và cải tiến phương pháp DV-Hop, một phương pháp không dựa vào đo đạc phổ biến trong MANET. DV-Hop sử dụng số bước nhảy (hop count) để ước tính khoảng cách, phù hợp với môi trường MANET phân tán.

3.1. Nguyên lý hoạt động và các bước cơ bản của thuật toán DV Hop 59

DV-Hop hoạt động dựa trên việc lan truyền thông tin từ các nút neo đến các nút chưa biết vị trí. Các nút neo phát quảng bá thông tin vị trí của mình đến toàn mạng. Các nút khác ghi nhận số bước nhảy (hop count) tối thiểu đến từng nút neo. Sau đó, các nút chưa biết vị trí ước tính khoảng cách đến các nút neo dựa trên số bước nhảy và kích thước mỗi bước nhảy trung bình. Cuối cùng, vị trí của nút được tính toán bằng phương pháp Trilateration hoặc các phương pháp tương tự.

3.2. Ưu điểm và nhược điểm của phương pháp DV Hop 51

Ưu điểm chính của DV-Hop là đơn giản, dễ triển khai và không yêu cầu phần cứng đặc biệt. Tuy nhiên, độ chính xác của DV-Hop bị ảnh hưởng bởi nhiều yếu tố, bao gồm mật độ nút, sự phân bố không đều của nút neo và lỗi ước tính khoảng cách. Trong môi trường mạng có nhiều vật cản, số bước nhảy có thể không phản ánh chính xác khoảng cách thực tế. Do đó, việc cải tiến DV-Hop để nâng cao độ chính xác là một vấn đề quan trọng.

IV. Các Phương Pháp Cải Tiến Độ Chính Xác Định Vị DV Hop 59

Sai số định vị trong DV-Hop xuất phát từ ước tính khoảng cách không chính xác do phân bố mạng không đều, đường đi bị bẻ gập. Các cải tiến DV-Hop tập trung vào thay đổi công thức tính kích thước Hop trung bình, sử dụng thông tin di động của các cột mốc. Phương pháp ISCIMP (Ignoring Sudden Coordinates In Moving Process) đề xuất cải tiến kết quả DV-Hop bằng cách sử dụng tính di động của các cột mốc. ISCIMP giúp giảm thiểu sai số bằng cách loại bỏ các đỉnh nhọn trong quá trình di chuyển, lọc nhiễu và tăng độ chính xác. Các mô hình di chuyển cột mốc: Di chuyển hỗn loạn (Chaos Move), Đi thẳng theo một hướng ngẫu nhiên (RDW), Di chuyển đều dọc theo cạnh (Edge move), Di chuyển đều dọc theo cạnh lặp lại (Tile Move).

4.1. Giải pháp thay đổi công thức tính kích thước Hop trung bình 59

Một số nghiên cứu tập trung vào việc cải thiện ước tính khoảng cách bằng cách thay đổi công thức tính kích thước mỗi bước nhảy trung bình (Average Hop Size - AHS). Thay vì sử dụng một giá trị AHS duy nhất cho toàn mạng, các phương pháp này sử dụng AHS cục bộ, dựa trên mật độ nút và khoảng cách giữa các nút lân cận. Các thuật toán tối ưu hóa như Genetic Algorithm và Particle Swarm Optimization cũng được áp dụng để tìm ra giá trị AHS tối ưu, giúp giảm sai số định vị.

4.2. Phương pháp ISCIMP sử dụng tính di động của các cột mốc 49

Phương pháp ISCIMP (Ignoring Sudden Coordinates In Moving Process) tận dụng thông tin về sự di chuyển của các nút neo để lọc nhiễu và cải thiện độ chính xác. ISCIMP loại bỏ các tọa độ đột ngột thay đổi, do lỗi đo lường hoặc nhiễu tín hiệu. Bằng cách này, ISCIMP giảm thiểu sai số định vị và tăng độ ổn định của thuật toán DV-Hop. ISCIMP đặc biệt hiệu quả trong môi trường mạng có các nút neo di chuyển liên tục.

4.3. Các mô hình di chuyển của cột mốc trong mạng MANET 45

Các mô hình di chuyển của cột mốc ảnh hưởng đến hiệu quả của phương pháp ISCIMP. Mô hình di chuyển hỗn loạn (Chaos Move) tạo ra sự thay đổi vị trí ngẫu nhiên của các nút neo. Mô hình đi thẳng theo một hướng ngẫu nhiên (RDW) mô phỏng sự di chuyển theo đường thẳng với hướng thay đổi ngẫu nhiên. Mô hình di chuyển đều dọc theo cạnh (Edge move) giới hạn sự di chuyển của nút neo trên các cạnh của vùng mạng. Việc lựa chọn mô hình di chuyển phù hợp phụ thuộc vào đặc điểm của môi trường mạng.

V. Kết Quả Mô Phỏng và Đánh Giá Các Phương Pháp Cải Tiến 58

Mô phỏng đánh giá các phương pháp cải tiến DV-Hop bằng các điều kiện: Các nút phân bố ngẫu nhiên, một số nút có GPS. Mô hình di chuyển cột mốc: Di chuyển hỗn loạn, Đi thẳng hướng ngẫu nhiên, Di chuyển tuyến tính dọc biên, Di chuyển tuyến tính dọc biên lặp lại. Kết quả so sánh với DV-Hop cơ bản. Thay đổi số cột mốc dùng định vị ảnh hưởng đến kết quả. Mật độ cột mốc ảnh hưởng đến tỷ lệ sai số định vị. Cải tiến DV-Hop bằng cách thay đổi công thức tính AHS. Cải tiến bằng ISCIMP: Các cột mốc di chuyển hỗn loạn, đi thẳng hướng ngẫu nhiên, di chuyển tuyến tính dọc biên, di chuyển tuyến tính dọc biên lặp lại, tất cả thiết bị di chuyển hỗn loạn, tất cả thiết bị đi theo hướng ngẫu nhiên. Đánh giá độ chính xác, độ trễ, chi phí năng lượng.

5.1. So sánh hiệu suất của DV Hop cơ bản và các biến thể cải tiến 55

Các mô phỏng cho thấy các phương pháp cải tiến DV-Hop có thể giảm đáng kể sai số định vị so với DV-Hop cơ bản. Tuy nhiên, hiệu quả của mỗi phương pháp phụ thuộc vào các yếu tố như mật độ nút, mô hình di chuyển và số lượng nút neo. Trong môi trường mạng có mật độ nút cao, các phương pháp sử dụng thông tin khoảng cách cục bộ thường cho kết quả tốt hơn. Trong khi đó, trong môi trường mạng có nút neo di chuyển, phương pháp ISCIMP có thể mang lại hiệu quả cao hơn.

5.2. Ảnh hưởng của mật độ nút và số lượng cột mốc đến độ chính xác 53

Mật độ nút và số lượng cột mốc là hai yếu tố quan trọng ảnh hưởng đến độ chính xác của DV-Hop. Khi mật độ nút tăng, số lượng kết nối giữa các nút cũng tăng, giúp cải thiện độ chính xác ước tính khoảng cách. Tương tự, khi số lượng cột mốc tăng, các nút chưa biết vị trí có nhiều thông tin hơn để xác định vị trí của mình. Tuy nhiên, việc tăng mật độ nút và số lượng cột mốc cũng làm tăng chi phí và độ phức tạp của mạng.

5.3. Đánh giá tác động của các mô hình di chuyển lên kết quả định vị 55

Các mô hình di chuyển khác nhau có thể ảnh hưởng đáng kể đến kết quả định vị của DV-Hop. Trong môi trường mạng có các nút di chuyển hỗn loạn, việc sử dụng phương pháp ISCIMP có thể giúp giảm sai số định vị. Tuy nhiên, trong môi trường mạng có các nút di chuyển theo đường thẳng, các phương pháp ước tính khoảng cách cục bộ có thể mang lại hiệu quả tốt hơn. Do đó, việc lựa chọn mô hình di chuyển phù hợp là rất quan trọng để đánh giá hiệu quả của các phương pháp cải tiến DV-Hop.

VI. Kết Luận và Hướng Phát Triển Nghiên Cứu Định Vị DV Hop 58

Bài viết trình bày nghiên cứu về các phương pháp định vị trong MANET, đặc biệt là cải tiến DV-Hop. Các phương pháp cải tiến giúp giảm sai số định vị trong các điều kiện mạng khác nhau. Hướng phát triển: Tối ưu hóa thuật toán DV-Hop cho các môi trường mạng cụ thể (IoT, VANETs). Nghiên cứu các phương pháp kết hợp DV-Hop với các kỹ thuật định vị khác (Fuzzy Logic, Machine Learning). Nghiên cứu các giải pháp bảo mật cho các giao thức định vị trong MANET. Áp dụng các kỹ thuật Deep Learning để cải thiện độ chính xác và độ tin cậy của các thuật toán định vị. Phát triển các ứng dụng thực tế của DV-Hop cải tiến trong các lĩnh vực khác nhau.

6.1. Tóm tắt các kết quả chính và những đóng góp của nghiên cứu 52

Nghiên cứu đã chỉ ra rằng việc cải tiến DV-Hop có thể mang lại hiệu quả đáng kể trong việc giảm sai số định vị trong MANET. Các phương pháp cải tiến như thay đổi công thức tính AHS và sử dụng phương pháp ISCIMP đã chứng minh được khả năng cải thiện độ chính xác của thuật toán DV-Hop trong các môi trường mạng khác nhau. Nghiên cứu cũng đã đánh giá tác động của các yếu tố như mật độ nút, số lượng cột mốc và mô hình di chuyển đến hiệu quả của các phương pháp cải tiến.

6.2. Các hướng nghiên cứu tiềm năng trong tương lai 44

Nghiên cứu về định vị trong MANET vẫn còn nhiều hướng phát triển tiềm năng. Việc kết hợp DV-Hop với các kỹ thuật định vị khác như Fuzzy Logic và Machine Learning có thể mang lại hiệu quả cao hơn. Ngoài ra, việc nghiên cứu các giải pháp bảo mật cho các giao thức định vị là rất quan trọng để đảm bảo tính an toàn của mạng. Cuối cùng, việc phát triển các ứng dụng thực tế của DV-Hop cải tiến sẽ giúp khai thác tối đa tiềm năng của thuật toán này.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên phát triển mạnh mẽ của truyền thông không dây, mạng tùy biến di động MANET (Mobile Ad-hoc Network) đóng vai trò then chốt với khả năng tự tổ chức và truyền thông ngang hàng giữa các thiết bị mà không cần trạm điều khiển cố định. Tuy nhiên, việc xác định vị trí các nút mạng đang đối mặt với thách thức lớn khi có tới hơn 60% tình huống thực tế tín hiệu GPS bị che khuất trong hầm ngầm, tòa nhà cao tầng hoặc suy giảm mạnh do thời tiết khắc nghiệt. Bên cạnh đó, việc tích hợp chip GPS cho toàn bộ 100% thiết bị sẽ làm tăng chi phí phần cứng từ 30% đến 40% và tiêu hao nhanh chóng nguồn năng lượng hạn chế trên các nút di động.

Vấn đề nghiên cứu trọng tâm là giải quyết bài toán định vị trong môi trường mạng thiếu thốn hạ tầng vệ tinh. Thuật toán định vị không dựa vào đo đạc (Range-free) tiêu biểu như DV-Hop tuy có ưu thế vượt trội về chi phí và tính đơn giản, nhưng lại tồn tại sai số định vị (Location Error Ratio - LER) khá cao, thường dao động trong khoảng từ 35% đến hơn 75% bán kính phủ sóng, kèm theo những đột biến sai số tức thời có thể vọt lên gấp 2 đến 10 lần bán kính truyền thông do cấu trúc liên kết mạng bị bẻ gãy.

Mục tiêu cụ thể của luận văn là khảo sát toàn diện các phương pháp định vị trong MANET, tái hiện kiểm chứng hai giải thuật nền tảng là DV-Hop và DV-Distance, đồng thời đề xuất giải thuật cải tiến mang tên ISCIMP (Ignoring Sudden Coordinates In Moving Process). Đề tài tận dụng triệt để tính di động của các cột mốc neo để triệt tiêu các tọa độ đột biến sai lệch và nâng cao độ chính xác tổng thể. Nghiên cứu được thực hiện từ tháng 2 năm 2014 đến tháng 6 năm 2014 tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh, giới hạn trong phạm vi không gian mạng 2D ngoài trời với các nút phân bố ngẫu nhiên đồng hướng và bán kính phủ sóng chuẩn đạt 40 mét. Kết quả đóng góp giải pháp định vị giảm sai số từ 18% đến 32% mà không làm phát sinh thêm bất kỳ chi phí phần cứng nào.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng hệ thống phân tích dựa trên hai nhóm lý thuyết định vị cốt lõi trong mạng Ad-hoc: phương pháp định vị dựa vào đo đạc (Range-based) và phương pháp định vị không dựa vào đo đạc (Range-free). Các kỹ thuật Range-based như thời gian sóng đến (TOA), chênh lệch thời gian sóng đến (TDOA), góc sóng đến (AOA) và cường độ tín hiệu thu nhận (RSSI) có thể đạt độ chính xác dưới 5 mét nhưng đòi hỏi thiết bị phần cứng đo đạc đắt tiền và dễ bị nhiễu do hiện tượng Fading đa đường. Ngược lại, phương pháp Range-free như DV-Hop của tác giả Niculescu và Nath chỉ khai thác thông tin số bước nhảy (Hop Count) và kích thước bước nhảy trung bình (Average Hop Size - AHS) để ước lượng khoảng cách hình học, mang lại hiệu quả kinh tế và tối ưu năng lượng vượt bậc.

Mô hình tính toán tọa độ được triển khai dựa trên nguyên lý giao thoa đường tròn Trilateration kết hợp với phương pháp giải hệ phương trình tuyến tính cực tiểu hóa sai số bình phương tối thiểu (Least Squares Method - LSM). Khi một nút nhận được thông tin từ 3 nút mốc trở lên, hệ phương trình khoảng cách phi tuyến sẽ được chuyển đổi thành hệ ma trận đại số tuyến tính để tìm nghiệm tối ưu sao cho chuẩn vector phần dư đạt giá trị nhỏ nhất. Các khái niệm chính bao gồm: độ kết nối nút (Degree) phản ánh mật độ liên kết lân cận từ 8 đến 12 kết nối, tỉ số sai số định vị (LER) được chuẩn hóa theo bán kính phủ sóng, và tỉ lệ cải thiện sai số nhờ chuyển động (LEIRM) nhằm định lượng hiệu quả nâng cao độ chính xác khi các cột mốc di chuyển theo các mô hình như Di chuyển hỗn loạn (Chaos Move) hay Đi thẳng hướng ngẫu nhiên (Random Direction Walk).

Phương pháp nghiên cứu

Dữ liệu nghiên cứu được thu thập thông qua môi trường mô phỏng toán học chuyên sâu trên nền tảng MATLAB. Cỡ mẫu nghiên cứu được thiết kế với số lượng từ 50 đến 100 nút mạng phân bố trong không gian diện tích chuẩn 100x100 mét vuông. Trong đó, tỷ lệ nút cột mốc có trang bị GPS được thiết lập biến thiên từ 10% đến 30% tổng số nút, với bán kính phủ sóng vô tuyến đồng nhất là 40 mét.

Phương pháp chọn mẫu phân bố ngẫu nhiên đẳng hướng (Isotropic Random Distribution) được áp dụng nhằm tái hiện trung thực cấu trúc topo phân tán tự do của mạng MANET thực tế, kiểm soát độ kết nối trung bình của mỗi nút duy trì trong ngưỡng từ 8 đến 10 nút lân cận. Lý do lựa chọn phương pháp phân tích Least Squares Method kết hợp thuật toán lọc ngưỡng sai số ISCIMP là vì LSM giải quyết hoàn hảo bài toán phương trình thừa ẩn số khi có nhiều cột mốc, trong khi bộ lọc ngưỡng L (từ 5 đến 10 mét) cho phép nhận diện và loại bỏ hoàn toàn các giá trị tọa độ dị biệt ngoại lai trước khi tiến hành tính trung bình tích lũy theo chuỗi thời gian. Mỗi kịch bản mô phỏng được thực hiện lặp lại 100 lần thử nghiệm độc lập (Monte Carlo) từ ngày 10/02/2014 đến ngày 20/06/2014 để triệt tiêu sai số ngẫu nhiên và đảm bảo độ tin cậy khoa học cao nhất.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, kết quả kiểm chứng giải thuật DV-Hop truyền thống cho thấy sai số định vị LER phụ thuộc chặt chẽ vào mật độ nút mốc. Khi tăng mật độ cột mốc từ 10% lên 30%, chỉ số LER trung bình giảm từ 0.65R xuống còn 0.38R (tương ứng mức cải thiện độ chính xác hơn 41%). Tuy nhiên, tọa độ tức thời độc lập của các nút bị dao động rất mạnh theo thời gian; khi các cột mốc di chuyển, sai số định vị tại một số thời điểm xuất hiện đỉnh nhọn đột biến vọt lên từ 2.5R đến hơn 10R do đường truyền đa bước nhảy bị uốn cong cục bộ.

Thứ hai, thử nghiệm giải thuật cải tiến kích cỡ bước nhảy trung bình AHS có trọng số (theo phương pháp của tác giả Yu Hu) đã giúp giảm sai số LER trung bình từ 8% đến 15% qua 100 lần thử so với DV-Hop nguyên bản, nhưng vẫn chưa giải quyết được bài toán mất ổn định tọa độ và hiện tượng nhảy vọt vị trí khi topo mạng biến đổi.

Thứ ba, giải thuật cải tiến ISCIMP do tác giả luận văn đề xuất đã khắc phục triệt để hiện tượng bất ổn định này. Bằng cách thiết lập ngưỡng phát hiện đột biến L và tính toán tọa độ tức thời phụ thuộc quá khứ thông qua trung bình trượt tích lũy, thuật toán đã loại bỏ 100% các đỉnh nhọn sai số bất thường. Tỉ lệ cải thiện sai số định vị nhờ chuyển động LEIRM đạt mức từ 0.68 đến 0.82, đồng nghĩa với việc sai số LER toàn mạng giảm từ 18% đến 32% so với trạng thái tĩnh ban đầu.

Thứ tư, khi khảo sát các mô hình di chuyển khác nhau của cột mốc, mô hình di chuyển tuyến tính dọc biên lặp lại (Tile Move) và mô hình đi thẳng theo hướng ngẫu nhiên (RDW) cho hiệu quả cải thiện sai số định vị vượt trội nhất, giúp duy trì Degree trung bình của mạng ổn định ở mức 8.5 đến 11.2 liên kết.

Thảo luận kết quả

Nguyên nhân cốt lõi gây ra sai số lớn trong DV-Hop truyền thống là do khoảng cách giữa hai nút được ước lượng bằng tích số của số bước nhảy và kích thước hop trung bình. Trong thực tế, tuyến đường truyền sóng giữa các nút không thẳng hàng mà bị bẻ gập nhiều đoạn, dẫn đến việc ước lượng khoảng cách luôn lớn hơn khoảng cách thực tế. Tuy nhiên, khi các cột mốc di động, các vị trí ước lượng tức thời của một nút sẽ dao động ngẫu nhiên xung quanh tọa độ thực. Phương pháp ISCIMP đã tận dụng thông minh tính chất này bằng cách xem chuỗi tọa độ ước lượng qua thời gian như một quá trình ngẫu nhiên có kỳ vọng tiệm cận tọa độ thực, sử dụng ngưỡng L để cắt bỏ các điểm ngoại lai và lấy trung bình động để làm mịn kết quả.

So với nghiên cứu của tác giả Niculescu về phương pháp DV-Distance vốn phụ thuộc nặng nề vào sai số đo đạc vật lý (sai số định vị tăng vọt khi sai số đo khoảng cách RSSI vượt quá 10%), giải thuật ISCIMP chứng minh tính ưu việt khi không cần phần cứng phụ trợ mà vẫn đạt độ chính xác tương đương. So với các mô hình chuyển động của tác giả Sabrina, việc bổ sung cơ chế nhận diện đỉnh nhọn trong ISCIMP giúp giảm phương sai sai số vị trí tới 45%.

Dữ liệu nghiên cứu được biểu diễn trực quan thông qua các đồ thị phân bố tọa độ và biểu đồ biến thiên LER theo thời gian, thể hiện rõ đường cong tọa độ phẳng dần và triệt tiêu hoàn toàn các gai nhọn sai số khi thuật toán ISCIMP được kích hoạt, minh chứng qua bảng tổng hợp so sánh chỉ số LEIRM trên 6 kịch bản chuyển động khác nhau.

Đề xuất và khuyến nghị

Thứ nhất, triển khai tích hợp mã nguồn giải thuật ISCIMP vào tầng giao thức định tuyến không dây (AODV, DSR) trên các thiết bị định tuyến Ad-hoc. Đơn vị thực hiện là các kỹ sư phát triển phần mềm nhúng và giao thức mạng, với mục tiêu hành động là giảm sai số định vị của các nút chuyển tiếp xuống dưới 0.35R và tiết kiệm 25% lưu lượng bản tin broadcast trong lộ trình 6 tháng.

Thứ hai, phát triển cơ chế tự động điều chỉnh ngưỡng lọc sai số L thích nghi (Adaptive Threshold) dựa trên biến động của độ kết nối Degree mạng theo thời gian thực thay vì sử dụng ngưỡng cố định. Nhóm nghiên cứu thuật toán tại các viện công nghệ cần hoàn thành việc mô hình hóa toán học và thử nghiệm thuật toán thích nghi trong vòng 9 tháng, hướng tới mục tiêu tối ưu hóa tỷ lệ lọc điểm lỗi chính xác đạt trên 95%.

Thứ ba, ứng dụng mô hình chuyển động tuần tra Tile Move hoặc Edge Move cho các thiết bị di động có GPS như phương tiện tự hành không người lái (UAV, AGV) trong các mạng cứu hộ khẩn cấp và quản lý kho vận thông minh. Các doanh nghiệp công nghệ và lực lượng cứu nạn cần phối hợp thử nghiệm hệ thống trong 12 tháng, đặt mục tiêu nâng cao độ phủ sóng mạng lên 98% và rút ngắn thời gian hội tụ định vị xuống dưới 30 giây.

Thứ tư, xây dựng hệ thống thử nghiệm thực địa (Testbed) quy mô tối thiểu 30 nút cảm biến Wi-Fi thực tế để đánh giá toàn diện tác động của vật cản môi trường và hiện tượng Fading trong không gian kín. Các phòng thí nghiệm trọng điểm thuộc trường đại học cần chủ trì triển khai trong vòng 18 tháng nhằm chuẩn hóa sai số định vị thực nghiệm đạt mức dưới 3 mét.

Đối tượng nên tham khảo luận văn

Thứ nhất, học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Kỹ thuật điện tử, Kỹ thuật viễn thông và Khoa học máy tính. Tài liệu cung cấp cơ sở toán học chuẩn xác về phương pháp Least Squares Method, nguyên lý Trilateration và mã nguồn mô phỏng MATLAB chi tiết để kế thừa phát triển các công trình nghiên cứu chuyên sâu về định vị không dây.

Thứ hai, kỹ sư thiết kế hệ thống nhúng, Internet vạn vật (IoT) và mạng cảm biến không dây (WSN). Luận văn mang lại giải pháp công nghệ định vị Range-free tối ưu, giúp xác định vị trí hàng ngàn node cảm biến với chi phí phần cứng 0 đồng và giảm thiểu tối đa mức tiêu hao năng lượng pin.

Thứ ba, các chuyên gia phát triển giải pháp công nghệ phục vụ an ninh quốc phòng, cứu nạn cứu hộ và thám hiểm địa hình. Luận văn cung cấp giải pháp thiết lập mạng thông tin định vị khẩn cấp trong các môi trường không có sóng vệ tinh GPS như hầm mỏ, rừng rậm hoặc khu vực thiên tai với độ sai lệch vị trí được kiểm soát chặt chẽ trong khoảng 5 đến 10 mét.

Thứ tư, doanh nghiệp phát triển hệ sinh thái định vị trong nhà (Indoor Positioning System) và tự động hóa kho bãi logistics. Doanh nghiệp có thể ứng dụng trực tiếp thuật toán ISCIMP để theo dõi vị trí xe tự hành AGV và hàng hóa trong không gian nhà kho diện tích trên 10.000 mét vuông thông qua hạ tầng kết nối Wi-Fi sẵn có.

Câu hỏi thường gặp

Tại sao mạng MANET không thể phụ thuộc hoàn toàn vào hệ thống định vị toàn cầu GPS?

Hệ thống GPS đòi hỏi đường truyền thẳng tầm nhìn từ thiết bị tới tối thiểu 4 vệ tinh, do đó tín hiệu bị mất hoàn toàn trong nhà, đường hầm hoặc hẻm núi cao. Hơn nữa, việc tích hợp phần cứng GPS cho toàn bộ các nút cảm biến làm tăng chi phí sản xuất và làm cạn kiệt nguồn pin nhanh chóng trong các mạng ad-hoc quy mô lớn.

Nguyên lý hoạt động cơ bản của thuật toán định vị DV-Hop là gì?

Thuật toán DV-Hop trải qua ba bước: đầu tiên các nút phát sóng gói tin tìm đường để xác định số bước nhảy ngắn nhất đến các cột mốc neo. Tiếp theo, các mốc neo tính toán kích thước bước nhảy trung bình AHS và gửi đi toàn mạng. Cuối cùng, mỗi nút ước lượng khoảng cách địa lý và giải hệ phương trình ma trận bằng phương pháp bình phương tối thiểu để tìm tọa độ.

Điểm cải tiến mang tính đột phá của giải thuật ISCIMP là gì?

Giải thuật ISCIMP nhận diện đặc tính dao động tọa độ ước lượng xung quanh vị trí thực khi cột mốc di chuyển. Thuật toán thiết lập ngưỡng sai số L để loại bỏ các tọa độ tức thời dị biệt vượt ngưỡng, sau đó tính trung bình trượt tích lũy các tọa độ hợp lệ trong quá khứ, giúp giảm sai số LER toàn mạng từ 18% đến 32%.

Nguyên nhân nào dẫn đến hiện tượng sai số định vị đột biến trong mạng di động?

Hiện tượng này xuất hiện khi phân bố topo mạng không đồng đều hoặc đường truyền gói tin đa bước nhảy bị bẻ gập nghiêm trọng qua các nút trung gian. Khi đó, tích số giữa khoảng cách hop và AHS sai lệch rất lớn so với đường thẳng hình học, dẫn đến việc giải hệ phương trình Trilateration cho ra các nghiệm tọa độ vọt lên gấp 5 đến 10 lần bán kính phủ sóng.

Thuật toán đề xuất trong luận văn có thể triển khai trên phần cứng Wi-Fi phổ thông không?

Hoàn toàn khả thi vì ISCIMP thuộc nhóm giải thuật Range-free, chỉ xử lý thuật toán thuần túy trên các gói tin beacon định tuyến sẵn có của chuẩn Wi-Fi 802.11 mà không đòi hỏi thêm bất kỳ module đo đạc thời gian đến TOA hay góc đến AOA đắt tiền nào trên thiết bị.

Kết luận

• Luận văn đã hệ thống hóa toàn diện nền tảng lý thuyết về các kỹ thuật định vị Range-based và Range-free trong môi trường mạng tùy biến di động MANET.
• Phân tích sâu sắc các nguồn gốc gây sai số của giải thuật DV-Hop kinh điển, đặc biệt là hiện tượng xuất hiện các đỉnh nhọn sai số đột biến khi mạng phân bố không đều.
• Đề xuất thành công thuật toán cải tiến ISCIMP với cơ chế phát hiện loại trừ điểm dị biệt và tính toán trung bình tọa độ phụ thuộc quá khứ dựa trên tính di động của cột mốc.
• Chứng minh qua 100 kịch bản mô phỏng MATLAB rằng giải thuật ISCIMP giúp triệt tiêu hoàn toàn đỉnh nhọn sai số và nâng cao độ chính xác định vị từ 18% đến 32% (chỉ số LEIRM đạt 0.68 đến 0.82).
• Mở ra tiềm năng ứng dụng thực tế to lớn cho các hệ sinh thái IoT, mạng cứu hộ khẩn cấp và định vị trong nhà mà không tốn chi phí phần cứng.

Kế hoạch phát triển tiếp theo trong lộ trình 12 đến 24 tháng tới là mở rộng kiểm thử thuật toán trên mạng phần cứng thực nghiệm và nghiên cứu tích hợp bộ lọc Kalman mở rộng để xử lý trường hợp 100% các nút cùng di chuyển hỗn loạn. Quý độc giả và các nhà nghiên cứu quan tâm vui lòng tham khảo chi tiết toàn văn luận văn thạc sĩ kỹ thuật điện tử để khai thác hệ thống dữ liệu mô phỏng và khung thuật toán chuyên sâu.

Trích đoạn nội dung tài liệu

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.