đặt vấn đề, phát biểu bài toán và mục tiêu của luận án, tóm tắt nội dung và những đóng góp chính của luận án. - Chương 2 trình bày kết quả nghiên cứu tổng quan về định vị và định tuyến đơn phát dựa trên thông tin vị trí. Các bài toán định vị, phát hiện biên, và định tuyến đơn phát dựa trên thông tin vị trí đƣợc phát biểu. Các công trình liên quan đến các bài toán nói trên đƣợc khảo sát và trình bày tóm tắt.
Chƣơng 2 kết thúc với một số nhận xét về những giải pháp đã có. - Chương 3 trình bày một thuật toán phát hiện biên dựa trên kết nối đƣợc đề xuất. Mục đích thiết kế, nội dung thuật toán, đánh giá và so sánh hiệu năng của thuật 19 toán đƣợc đề xuất với những thuật toán đã có, cùng với hƣớng phát triển lần lƣợt đƣợc trình bày. - Chương 4 trình bày một giao thức đƣợc đề xuất nhằm tối ƣu hóa đƣờng đi trong định tuyến đơn phát dựa trên thông tin vị trí.
Kỹ thuật tối ƣu hóa đƣờng đi giúp nâng cao hiệu năng của giao thức định tuyến đơn phát một cách rõ rệt và đƣợc kiểm chứng qua mô phỏng. Mục đích thiết kế giao thức, nội dung giao thức, đánh giá hiệu năng của giao thức, hƣớng nghiên cứu cải tiến giao thức lần lƣợt đƣợc trình bày. - Chương 5 trình bày một giao thức khác đƣợc đề xuất nhằm nâng cao hiệu năng định tuyến đơn phát dựa trên thông tin vị trí bằng việc sử dụng cạnh tranh kết hợp không sử dụng gói tin chào hỏi. Mục đích thiết kế giao thức, nội dung giao thức, đánh giá hiệu năng của giao thức, hƣớng nghiên cứu cải tiến giao thức lần lƣợt đƣợc trình bày.
- Luận án kết thúc với phần kết luận tổng kết các kết quả chính của luận án và giới thiệu một số hƣớng nghiên cứu mở rộng tiếp theo. Ngoài nội dung chính đƣợc trình bày trong các chƣơng kể trên, những nội dung tham khảo hoặc mở rộng đƣợc trình bày trong hai phụ lục: - Phụ lục 1 trình bày các phƣơng pháp ƣớc lƣợng khoảng cách và ƣớc lƣợng góc đƣợc áp dụng trong định vị. - Phụ lục 2 trình bày cơ sở toán học của phƣơng pháp định vị theo đa khoảng cách.6 Đóng góp của luận án Những đóng góp chính của luận án bao gồm: - Đề xuất một thuật toán phát hiện biên dựa trên kết nối có độ phức tạp tính toán và truyền thông thấp, có thể làm việc tốt trên cả các mạng cảm biến có mật độ thấp. Theo thuật toán này, mỗi nút đánh giá đồ thị vùng lân cận 2 chặng của nó để quyết định nó có nằm gần biên hay không.
Một nút nằm gần biên khi và chỉ khi đồ thị vùng lân cận 2 chặng của nó không tạo thành một cái vành. Việc xây dựng và đánh giá đồ thị vùng lân cận 2 chặng đơn giản và ít tốn kém. 20 - Đề xuất một giao thức tối ƣu hóa đƣờng đi có tên Greedy with Path Optimization Routing (GPOR) cho mạng cảm biến không dây. Theo giao thức này, các đƣờng đi ban đầu đƣợc tìm bằng việc áp dụng chuyển tiếp tham lam và kỹ thuật đi theo biên, tiếp đó các đƣờng tắt đƣợc tạo và sử dụng nhằm rút ngắn các đƣờng đi, đồng thời tránh cực tiểu địa phƣơng.
Các đƣờng đi đƣợc rút ngắn và đẩy ra xa biên, do vậy giảm tải cho các nút biên và đạt cân bằng tải tốt hơn. Các phần tử định tuyến có thể áp dụng cho một vùng đích thay vì chỉ một nút đích nhƣ các giao thức đã có. - Đề xuất một giao thức định tuyến dựa trên thông tin vị trí không sử dụng gói tin chào hỏi có tên là Hybrid Contention-Based Geographic Routing (HCGR) sử dụng đồng thời hai hình thức cạnh tranh, đƣợc gọi là cạnh tranh kết hợp. Cạnh tranh quyết liệt đƣợc sử dụng trƣớc.
Nếu cạnh tranh quyết liệt thành công, cạnh tranh không quyết liệt sẽ bị hủy bỏ. Ngƣợc lại, tức cạnh tranh quyết liệt thất bại, cạnh tranh không quyết liệt sẽ đƣợc dùng để chuyển tiếp gói tin. Do đó, HCGR có thể làm cực đại tỉ lệ chuyển gói thành công trong khi giữ đƣợc độ phức tạp thông báo và trễ ở mức tƣơng đối thấp. Ngoài cạnh tranh kết hợp, một biến thể của kỹ thuật đi theo biên sử dụng cạnh tranh kết hợp cũng đƣợc đề xuất.1 thể hiện trực quan về các bài toán đƣợc quan tâm cùng những đề xuất đã đƣợc đƣa ra nhằm giải quyết các bài toán này.
21 Các nút có Sai thông tin vị Phát hiện biên dựa trên kết nối trí Định vị Định vị bằng việc sử dụng đồ thị Delaunay Đúng kết hợp định vị theo khoảng cách Định tuyến đơn phát Chuyển tiếp tham lam và đi theo biên Nâng cao hiệu Tối ƣu hóa Cạnh tranh kết năng đƣờng đi hợp Các công trình liên quan Nội dung được đề xuất Hình 1. Giải pháp đƣợc đề xuất. 22 CHƢƠNG 2 TỔNG QUAN VỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN VỊ TRÍ Chƣơng này trình bày tổng quan các vấn đề định vị và định tuyến đơn phát dựa trên thông tin vị trí trong mạng cảm biến không dây, tóm tắt nội dung và đánh giá các thuật toán và giao thức đã có nhằm làm cơ sở cho các đề xuất đƣợc trình bày ở các chƣơng tiếp theo. Những nội dung sau đây đƣợc trình bày trong chƣơng này: - Vấn đề định vị.
- Tổng quan về các thuật toán định vị. - Vấn đề phát hiện biên. - Tổng quan về các thuật toán phát hiện biên. - Tổng quan về định tuyến đơn phát dựa trên thông tin vị trí.
- Nhận xét về các thuật toán đã có.1 Định vị Trong định tuyến dựa trên thông tin vị trí, vị trí hay tọa độ của các nút là thông tin thiết yếu. Thông tin này có thể nhận đƣợc bằng việc sử dụng các hệ thống định vị nhƣ GPS. Tuy nhiên, việc sử dụng các hệ thống định vị sẽ tốn kém về mặt kinh tế. Ngoài ra, các thiết bị định vị sẽ tiêu tốn nhiều năng lƣợng dẫn đến làm giảm tuổi thọ của các nút cảm biến.
Trong một số môi trƣờng, ví dụ trong nhà, các thiết bị định vị không phát huy tác dụng. Một vấn đề nữa là sự thiếu thuận tiện trong việc trang bị thiết bị định vị cho các nút cảm biến có kích thƣớc nhỏ. Với những hạn chế kể trên của hệ thống định vị, một 23 phƣơng pháp khác kinh tế và hiệu quả hơn đƣợc áp dụng để xác định tọa độ của các nút là sử dụng các thuật toán định vị. Không hoặc một số ít các nút, còn gọi là điểm neo, đƣợc trang bị thiết bị định vị và do đó biết tọa độ của chúng, tọa độ của những nút còn lại sẽ đƣợc tính toán bằng thuật toán định vị.
Các thuật toán định vị đã đƣợc đề xuất đƣợc chia thành hai lớp chính là dựa trên khoảng (range-based) và dựa trên kết nối (connectivity-based), tùy theo thông tin về ƣớc lƣợng khoảng hay thông tin về kết nối giữa các nút đƣợc sử dụng để xác định tọa độ của các nút. Có thể tiếp tục chia định vị dựa trên khoảng thành hai lớp nhỏ hơn là định vị theo khoảng cách (lateration) và định vị theo góc (angulation) tùy theo thông tin về khoảng cách hay thông tin về góc đƣợc sử dụng3. Với định vị theo khoảng cách [61, 97], trƣờng hợp đơn giản nhất là một nút có thông tin chính xác về khoảng cách từ nó đến ba điểm neo không thẳng hàng. Sử dụng các khoảng cách và vị trí các điểm neo, vị trí của một nút là ở giao điểm của ba đƣờng tròn có tâm ở ba điểm neo.
Vấn đề là trong thực tế các ƣớc lƣợng khoảng cách thƣờng không chính xác dẫn đến ba đƣờng tròn không giao nhau tại một điểm. Để khắc phục điều này, ƣớc lƣợng khoảng cách đến nhiều hơn ba điểm neo đƣợc sử dụng, dẫn đến bài toán định vị theo đa khoảng cách (multilateration)4. Định vị theo góc [72] khai thác tính chất nếu biết hai đỉnh, độ dài hai cạnh hoặc độ lớn hai góc của một tam giác thì sẽ biết đƣợc vị trí của điểm thứ ba là giao điểm của hai cạnh còn lại. Ƣớc lƣợng không chính xác cũng có thể xảy ra và có thể khắc phục bằng đa ƣớc lƣợng.
Để có thông tin ƣớc lƣợng khoảng ngoại trừ RSSI [61], các phần cứng phụ trợ đƣợc yêu cầu. Các phần cứng phụ trợ này dẫn đến các hạn chế nhƣ thiết bị định vị. Hơn nữa, độ chính xác trong ƣớc lƣợng do các thiết bị mang lại có thể bị ảnh hƣởng do tác động của môi trƣờng [67]. Ngoài ra, để thông tin ƣớc lƣợng khoảng có ích, phải có một số lƣợng đủ lớn các điểm neo đƣợc phân bố đồng đều.
Nhìn chung, định vị dựa trên khoảng 3 Ƣớc lƣợng khoảng cách và góc đƣợc trình bày trong Phụ lục 1. 4 Cơ sở toán học cho định vị theo khoảng cách đƣợc trình bày trong Phụ lục 2. 24 có thể áp dụng cho các hệ thống khác nhƣng không phù hợp cho mạng cảm biến không dây. Khác với định vị dựa trên khoảng, định vị dựa trên kết nối chỉ khai thác thông tin kết nối giữa các nút và không cần các điểm neo.
Do vậy, định vị dựa trên kết nối hiệu quả về mặt kinh tế và không bị ảnh hƣởng bởi nhiễu [36]. Việc sử dụng các điểm neo giúp cung cấp tọa độ tuyệt đối, tức tọa độ đúng với mọi đối tƣợng và đƣợc đặt trong một khung tham chiếu nhƣ GPS. Tuy nhiên, với định vị dựa trên thông tin vị trí, một hệ tọa độ tƣơng đối – trong đó các nút có tọa độ tƣơng đối đối chiếu với các nút khác - là đủ. Từ những phân tích ở trên, luận án này chỉ tập trung vào định vị dựa trên kết nối không sử dụng điểm neo.
Định vị dựa trên kết nối không sử dụng điểm neo đã đƣợc quan tâm giải quyết từ nhiều năm nay. Shang và các cộng sự sử dụng co giãn đa chiều (MDS) [86]. Dựa trên thông tin kết nối giữa các nút, một thuật toán đƣờng đi ngắn nhất giữa mọi cặp đỉnh đƣợc sử dụng để tính ma trận khoảng cách của đồ thị mạng. Ma trận này đƣợc dùng làm đầu vào cho MDS, MDS sẽ tính vị trí các nút trong không gian đa chiều rồi chiếu vào không gian hai chiều.
Một cách trực quan, MDS cố gắng kéo dãn mạng theo mọi hƣớng. Nếu khoảng cách giữa các nút đƣợc biết chính xác, MDS sẽ cho kết quả định vị chính xác.
