Nghiên cứu định tuyến đơn phát dựa trên thông tin vị trí cho mạng cảm biển không dây

Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 13 NGHIÊN CỨU ĐỊNH TUYẾN ĐƠN PHÁT DỰA TRÊN THÔNG TIN VỊ TRÍ CHO MẠNG CẢM BIỂN KHÔNG DÂY Vũ Văn Diện*, Nguyễn Thị Hiền Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên TÓM TẮT Định tuyến dựa trên thông tin vị trí đã thay thế định tuyến dựa trên topo trong mạng cảm biến không dây. Kỹ thuật chuyển tiếp tham lam đã được sử dụng rất hiệu quả để chuyển tiếp gói tin từ nguồn đến đích. Tuy nhiên, kiểu chuyển tiếp này có nhược điểm là dễ gặp thất bại khi gặp vùng trống. Khi đó, nó sẽ sử dụng định tuyến khôi phục trên đồ thị phẳng để đưa gói tin qua vùng trống. Trong bài báo này, nhóm tác giả sử dụng hai đồ thị phẳng là RNG (Relative Neighbor Graph) và GG (Gabriel Graph) trong định tuyến khôi phục. Qua mô phỏng, đánh giá định tuyến khôi phục trên đồ thị phẳng RNG và GG, nhóm tác giả đã thấy được định tuyến khôi phục trên đồ thị RNG cho kết quả tốt hơn xét về tỉ lệ phân phối gói tin thành công từ nguồn đến đích, chi phí giao thức định tuyến được sử dụng. Từ khóa: Mạng cảm biến không dây, định tuyến, chuyển tiếp, khôi phục, đồ thị phẳng GIỚI THIỆU* Các phương pháp định tuyến dựa trên topo yêu cầu các nút này phải lưu trữ nhiều thông tin về các đường định tuyến. Yêu cầu này vượt ngoài khả năng đáp ứng của các nút cảm biến. Ngoài ra, định tuyến dựa trên topo sử dụng nhiều gói tin điều khiển để tìm và duy trì các đường định tuyến. Ngoài tác động làm giảm băng thông sẵn có cho dữ liệu, nhiều gói tin điều khiển tiêu hao nhiều điện năng của các nút và hệ quả là làm giảm tuổi thọ của các nút. Với đặc điểm như phân tích ở trên, định tuyến dựa trên topo hầu như không áp dụng cho mạng cảm biến. Trong những năm gần đây, một cách tiếp cận hoàn toàn khác cho vấn đề định tuyến cho mạng cảm biến không dây là sử dụng thông tin về vị trí của các nút làm thông tin dẫn đường. Tiếp cận mới này có tên là định tuyến dựa trên thông tin vị trí. Định tuyến này giả thiết mỗi nút biết về vị trí của nó bằng việc sử dụng hệ thống định vị như GPS. Ngoài ra, định tuyến cần sử dụng một dịch vụ khác, được gọi là dịch vụ thông tin vị trí, để xác định vị trí của nút đích. Trước khi thực hiện giao thức định tuyến, nút nguồn xác định vị trí của nút đích thông qua việc gọi dịch vụ * Tel: 0977 680685, Email: vvdien@ictu.edu.vn thông tin vị trí. Sau đó, thông tin về vị trí của nút đích được gắn vào mỗi gói tin cần chuyển đi và được sử dụng làm thông tin dẫn đường. Trong định tuyến dựa trên thông tin vị trí, chuyển tiếp tham lam thường được sử dụng vì tính đơn giản và hiệu qủa của nó. Tuy nhiên, dạng chuyển tiếp này lại gặp thất bại khi xuất hiện vùng trống. Khi đó, kỹ thuật khôi phục sẽ được sử dụng để đưa gói tin thoát khỏi vùng trống sử dụng đồ thị phẳng. Hai đồ thị phẳng được sử dụng ở đây là đồ thị RNG và GG, qua mô phỏng sẽ đánh giá được định tuyến trên đồ thị phẳng nào là tốt hơn. Phần II của bài báo trình bày tổng quan về định tuyến dựa trên thông tin vị trí. Phần III trình bày về các kỹ thuật chuyển tiếp dựa trên thông tin vị trí. Định tuyến khôi phục trên đồ thị phẳng được trình bày trong phần IV. Phần V là kết quả mộ phỏng và đánh giá. Phần VI là kết luận. ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN VỊ TRÍ Định tuyến dựa trên thông tin vị trí sử dụng kết hợp chuyển tiếp dựa trên thông tin vị trí và kỹ thuật khôi phục để định tuyến gói tin. Chuyển tiếp dựa trên thông tin vị trí là kỹ thuật chuyển gói tin từ nút này đến nút khác gần đích hơn. Độ gần đích của một nút có thể đo bằng khoảng cách từ nút đó đến nút đích. Nitro PDF Software 100 Portable Document Lane Wonderland Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 14 Nút không có láng giềng gần đích hơn được gọi là cực tiểu địa phương (local minima). Để mỗi nút nhận được gói tin biết nên sử dụng chuyển tiếp dựa trên thông tin vị trí hay kỹ thuật khôi phục cho gói tin nhận được, thông tin chỉ dẫn được ghi trong tiêu đề của gói tin và được gọi là chế độ (mode) định tuyến của gói tin. Nút nguồn thiết lập chế độ tham lam, hay chế độ sử dụng chuyển tiếp dựa trên thông tin vị trí, cho gói tin. Khi nhận được gói tin ở chế độ tham lam, nút không có láng giềng gần đích hơn nó sẽ thay đổi gói tin sang chế độ khôi phục, hay chế độ sử dụng kỹ thuật khôi phục, đồng thời ghi thông tin về vị trí của nó vào tiêu đề gói tin ở trường nút không có láng giềng gần đích hơn gặp cuối cùng. Khi nhận được gói tin ở chế độ khôi phục, nút gần đích hơn cực tiểu địa phương gặp cuối cùng khôi phục gói tin về chế độ tham lam. Ở những tình huống còn lại, nút nhận được gói tin không thay đổi chế độ định tuyến của gói tin và chỉ chuyển tiếp gói tin bằng việc áp dụng chuyển tiếp dựa trên thông tin vị trí hay kỹ thuật khôi phục tùy theo chế độ định tuyến hiện tại của gói tin. Hành vi của các nút trong định tuyến dựa trên thông tin vị trí được mô tả trong Bảng 1. Các kỹ thuật chuyển tiếp dựa trên thông tin vị trí sẽ được trình bày trong phần tiếp theo. BẢNG 1. HÀNH VI CỦA MỖI NÚT CẢM BIẾN TRONG ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN VỊ TRÍ ------------------------------------------------------- PROCEDURE Xử_lý_gói_tin 1: Nếu x là nút đích của gói tin, 1.1: Chuyển gói tin lên tầng trên (giao vận) 2: Ngược lại, tôi không phải là nút đích của gói tin, 2.1: Nếu gói tin đang ở chế độ tham lam, 2.1.1: Sử dụng chuyển tiếp dựa trên thông tin vị trí (GF) để chuyển gói tin 2.1.1.1: Nếu chọn được láng giềng để chuyển gói tin theo GF, chuyển gói tin cho láng giềng được chọn 2.1.1.2: Nếu không chọn được láng giềng để chuyển gói tin theo GF, thì: Đặt gói tin về chế độ khôi phục và áp dụng kỹ thuật khôi phục để chuyển gói tin. Nếu áp dụng kỹ thuật khôi phục không thành công thì loại bỏ gói tin. 2.2: Ngược lại, gói tin đang ở chế độ khôi phục, 2.2.1: Nếu có thể đưa gói tin về chế độ tham lam, thì chuyển gói tin về chế độ tham lam rồi quay lại bước 2.1.1. 2.2.2: Ngược lại, không thể đưa gói tin về chế độ tham lam, áp dụng kỹ thuật khôi phục để chuyển gói tin. Nếu áp dụng kỹ thuật khôi phục không thành công thì loại bỏ gói tin. ------------------------------------------------------- CHUYỂN TIẾP DỰA TRÊN THÔNG TIN VỊ TRÍ Chuyển tiếp theo khoảng cách/tham lam Kỹ thuật chuyển tiếp dựa trên thông tin vị trí được sử dụng rộng rãi nhất, vì tính đơn giản của nó, kỹ thuật này là chuyển tiếp tham lam (greedy forwarding) hay chuyển tiếp theo khoảng cách [1]. Trong chuyển tiếp này, khoảng cách đến đích được sử dụng làm độ đo khi lựa chọn nút kế tiếp. Cụ thể, nút hiện tại chọn láng giềng gần đích nhất và gần đích hơn nó làm nút kế tiếp. Rất nhiều giao thức được đề xuất sử dụng chuyển tiếp tham lam [2, 3, 4]. Chuyển tiếp tham lam có ưu điểm là đơn giản, hiệu quả và không tạo vòng lặp định tuyến nhưng có yếu điểm là dễ thất bại khi gặp các vùng trống [9], do nút hết năng lượng, thiên tai, lũ lụt,... Nếu chuyển tiếp tham lam được sử dụng thành công bởi tất cả các nút trên đường định tuyến từ nguồn đến đích, đường định tuyến sẽ gần với đường tối ưu. Nitro PDF Software 100 Portable Document Lane Wonderland Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 15 Hình 1. Ví dụ về chuyển tiếp tham lam, y là nút láng giềng gần nút đích D nhất Hình 2. Chuyển tiếp tham lam bị lỗi, khi không có láng giềng nào của x gần D hơn nó Chuyển tiếp theo góc Chuyển tiếp theo góc (compass forwarding) [5, 6, 7] cũng yêu cầu thông tin vị trí của các láng giềng và nút đích như chuyển tiếp tham lam nhưng sử dụng góc được tạo bởi hai véctơ, một từ nút hiện tại đến đích và một từ nút hiện tại đến láng giềng, làm độ đo. Láng giềng có góc bé nhất sẽ được chọn làm nút kế tiếp. So với chuyển tiếp tham lam, chuyển tiếp theo góc ít thất bại do cực tiểu địa phương nhưng có thể tạo ra vòng lặp định tuyến. Sự khác biệt này có được do chuyển tiếp theo góc không ràng buộc nút kế tiếp phải gần đích hơn. Chuyển tiếp theo góc chỉ thất bại khi nút hiện tại không có láng giềng nào. Khi nút hiện tại không có láng giềng gần đích hơn, gói tin được tạm thời đẩy xa đích. Sau đó, khi gói tin được chuyển tiếp gần đích hơn, vòng lặp định tuyến có thể được tạo ra. Chuyển tiếp theo bước tiến Chuyển tiếp theo bước tiến (progress forwarding) [8] sử dụng độ đo là độ dài hình chiếu của đoạn thẳng nối nút hiện tại đến láng giềng lên đường thẳng đi qua nút hiện tại và nút đích. Láng giềng gần đích hơn và có độ đo lớn nhất được chọn làm nút kế tiếp. Hình 3. Ví dụ về chuyển tiếp theo góc, gói tin từ v được chuyển đến u ĐỊNH TUYẾN KHÔI PHỤC TRÊN ĐỒ THỊ PHẲNG Định tuyến khôi phục Chuyển tiếp tham lam thường hay được sử dụng để đưa gói tin từ nguồn đến đích. Tuy nhiên, khi xuất hiện vùng trống (rất hay xuất hiện trong mạng cảm biến) thì kiểu chuyển tiếp này hay gặp thất bại khi không có nút láng giềng nào gần đích hơn nút hiện tại. Trong trường hợp như vậy, ta sẽ sử dụng định tuyến khôi phục để đưa gói tin thoát khỏi vùng trống dựa trên đồ thị phẳng sử dụng quy tắc bàn tay phải. Hình 4: Quy tắc bàn tay phải, x nhận gói tin từ y, và chuyển tiếp nó đến nút láng giềng đầu tiên theo ngược chiều kim đồng hồ, z Nếu gói tin đến được một nút mà nó gần đích hơn nút cực tiểu địa phương thì sẽ khôi phục chế độ chuyển tiếp tham lam từ nút này. Ngược lại, gói tin vẫn sẽ được chuyển tiếp theo quy tắc bàn tay phải trên đồ thị phẳng. Các đồ thị phẳng Một đồ thị mà không có hai cạnh giao nhau được gọi là đồ thị phẳng . Một tập các nút với Nitro PDF Software 100 Portable Document Lane Wonderland Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 16 sóng vô tuyến, ở đó các phạm vi sóng vô tuyến là giống nhau (là r), có thể xem như là một đồ thị: mỗi nút là một đỉnh, và cạnh (n; m) tồn tại giữa các nút n và m nếu khoảng cách giữa n và m, rmnd ),( Đồ thị RNG (Relative Neighbor Graph) và GG (Gabriel Graph) [4] là hai đồ thị phẳng đã được biết đến từ lâu. Đồ thị RNG được định nghĩa như sau: Cho một tập các đỉnh, cạnh (u, v) tồn tại giữa đỉnh u và v nếu khoảng cách giữa chúng nhỏ hơn hoặc bằng khoảng cách giữa một điểm w bất kỳ (khác u, v) đến u hoặc đến v:  ),(),,(max),(:, wvdwudvudvuw  Hình 5. Cạnh uv là cạnh của RNG khi giao 2 đường tròn tâm u và v phải không chứa w Quá trình xây dựng đồ thị RNG từ đồ thị chưa phải là RNG thực hiện bằng cách loại bỏ các cạnh như sau: For tất cả đỉnh v thuộc tập láng giềng N do For tất cả đỉnh w thuộc N do if w = = v then continue else if d(u,v) > max[d(u,w), d(v,w)] then loại bỏ cạnh (u,v) break endif end for end for Đồ thị GG được định nghĩa như sau: Một cạnh (u, v) tồn tại giữa u và v nếu không có đỉnh w nào khác trong vòng tròn nhận uv làm đường kính. Ta có công thức sau:    wvdwudvudvuw ,,),(:, 222  Hình 6: Cạnh uv thuộc GG khi đường tròn đường kính uv phải không chứa w Quá trình xây dựng đồ thị GG từ đồ thị chưa phải là GG thực hiện bằng cách loại bỏ các cạnh như sau: m = trung điểm của uv for tất cả đỉnh v thuộc tập các láng giềng N do for tất cả w thuộc N do if w = = v then continue else if d(m,w) < d(u, m) then loại bỏ cạnh (u, v) end if end for end for KẾT QUẢ MÔ PHỎNG VÀ ĐÁNH GIÁ Môi trường mô phỏng Nhóm tác giả mô phỏng định tuyến khôi phục trên đồ thị phẳng RNG và GG sử dụng phần mềm mô phỏng ns-2 . Giao thức định tuyến sử dụng là GPSR [4]. Môi trường mô phỏng được thực hiện với 100 nút mạng trên vùng 1000 x 500. Tỉ lệ phân phối gói tin thành công Tỉ lệ phân phối gói tin thành công được xác định bằng tỉ số giữa số gói tin nhận được chia cho số gói tin gửi đi. Kết quả mô phỏng được chỉ ra như trong hình 7 sau: Hình 7: Tỉ lệ phân phối gói tin thành công Nitro PDF Software 100 Portable Document Lane Wonderland Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 17 Khi định khôi phục sử dụng đồ thị RNG cho tỉ lệ phân phối gói tin thành công cao hơn so với đồ thị GG. Chi phí định tuyến Hình 8 chỉ ra chi phí của giao thức định tuyến, được đo bằng số gói tin được gửi đi trên toàn mạng. Hình 8: Chi phí giao thức định tuyến Khi định tuyến khôi phục sử dụng đồ thị RNG sẽ có chi phí giảm đi so với việc sử dụng đồ thị GG. KẾT LUẬN Báo cáo đã trình bày về định tuyến khôi phục dựa trên đồ thị phẳng trong định tuyến dựa trên thông tin vị trí. Qua mô phỏng, đánh giá ta thấy được được rằng định tuyến khôi phục trên đồ thị RNG giảm thiểu được chi phí so với GG mà lại cho tỉ lệ phân phối gói tin thành công tốt hơn GG, làm cơ sở để lựa chọn đồ thị phẳng khi định tuyến khôi phục đưa gói tin thoát khỏi vùng trống và cùng với chuyển tiếp tham lam đưa gói tin đến đích thành công. TÀI LIỆU THAM KHẢO 1. G. G. Finn, “Routing and addressing problems in large metropolitan-scale internetwork,” Tech. Rep. ISI/RR-87- 180,Information Sciences Institute, Mar. 1987. 2. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” Wireless Networks, 7(6):609-616, 2001. 3. Q. Fang, J. Gao, and L. Guibas, “Locating and bypassing routing holes in sensor networks,” Mobile Networks and Applications, 11(2): 187- 200, April 2006. 4 B. Karp and H.T. Kung, “GPSR: Greedy perimeter stateless routing for wireless sensor networks,” Proc. of Mobicom, pp. 243-254, 2000. 5. P. Bose, P. Morin, “Online routing in triangulations,” Proc. of 10th International Symposium on Algorithms and Computation, pp. 113-122, 1999. 6. P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, J. I. Munro, “Online routing in convex subdivisions,” International Symposium on Algorithms and Computation, pp. 47-59, 2000. 7. E. Kranakis, H Singh, and J. Urrutia, “Compass routing on geometric networks,” Proc. of the 11th Canadian Conference on Computational Geometry, pp. 51-54, 1989. 8. I. Stojmenovic, X. Lin, “Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks,” IEEE Trans. on Parallel and Distributed Systems, vol. 12, pp. 1023-1032, Oct. 2001. 9. B. Karp, “Challenges in geographic routing: Sparse networks, obstacles, and traffic provisioning,” DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May 2001. Nitro PDF Software 100 Portable Document Lane Wonderland Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 18 SUMMARY RECOVERY ROUTING BASED ON PLANAR GRAPH IN GEOGRAPHIC ROUTING FOR WIRELESS SENSOR NETWORK Vu Van Dien * , Nguyen Thi Hien College of Information and Communication Technology - TNU Routing based on location information have alternatived the routing based on topology in wireless sensor networks. Greedy forwarding technique has been used very effectively to forward packets from source to destination. However, the drawback of this type of forwading is easy to fail to meet holes. As such, it will use recovery routing on planar graphs to put packets through the holes. In this paper, we use two planar graph, RNG (Relative Neighbor Graph) and GG (Gabriel Graph) in the recovery routing. Through simulation, evaluating about recovery routing on planar graphs RNG and GG, we saw the recovery routing on graph RNG for better results in terms of the percentage distribution of packets from source to destination successfully, cost of routing protocol used. Key: Wireless sensor network, routing, forwarding, recovery, planar graph Ngày nhận bài:31/10/2014; Ngày phản biện:28/11/2014; Ngày duyệt đăng: 31/5/2015 Phản biện khoa học: TS. Đào Huy Du – Trường Đại học Kỹ thuật Công nghiệp - ĐHTN * Tel: 0977 680685, Email: vvdien@ictu.edu.vn Nitro PDF Software 100 Portable Document Lane Wonderland