Nghiên Cứu Phương Pháp Định Vị Trong Mạng MANET Và Cải Tiến Kỹ Thuật DV-Hop Bởi Đỗ Nguyễn Minh Tuấn

Tài liệu nghiên cứu Đỗ nguyễn minh tuấn        nghiên cứu các phương pháp định vị trong manet cải tiến phương pháp dvhop, tổng hợp lý thuyết và thực hành, cung cấp kiến thức

• 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: Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh
• 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 và 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: Thành phố 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. Giới thiệu MANET

MANET (Mobile Ad hoc Network) là một mạng không dây tự tổ chức, không cần cơ sở hạ tầng cố định. Các thiết bị trong mạng này có thể di chuyển tự do và kết nối với nhau thông qua các liên kết không dây. MANET thường được sử dụng trong các tình huống khẩn cấp, quân sự, hoặc các ứng dụng di động. Một trong những thách thức lớn của MANET là việc xác định vị trí của các nút mạng, đặc biệt khi không có sẵn hệ thống GPS. Điều này dẫn đến nhu cầu nghiên cứu các phương pháp định vị hiệu quả trong MANET.

1.1. Định vị trong MANET

Định vị trong MANET là quá trình xác định vị trí của các nút mạng di động. Việc này rất quan trọng cho các giao thức định tuyến dựa trên vị trí và các ứng dụng thực tế như cứu nạn, du lịch, và quản lý mạng. Mặc dù GPS là giải pháp phổ biến, nhưng trong nhiều trường hợp, GPS không khả thi do hạn chế về tín hiệu hoặc chi phí. Do đó, các phương pháp định vị không dựa trên GPS như DV-Hop được nghiên cứu và cải tiến để đáp ứng nhu cầu này.

II. Phương pháp DV Hop

DV-Hop là một phương pháp định vị phổ biến trong MANET, sử dụng thông tin về số lượng hop giữa các nút để ước tính khoảng cách. Phương pháp này không yêu cầu thiết bị hỗ trợ GPS, giúp giảm chi phí và tăng tính linh hoạt. Tuy nhiên, DV-Hop có nhược điểm là sai số lớn khi mạng phân bố không đều hoặc có vật cản. Để khắc phục, các nghiên cứu đã đề xuất cải tiến DV-Hop bằng cách sử dụng thông tin di động của các nút mạng.

2.1. Cải tiến DV Hop

Một trong những cải tiến nổi bật là phương pháp ISCIMP (Ignoring Sudden Coordinates In Moving Process), được đề xuất bởi Đỗ Nguyễn Minh Tuấn. ISCIMP tập trung vào việc loại bỏ các tọa độ đột ngột trong quá trình di chuyển của các nút mạng, giúp giảm sai số định vị. Phương pháp này đặc biệt hiệu quả trong các mạng có mật độ nút cao và phân bố ngẫu nhiên. Kết quả thử nghiệm cho thấy ISCIMP cải thiện đáng kể độ chính xác của DV-Hop.

III. Ứng dụng thực tế

Các phương pháp định vị trong MANET, đặc biệt là DV-Hop và ISCIMP, có nhiều ứng dụng thực tế. Chúng có thể được sử dụng để định vị trong các tòa nhà, hội chợ, hoặc các khu vực không có tín hiệu GPS. Ngoài ra, các phương pháp này cũng hỗ trợ các thiết bị không được trang bị GPS, như laptop, máy tính bảng, hoặc các cảm biến trong mạng IoT. Điều này mở ra nhiều cơ hội ứng dụng trong thương mại, công nghiệp, và quản lý kho bãi.

3.1. Hướng phát triển

Trong tương lai, các nghiên cứu về định vị trong MANET sẽ tập trung vào việc tích hợp các phương pháp định vị với các công nghệ mới như AI và Machine Learning. Điều này sẽ giúp tăng độ chính xác và giảm thời gian tính toán. Ngoài ra, việc áp dụng các phương pháp định vị trong các mạng di động 5G cũng là một hướng nghiên cứu tiềm năng.

Nội dung chính

Tổng quan nghiên cứu

Mạng tùy biến không dây di động (MANET) là cấu trúc mạng cục bộ tự trị hình thành từ 100% các thiết bị di động liên lạc ngang hàng thông qua sóng vô tuyến mà không cần hạ tầng trạm phát cố định. Mặc dù hệ thống định vị toàn cầu GPS rất phổ biến, việc trang bị chip GPS cho toàn bộ các nút mạng thường bị hạn chế do chi phí phần cứng, mức tiêu thụ năng lượng cao và hiện tượng mất sóng nghiêm trọng trong nhà hầm, tòa nhà cao tầng hoặc thời tiết xấu. Khi khởi động ngoài trời, GPS cũng đòi hỏi khoảng thời gian chờ từ 3 đến 5 phút để hoàn tất việc xác định tọa độ ban đầu. Vấn đề cốt lõi đặt ra là làm thế nào để xác định vị trí địa lý của các nút mạng chưa biết tọa độ với độ chính xác cao trong điều kiện chỉ có khoảng 10% đến 20% số nút trong mạng được tích hợp GPS (nút cột mốc hay anchor).

Mục tiêu cụ thể của luận văn là nghiên cứu, đánh giá toàn diện các kỹ thuật định vị trong MANET, tái lập thuật toán định vị không dùng đo đạc khoảng cách DV-Hop và thuật toán DV-Distance, từ đó đề xuất giải pháp cải tiến mang tên ISCIMP (Ignoring Sudden Coordinates In Moving Process). Đề tài tập trung giải quyết bài toán định vị trong môi trường phân bố ngẫu nhiên đẳng hướng, bán kính phủ sóng trung bình của mỗi nút đạt 40 mét. Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc tối ưu hóa tỷ số sai số định vị (Location Error Ratio - LER), ngăn chặn các bước nhảy tọa độ bất thường có thể vọt lên tới mức sai số gấp 10 lần bán kính truyền sóng khi các nút di chuyển. Kết quả nghiên cứu đóng góp giải pháp kỹ thuật có tính ứng dụng cao cho công tác cứu hộ khẩn cấp, giám sát kho bãi thông minh và quản lý thiết bị di động trong điều kiện GPS bị cô lập.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng các mô hình hình học không gian và giải thuật định vị mạng cảm biến không dây:

• Phương pháp định vị giao thoa hình học (Trilateration) và phương pháp lượng giác (Triangulation): Kỹ thuật Trilateration xác định vị trí giao điểm của ít nhất 3 đường tròn hình học phẳng khi biết tọa độ tâm và khoảng cách ước lượng từ nút cần định vị tới các cột mốc. Kỹ thuật Triangulation sử dụng góc sóng đến (Angle of Arrival - AOA) để tính toán tọa độ tam giác.
• Phương pháp bình phương bé nhất (Least Squares Method - LSM): Khi số lượng phương trình khoảng cách lớn hơn số ẩn số tọa độ cần tìm (hệ phương trình $y = Ax$ với $m > n$), LSM tìm kiếm vector nghiệm tối ưu sao cho chuẩn sai số Euclidean đạt giá trị cực tiểu theo công thức nghiệm $x = (A^T A)^{-1} A^T y$.
• Thuật toán định vị DV-Hop cổ điển của Niculescu và Nath: Gồm 3 giai đoạn: (1) Lan truyền gói tin tìm đường dạng Distance Vector để đếm số bước nhảy (Hop Count) giữa mọi cặp nút; (2) Các cột mốc tính toán kích thước bước nhảy trung bình (Average Hop Size - AHS) và quảng bá trên toàn mạng; (3) Các nút tự do ước lượng khoảng cách địa lý bằng tích số giữa Hop Count và AHS, sau đó áp dụng phép toán LSM để giải tọa độ.
• Mô hình hiệu chỉnh trung bình bước nhảy có trọng số của Yu Hu: Tinh chỉnh công thức AHS của từng nút thông qua trọng số $W_i$ tỷ lệ nghịch với khoảng cách bước nhảy tới từng cột mốc, giúp giảm thiểu độ lệch khoảng cách ở các khu vực biên mạng.
• Thuật toán đề xuất ISCIMP: Khai thác tính di động của các nút cột mốc để thu thập chuỗi tọa độ ước lượng tức thời độc lập qua các thời điểm $t_1, t_2, ..., t_k$, thiết lập ngưỡng sai lệch $L$ để nhận diện và loại bỏ các đỉnh nhọn dị biệt (spikes), sau đó tính trung bình trượt tích lũy nhằm tạo ra tọa độ tức thời phụ thuộc quá khứ có độ ổn định vượt trội.

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

Nghiên cứu áp dụng phương pháp mô phỏng số lượng nghiệm trên nền tảng ngôn ngữ kỹ thuật MATLAB. Nguồn dữ liệu mô phỏng được sinh ngẫu nhiên theo mô hình không gian hai chiều đẳng hướng với các tham số mạng chuẩn hóa:

• Cỡ mẫu và thiết kế mô phỏng: Tập mẫu gồm 100 lần chạy thử nghiệm độc lập cho mỗi kịch bản để loại trừ sai số ngẫu nhiên. Mạng khảo sát gồm 100 nút mạng phân bố trên vùng không gian xác định với bán kính phủ sóng vô tuyến $R = 40$ mét.
• Phương pháp chọn mẫu: Lựa chọn ngẫu nhiên vị trí các nút theo phân bố đều (uniform distribution), đảm bảo độ kết nối trung bình của mạng (Degree) duy trì ổn định trong khoảng từ 8 đến 12 láng giềng trên mỗi nút. Tỷ lệ cột mốc trang bị GPS được biến thiên từ 10% đến 30% tổng số nút.
• Lý do lựa chọn phương pháp: Mô phỏng số trên MATLAB là phương pháp tối ưu và khả thi nhất để kiểm soát chặt chẽ các thông số topo mạng MANET, cho phép giả lập linh hoạt các mô hình di chuyển động (Chaos Move, Random Direction Walk, Edge Move, Tile Move) và thu thập chuỗi dữ liệu tọa độ theo thời gian thực mà không gặp rào cản về chi phí trang bị hàng trăm thiết bị phần cứng đo đạc thực địa.

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

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

Quá trình thực nghiệm và phân tích mô phỏng đã mang lại 4 phát hiện khoa học quan trọng:

• Phát hiện 1 - Sai số và sự mất ổn định của DV-Hop cơ bản: Trong điều kiện mạng tĩnh, DV-Hop cơ bản cho tỷ số sai số định vị LER trung bình từ 0.45 đến 0.75. Tuy nhiên, khi các nút chuyển động, đường truyền bước nhảy bị bẻ cong khiến sai số tức thời không ổn định và xuất hiện các đỉnh nhọn đột biến với LER vượt ngưỡng 10.0 tại một số thời điểm ngẫu nhiên.
• Phát hiện 2 - Tác động của mật độ cột mốc: Khi tăng tỷ lệ nút cột mốc từ 10% lên 30% trong mạng 100 nút, tỷ số LER trung bình giảm khoảng 32%, từ mức 0.68 xuống còn 0.46. Đồng thời, việc sử dụng từ 4 đến 6 cột mốc để lập hệ phương trình LSM giúp ma trận hiệp phương sai ổn định hơn 25% so với trường hợp chỉ dùng tối thiểu 3 cột mốc.
• Phát hiện 3 - Hiệu quả triệt tiêu đỉnh nhọn của giải thuật ISCIMP: Bằng cách thiết lập ngưỡng lọc biến thiên $L = 5$ mét, thuật toán ISCIMP đã loại bỏ hoàn toàn 100% các đỉnh nhọn sai số đột biến trong suốt quá trình di chuyển của các cột mốc, giúp quỹ đạo ước lượng không còn bị rung lắc gián đoạn.
• Phát hiện 4 - Mức độ cải thiện sai số qua các mô hình di chuyển: Chỉ số cải thiện sai số nhờ chuyển động LEIRM đạt giá trị từ 0.62 đến 0.80 (tương đương với việc giảm từ 20% đến 38% sai số LER toàn mạng). Trong đó, mô hình di chuyển lặp lại dọc biên chia ô (Tile Move) với 12 cột mốc bố trí trên 4 ô đạt hiệu quả định vị tối ưu nhất, duy trì sai số LER dưới mức 0.28.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sai số lớn trong DV-Hop truyền thống là do giả định khoảng cách địa lý tỷ lệ tuyến tính với số bước nhảy hop. Trong thực tế, các nút mạng phân bố không đồng đều làm cho kích thước bước nhảy thực tế dao động từ 15 mét đến 38 mét thay vì bằng giá trị trung bình AHS. Khi các cột mốc di chuyển, topo mạng thay đổi liên tục khiến đường dẫn ngắn nhất giữa hai nút chuyển đổi đột ngột giữa các tuyến khác nhau, gây ra hiện tượng nhảy vọt tọa độ.

So với phương pháp cải tiến AHS có trọng số của Yu Hu (chỉ cải thiện khoảng 8% đến 12% LER trên mạng tĩnh), giải pháp ISCIMP khai thác triệt để tính lịch sử của tọa độ trong môi trường động. Khi trực quan hóa dữ liệu qua biểu đồ đường theo 25 chu kỳ thời gian định vị và bảng phân tích so sánh chỉ số LEIRM giữa các mô hình di chuyển, tọa độ sau khi lọc qua ISCIMP tạo thành đường tiệm cận phẳng bám sát tọa độ thực tế của nút mạng. Biểu đồ phân tán tọa độ 2D cho thấy vùng phân tán sai số bị thu hẹp đáng kể, chứng minh rằng tính di động của cột mốc nếu được xử lý qua bộ lọc đột biến sẽ trở thành một lợi thế kỹ thuật thay vì là nguồn gây nhiễu cho mạng MANET.

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

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đưa ra 4 khuyến nghị kỹ thuật cụ thể:

• Tích hợp thuật toán lọc ISCIMP vào firmware thiết bị IoT không dây: Các kỹ sư phát triển phần mềm nhúng nên nhúng trực tiếp khối thuật toán lọc tọa độ phụ thuộc quá khứ vào tầng ứng dụng của nút mạng nhằm duy trì tỷ số sai số LER dưới mức 0.30, hoàn thành trong khung thời gian từ 3 đến 6 tháng thử nghiệm phòng lab.
• Chuẩn hóa quy hoạch quỹ đạo di chuyển của các nút mốc theo mô hình Tile Move: Nhóm thiết kế mạng MANET và điều khiển robot tự hành cần thiết lập lộ trình tuần tra của các nút mang GPS dọc theo các cạnh phân ô của khu vực giám sát, nhằm nâng cao độ phủ sóng hữu hiệu của cột mốc lên trên 95% diện tích mục tiêu trong vòng 6 tháng.
• Tối ưu hóa cơ chế điều chỉnh ngưỡng lọc sai số thích nghi tự động: Bộ phận nghiên cứu và phát triển thuật toán viễn thông cần bổ sung module tự động cập nhật ngưỡng sai lệch $L$ theo bán kính phủ sóng thực tế và mật độ kết nối cục bộ, triệt tiêu trên 99% các giá trị tọa độ ngoại lai trong thời gian 3 tháng.
• Ứng dụng mô hình định vị lai kết hợp thông số cường độ sóng RSSI: Các doanh nghiệp cung cấp giải pháp định vị trong nhà và quản lý kho hàng nên tích hợp thuật toán DV-Hop cải tiến với kỹ thuật đo RSSI ở khoảng cách ngắn để đạt độ chính xác định vị dưới 2.5 mét, lộ trình triển khai hoàn thiện trong 12 tháng.

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

• Kỹ sư thiết kế hệ thống IoT và mạng cảm biến không dây: Ứng dụng giải pháp định vị không dùng GPS để quản lý vị trí hàng hóa trong kho bãi kín, hầm mỏ hoặc nhà xưởng công nghiệp với chi phí phần cứng tối thiểu.
• Học viên cao học và nghiên cứu sinh chuyên ngành Kỹ thuật Điện tử - Viễn thông: Sử dụng toàn bộ mã nguồn mô phỏng MATLAB và khung lý thuyết giải hệ phương trình Least Squares Method làm tài liệu tham khảo cho các đề tài nghiên cứu về tối ưu hóa mạng tùy biến.
• Nhà phát triển hệ thống điều khiển bầy đàn robot và thiết bị bay không người lái (UAV): Áp dụng mô hình cột mốc di động Tile Move để thiết lập mạng lưới định vị dẫn đường tương hỗ giữa các thiết bị tự hành trong môi trường không có sóng vệ tinh.
• Giảng viên và chuyên gia giảng dạy mạng máy tính: Khai thác các ví dụ tính toán từng bước của giải thuật DV-Hop, DV-Distance và các mô hình di chuyển ngẫu nhiên làm học liệu giảng dạy chuyên đề mạng không dây nâng cao.

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

• Thuật toán DV-Hop cơ bản gặp phải những nhược điểm cốt lõi nào trong mạng MANET? DV-Hop cơ bản có sai số lớn (LER dao động từ 0.45 đến 0.75) do giả định kích thước bước nhảy là cố định. Khi các nút di chuyển, topo mạng thay đổi liên tục tạo ra các đường truyền bị gấp khúc, dẫn đến hiện tượng tọa độ bị nhảy vọt đột biến với sai số có thể gấp 10 lần bán kính phát sóng.
• Thuật toán ISCIMP xử lý hiện tượng nhảy vọt tọa độ đột biến bằng cách nào? ISCIMP thiết lập ngưỡng sai lệch tọa độ $L = 5$ mét giữa hai chu kỳ liên tiếp. Nếu tọa độ tức thời vượt quá ngưỡng này, hệ thống sẽ nhận diện là đỉnh nhọn sai số và tạm thời loại bỏ. Tọa độ cuối cùng được tính bằng trung bình cộng tích lũy của các giá trị hợp lệ trong quá khứ.
• Tại sao định vị không dựa vào đo đạc (Range-free) lại phù hợp cho mạng MANET hơn phương pháp Range-based? Phương pháp Range-free như DV-Hop chỉ dựa vào thông tin kết nối và số bước nhảy, không đòi hỏi phần cứng đo khoảng cách hay góc sóng phức tạp (như TOA hay AOA). Điều này giúp tiết kiệm trên 60% chi phí phần cứng và giảm tiêu hao năng lượng cho các thiết bị di động nhỏ gọn.
• Mô hình di chuyển nào của các nút cột mốc mang lại hiệu quả định vị tốt nhất? Mô hình di chuyển dọc biên lặp lại theo phân ô (Tile Move) với 12 cột mốc chia thành 4 ô mang lại hiệu quả cao nhất, giúp chỉ số LEIRM giảm xuống mức 0.62 (cải thiện 38% độ chính xác) và giữ cho mức độ kết nối mạng luôn ổn định quanh giá trị 10 láng giềng.
• Phương pháp bình phương bé nhất (Least Squares Method) có vai trò gì trong định vị? Do sai số trong việc ước lượng khoảng cách và vị trí cột mốc, các đường tròn định vị không cắt nhau tại một điểm duy nhất mà tạo thành một miền nghiệm. LSM giải quyết hệ phương trình dư số, tìm ra tọa độ tối ưu có tổng bình phương khoảng cách sai lệch là nhỏ nhất.

Kết luận

• Luận văn đã hệ thống hóa toàn diện các lý thuyết định vị trong mạng MANET, chỉ rõ nguyên nhân gây ra sai số và hiện tượng mất ổn định tọa độ của giải thuật DV-Hop truyền thống.
• Đề xuất thành công thuật toán cải tiến ISCIMP kết hợp cơ chế loại bỏ đỉnh nhọn sai số đột biến và tính toán trung bình tọa độ tích lũy theo thời gian.
• Chứng minh thực nghiệm qua 100 lần mô phỏng độc lập trên MATLAB rằng ISCIMP giúp cải thiện từ 20% đến 38% tỷ số sai số định vị (LER), triệt tiêu hoàn toàn các bước nhảy tọa độ dị biệt khi các cột mốc di chuyển.
• Xác lập mô hình di chuyển phân ô lặp lại (Tile Move) là cấu hình tối ưu nhất cho mạng MANET có cột mốc cơ động, đạt độ chính xác cao hơn 35% so với di chuyển hỗn loạn.
• Định hình lộ trình phát triển từ 3 đến 12 tháng nhằm mở rộng thuật toán sang mô hình không gian 3 chiều và tích hợp dữ liệu RSSI hiệu chuẩn. Các kỹ sư và nhà nghiên cứu có thể tải về tài liệu toàn văn và mã nguồn mô phỏng để ứng dụng trực tiếp vào các dự án mạng không dây tự hành.

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.