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

Nội dung text: 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

1. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 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* thông tin vị trí. Sau đó, thông tin về vị trí của Các phương pháp định tuyến dựa trên topo nút đích được gắn vào mỗi gói tin cần chuyển yêu cầu các nút này phải lưu trữ nhiều thông đi và được sử dụng làm thông tin dẫn đường. tin về các đường định tuyến. Yêu cầu này Trong định tuyến dựa trên thông tin vị trí, vượt ngoài khả năng đáp ứng của các nút cảm chuyển tiếp tham lam thường được sử dụng vì biến. Ngoài ra, định tuyến dựa trên topo sử tính đơn giản và hiệu qủa của nó. Tuy nhiên, dụng nhiều gói tin điều khiển để tìm và duy dạng chuyển tiếp này lại gặp thất bại khi xuất trì các đường định tuyến. Ngoài tác động làm hiện vùng trống. Khi đó, kỹ thuật khôi phục giảm băng thông sẵn có cho dữ liệu, nhiều gói sẽ được sử dụng để đưa gói tin thoát khỏi tin điều khiển tiêu hao nhiều điện năng của vùng trống sử dụng đồ thị phẳng. Hai đồ thị các nút và hệ quả là làm giảm tuổi thọ của các phẳng được sử dụng ở đây là đồ thị RNG và nút. Với đặc điểm như phân tích ở trên, định GG, qua mô phỏng sẽ đánh giá được định tuyến dựa trên topo hầu như không áp dụng tuyến trên đồ thị phẳng nào là tốt hơn. cho mạng cảm biến. Phần II của bài báo trình bày tổng quan về Trong những năm gần đây, một cách tiếp cận định tuyến dựa trên thông tin vị trí. Phần III hoàn toàn khác cho vấn đề định tuyến cho trình bày về các kỹ thuật chuyển tiếp dựa trên mạng cảm biến không dây là sử dụng thông thông tin vị trí. Định tuyến khôi phục trên đồ tin về vị trí của các nút làm thông tin dẫn thị phẳng được trình bày trong phần IV. Phần đường. Tiếp cận mới này có tên là định tuyến V là kết quả mộ phỏng và đánh giá. Phần VI dựa trên thông tin vị trí. Định tuyến này giả là kết luận. thiết mỗi nút biết về vị trí của nó bằng việc sử ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN dụng hệ thống định vị như GPS. Ngoài ra, VỊ TRÍ định tuyến cần sử dụng một dịch vụ khác, Định tuyến dựa trên thông tin vị trí sử dụng được gọi là dịch vụ thông tin vị trí, để xác kết hợp chuyển tiếp dựa trên thông tin vị trí định vị trí của nút đích. Trước khi thực hiện và kỹ thuật khôi phục để định tuyến gói tin. giao thức định tuyến, nút nguồn xác định vị Chuyển tiếp dựa trên thông tin vị trí là kỹ trí của nút đích thông qua việc gọi dịch vụ 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ể * Tel: 0977 680685, Email: vvdien@ictu.edu.vn đo bằng khoảng cách từ nút đó đến nút đích. 13 Nitro PDF Software 100 Portable Document Lane Wonderland
2. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 Nút không có láng giềng gần đích hơn được 2.1.1.2: Nếu không chọn được láng gọi là cực tiểu địa phương (local minima). Để giềng để mỗi nút nhận được gói tin biết nên sử dụng chuyển gói tin theo GF, thì: chuyển tiếp dựa trên thông tin vị trí hay kỹ Đặt gói tin về chế độ khôi phục và 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 áp dụng kỹ thuật khôi phục để chuyển và được gọi là chế độ (mode) định tuyến của gói tin. gói tin. Nút nguồn thiết lập chế độ tham lam, Nếu áp dụng kỹ thuật khôi phục không hay chế độ sử dụng chuyển tiếp dựa trên thành thông tin vị trí, cho gói tin. Khi nhận được gói công thì loại bỏ gói tin. tin ở chế độ tham lam, nút không có láng 2.2: Ngược lại, gói tin đang ở chế độ khôi giềng gần đích hơn nó sẽ thay đổi gói tin sang phục, chế độ khôi phục, hay chế độ sử dụng kỹ 2.2.1: Nếu có thể đưa gói tin về chế độ tham thuật khôi phục, đồng thời ghi thông tin về vị lam, 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 thì chuyển gói tin về chế độ tham cùng. Khi nhận được gói tin ở chế độ khôi lam rồi phục, nút gần đích hơn cực tiểu địa phương quay lại bước 2.1.1. gặp cuối cùng khôi phục gói tin về chế độ 2.2.2: Ngược lại, không thể đưa gói tin về tham lam. Ở những tình huống còn lại, nút chế độ tham lam, áp dụng kỹ thuật khôi phục nhận được gói tin không thay đổi chế độ định để chuyển gói tin. Nếu áp dụng kỹ thuật khôi tuyến của gói tin và chỉ chuyển tiếp gói tin phục không thành công thì loại bỏ 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ế CHUYỂN TIẾP DỰA TRÊN THÔNG TIN độ định tuyến hiện tại của gói tin. Hành vi của VỊ TRÍ các nút trong định tuyến dựa trên thông tin vị trí được mô tả trong Bảng 1. Chuyển tiếp theo khoảng cách/tham lam Các kỹ thuật chuyển tiếp dựa trên thông tin vị Kỹ thuật chuyển tiếp dựa trên thông tin vị trí trí sẽ được trình bày trong phần tiếp theo. được sử dụng rộng rãi nhất, vì tính đơn giản BẢNG 1. HÀNH VI CỦA MỖI NÚT CẢM của nó, kỹ thuật này là chuyển tiếp tham lam BIẾN TRONG ĐỊNH TUYẾN DỰA TRÊN (greedy forwarding) hay chuyển tiếp theo THÔNG TIN VỊ TRÍ 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 PROCEDURE Xử_lý_gói_tin hiện tại chọn láng giềng gần đích nhất và gần 1: Nếu x là nút đích của gói tin, đích hơn nó làm nút kế tiếp. Rất nhiều giao 1.1: Chuyển gói tin lên tầng trên (giao vận) thức được đề xuất sử dụng chuyển tiếp 2: Ngược lại, tôi không phải là nút đích của tham lam [2, 3, 4]. Chuyển tiếp tham lam gói tin, có ưu điểm là đơn giản, hiệu quả và không 2.1: Nếu gói tin đang ở chế độ tham lam, 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 2.1.1: Sử dụng chuyển tiếp dựa trên thông nút hết năng lượng, thiên tai, lũ lụt, Nếu tin vị trí (GF) để chuyển gói tin chuyển tiếp tham lam được sử dụng thành 2.1.1.1: Nếu chọn được láng giềng để công bởi tất cả các nút trên đường định chuyển gói tin theo GF, chuyển gói tin cho tuyến từ nguồn đến đích, đường định tuyến sẽ láng giềng được chọn gần với đường tối ưu. 14 Nitro PDF Software 100 Portable Document Lane Wonderland
3. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 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 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 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 Hình 2. Chuyển tiếp tham lam bị lỗi, khi không có láng giềng nào gần đích hơn nút hiện tại. láng giềng nào của x gần D hơn nó Trong trường hợp như vậy, ta sẽ sử dụng định Chuyển tiếp theo góc tuyến khôi phục để đưa gói tin thoát khỏi Chuyển tiếp theo góc (compass forwarding) vùng trống dựa trên đồ thị phẳng sử dụng quy [5, 6, 7] cũng yêu cầu thông tin vị trí của tắc bàn tay phải. 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 Hình 4: Quy tắc bàn tay phải, x nhận gói tin từ y, theo góc chỉ thất bại khi nút hiện tại không và chuyển tiếp nó đến nút láng giềng đầu tiên theo có láng giềng nào. Khi nút hiện tại không có ngược chiều kim đồng hồ, z láng giềng gần đích hơn, gói tin được tạm Nếu gói tin đến được một nút mà nó gần đích thời đẩy xa đích. Sau đó, khi gói tin được 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. chuyển tiếp gần đích hơn, vòng lặp định tuyến Ngược lại, gói tin vẫn sẽ được chuyển tiếp có thể được tạo ra. theo quy tắc bàn tay phải trên đồ thị phẳng. Chuyển tiếp theo bước tiến Các đồ thị phẳng Chuyển tiếp theo bước tiến (progress Một đồ thị mà không có hai cạnh giao nhau forwarding) [8] sử dụng độ đo là độ dài hình được gọi là đồ thị phẳng . Một tập các nút với 15 Nitro PDF Software 100 Portable Document Lane Wonderland
4. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 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, d(n, m) r Đồ 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 Hình 6: Cạnh uv thuộc GG khi đường tròn đường đỉnh u và v nếu khoảng cách giữa chúng nhỏ kính uv phải không chứa w hơn hoặc bằng khoảng cách giữa một điểm w Quá trình xây dựng đồ thị GG từ đồ thị chưa bất kỳ (khác u, v) đến u hoặc đến v: phải là GG thực hiện bằng cách loại bỏ các w u,v : d(u,v) maxd(u,w),d(v,w) 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) max[d(u,w), d(v,w)] định bằng tỉ số giữa số gói tin nhận được chia then cho số gói tin gửi đi. loại bỏ cạnh (u,v) Kết quả mô phỏng được chỉ ra như trong hình break 7 sau: 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: 2 2 2 w u,v:d (u,v) d u,w d v,w Hình 7: Tỉ lệ phân phối gói tin thành công 16 Nitro PDF Software 100 Portable Document Lane Wonderland
5. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 18 Khi định khôi phục sử dụng đồ thị RNG cho TÀI LIỆU THAM KHẢO tỉ lệ phân phối gói tin thành công cao hơn so 1. G. G. Finn, “Routing and addressing problems in large metropolitan-scale với đồ thị GG. internetwork,” Tech. Rep. ISI/RR-87- Chi phí định tuyến 180,Information Sciences Institute, Mar. 1987. Hình 8 chỉ ra chi phí của giao thức định 2. P. Bose, P. Morin, I. Stojmenovic, and J. tuyến, được đo bằng số gói tin được gửi đi Urrutia, “Routing with guaranteed delivery in trên toàn mạng. 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. Hình 8: Chi phí giao thức định tuyến 113-122, 1999. 6. P. Bose, A. Brodnik, S. Carlsson, E. D. Khi định tuyến khôi phục sử dụng đồ thị Demaine, R. Fleischer, A. Lopez-Ortiz, P. RNG sẽ có chi phí giảm đi so với việc sử Morin, J. I. Munro, “Online routing in convex subdivisions,” International Symposium on dụng đồ thị GG. Algorithms and Computation, pp. 47-59, 2000. KẾT LUẬN 7. E. Kranakis, H Singh, and J. Urrutia, Báo cáo đã trình bày về định tuyến khôi “Compass routing on geometric networks,” phục dựa trên đồ thị phẳng trong định tuyến Proc. of the 11th Canadian Conference on dựa trên thông tin vị trí. Qua mô phỏng, đánh Computational Geometry, pp. 51-54, 1989. 8. I. Stojmenovic, X. Lin, “Loop-free hybrid giá ta thấy được được rằng định tuyến khôi single-path/flooding routing algorithms with phục trên đồ thị RNG giảm thiểu được chi guaranteed delivery for wireless networks,” IEEE phí so với GG mà lại cho tỉ lệ phân phối gói Trans. on Parallel and Distributed Systems, vol. tin thành công tốt hơn GG, làm cơ sở để lựa 12, pp. 1023-1032, Oct. 2001. 9. B. Karp, “Challenges in geographic routing: chọn đồ thị phẳng khi định tuyến khôi phục Sparse networks, obstacles, and traffic đưa gói tin thoát khỏi vùng trống và cùng với provisioning,” DIMACS Workshop on Pervasive chuyển tiếp tham lam đưa gói tin đến đích Networking, Piscataway, NJ, May 2001. thành công. 17 Nitro PDF Software 100 Portable Document Lane Wonderland
6. Vũ Văn Diện và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 13 - 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 18 Nitro PDF Software 100 Portable Document Lane Wonderland