Các kỹ thuật phân nhóm trong các mạng cảm biến vô tuyến

nào như được trang bị thiết bị GPS chẳng hạn và tất cả các nút được phân nhóm là quan trọng như nhau. Mục đích chính của HEED là kéo dài thời gian hoạt động của mạng. Thời gian hoạt động của mạng được định nghĩa như là khoảng thời gian cho đến khi nút đầu tiên (hoặc cuối cùng) trong mạng dùng hết năng lượng của nó. Để đạt được mục đích này, HEED sử dụng phương thức tiếp cận xác suất để lựa chọn các nút chính có năng lượng dư thừa cao (so sánh với các nút thông thường) với số lần lặp không đổi. Một nút được sắp xếp vào một nhóm và phải có khả năng trao đổi thông tin với nút chính của nhóm qua một chặng bằng việc sử dụng phạm vi truyền dẫn bên trong nhóm, Rc, Rc tương ứng với mức công suất Pc. Định tuyến giữa các nhóm sử dụng phạm vi truyền dẫn lớn hơn, Rt, (Rt > Rc) và tương ứng với mức công suất Pt. Lựa chọn nút chính dựa vào hai tham số: tham số thứ nhất (năng lượng dư của nút) được sử dụng để lựa chọn một tập hợp ban đầu các nút chính, và tham số thứ hai được sử dụng để phá vỡ những sự ràng buộc. Sự ràng buộc xuất hiện khi có hai nút trong phạm vi Rc thông báo cho nhau về sự sẵn sàng trở thành nút chính. Tham số thứ hai này có thể được thiết lập cho việc ước lượng “chi phí” trao đổi thông tin trong nhóm, “chi phí” này là hàm của mật độ nhóm và quan hệ lân cận. Một nút thường thiết lập ban đầu xác suất của nó để trở thành nút chính maxE E CCH residualprobprob = , ở đây Eresidual là năng lượng dư ước chừng của nút, Emax là năng lượng tối đa tham chiếu và Cprob là một hằng số nhỏ không đổi được sử dụng để giới hạn số các thông báo của nút chính ban đầu. CHprob không được phép thấp hơn một giá trị xác suất nhỏ pmin, để đảm bảo kết cuối thời gian không đổi. Trong mỗi một hoạt động lặp, một nút thường phân xử lựa chọn trong số các thông báo của nút chính mà nó thu được để lựa chọn nút chính có chi phí thấp nhất. Nếu nó không nhận được bất kỳ một thông báo nào, nó sẽ tự chọn nó trở thành nút chính với xác suất CHprob. Nếu thành công, nó gửi đi một thông báo nói về sự “sẵn sàng” trở thành nút chính. Tiếp đó nút sẽ gấp đôi giá trị xác suất CHprob, chờ trong một khoảng thời gian lặp ngắn tc và sau đó bắt đầu lần lặp tiếp theo. Nút thường dừng quá trình lặp sau khi CHprob đạt đến 1. Nếu một nút quyết định trở thành nút chính, nó thường tăng công suất phát lên Pt cho trao đổi thông tin giữa các nhóm. 9 Các tác giả của HEED cũng đã chỉ ra trong [6] là HEED kết thúc việc chọn nút chính với số lần lặp cố định Niter = O(1) với 1 1log min 2 +⎥⎥ ⎤⎢⎢ ⎡≤ p Niter . Điều này tương phản với một số phương thức khác khi mà các nút chính được lựa chọn mới ngay sau mỗi bước lặp và nó cũng làm giảm các chi phí thiết lập cao, không cần thiết gắn kết với quá trình lựa chọn các nút chính. Thêm vào đó, mạng các nhóm vẫn duy trì kết nối theo một mô hình mật độ nhất định khi ct RR 6≥ . Ngoài ra, xác suất mà hai nút chính nằm lẫn nhau trong cùng phạm vi của nhóm Rc là rất nhỏ. Tuy nhiên, như các tác giả nhận định, việc lựa chọn thăm dò các nút chính là ngẫu nhiên và dựa trên năng lượng dư của các nút. Do vậy mà HEED không thể đảm bảo lựa chọn được tối ưu các nút chính về mặt năng lượng, và cũng như đối với số nhóm trong mạng và số nút trong một nhóm. Kuhn et. al. [3] đã đề xuất một kỹ thuật xác suất để lựa chọn các nút chính mà ở đó xác suất lựa chọn phụ thuộc vào bậc của nút. Sự hội tụ của kỹ thuật đề xuất bởi các tác giả phụ thuộc vào số nút ở trong mạng và bậc của nút là nhanh hơn rất nhiều so với các kỹ thuật lặp. Thêm vào đó phương thức tiếp cận này lựa chọn một tổ hợp chi phối của các nút chính gần tối ưu. Trên thực tế, trong khi và ngay sau khi triển khai một mạng cảm biến, không có một mô hình được thiết lập trước nào mà dựa vào đó các nút có thể trao đổi thông tin hiệu quả với nhau. Hay nói cách khác, sự không biết đầy đủ về cấu trúc của mạng (các nút không biết gì về các nút lân cận cũng như số lượng) là một đặc tính của mạng cảm biến vô tuyến trong khi được triển khai. Sự chuyển tiếp quá độ theo hướng tự tổ chức từ mạng không có cấu trúc sang mạng có cấu trúc được gọi là giai đoạn “khởi tạo” (Initialization). Thuật toán phân nhóm đề xuất bởi các tác giả của [3] đã lần đầu tiên quan tâm đến pha “khởi tạo” mạng với giả thiết mạng có nhiều chặng, không có phát hiện xung đột, các nút được triển khai không đồng bộ và do đó không phải truy nhập tới hệ thống đồng hồ đồng bộ chung. Đối với mô hình mạng ở giai đoạn khởi tạo, tập hợp các nút chính chi phối được xác định trong khoảng thời gian polylog(ñ), với ñ là giới hạn trên cho trước về số nút có trong hệ thống. Tuy nhiên, kỹ thuật phân nhóm của [3] hiện tại chỉ phù hợp với mô hình mạng cảm biến tĩnh, câu hỏi làm thế nào duy trì các nhóm có hiệu quả khi mà các nút di động vẫn đang là vấn đề mở cần phải giải quyết. Bảng 1 so sánh các ví dụ đại diện của các kỹ thuật phân nhóm phân bố. (lưu ý rằng một số các kỹ thuật khác đã được đề xuất trong một số các tài liệu liên quan , nhưng không được thảo luận ở đây do giới hạn không gian) . Bảng 1 chỉ ra rằng, tất cả các giao thức phân nhóm phân tán có tổng phí trao đổi bản tin là không đổi cho một nút. Đây là một ưu điểm quan trọng của các kỹ thuật phân tán so với các kỹ thuật phân nhóm tập trung. Việc xử lý tính toán tổng chi phí của mỗi một mạng cảm biến là không đáng kể đối với phương thức tập trung khi so với phương thức phân tán mà ở đó các nút thường tham gia vào sự tính toán. Ví dụ ở các phương thức tiếp cận lặp, một nút phải kiểm tra các bản tin thu được để quyết định việc nó nên phản ứng lại như thế nào. Lượng các bản tin này tỷ lệ với ( )δO mà δ là bậc của nút. Do năng lượng tiêu thụ cho xử lý số liệu thường thấp hơn cho trao đổi thông tin, tổng chi phí xử lý các bản tin có thể bỏ qua. Như đã được minh họa trong Bảng 1, phần lớn các giao thức phân tán có tổng chi phí thấp. Tổng chi phí này phụ thuộc vào tần suất phân nhóm lại mà thường nhỏ trong các áp dụng thông 10 thường. Thông lượng (throughput) thường không bị ảnh hưởng tiêu cực bởi việc phân nhóm như đã được chỉ ra trong quá trình thực hiện nghiên cứu của HEED [6]. Thực chất, thông lượng được cải thiện khi lưu lượng tải cao bởi vì sự giảm tranh chấp kênh. Hiệu năng của mỗi một giao thức phân nhóm phụ thuộc vào cấu hình của mạng, mô hình hệ thống và tình huống áp dụng. Bảng 1: So sánh các kỹ thuật phân nhóm phân tán điển hình Độ phức tap (cho một nút) Giao thức I/P Tiêu chuẩn phân nhóm Mục tiêu Các giả thiết Thời gian (lặp) Bản tin Barker et. al. [1] I Nhận dạng Tối thiểu tổ hợp chi phối Các nhận dạng nút duy nhất và phân bố đều các nút O(Diam) O(1) GAF [8] I Vị trí Loại bỏ sự dư thừa Biết trước cấu hình và phạm vi của mạng O(1) O(1) SPAN [9] I Kết nối hai chặng Loại bỏ sự dư thừa Tất cả các nút có một bảng định tuyến O(1) Phụ thuộc giao thức định tuyến DCA [11] I Trọng số Tổ hợp chi phối các nút có trọng số cao Mỗi nút có một giá trị trọng số thực và duy nhất O(Diam) O(1) Max-Min D-Cluster [4] I Bậc Hình thành nên nhóm có D chặng, D là không đổi Lớp MAC cung cấp cơ chế tránh xung đột O(D) O(D) ACE [7] I Bậc Hội tụ nhanh, nhiều nhóm Phân bố lưu lượng tải không đều O(1) O(1) LEACH [13] P Thay đổi các nút chính luân phiên Hội tụ nhanh và kéo dài tối đa thời gian hoạt động của mạng Mạng một chặng và phân bố lưu lượng tải đều O(1) O(1) HEED [6] P Năng lượng còn lại Hội tụ nhanh và kéo dài tối đa thời gian hoạt động của mạng Phân bố lưu lượng tải không đều O(1) O(1) Kuhn et. al. [3] P Bậc Tối thiểu tổ hợp chi phối Ba kênh trao đổi thông tin độc lập polylog(n) polylog(n) Chú thích: I/P chỉ ra giao thức có tính lặp hay xác suất, Diam là đường kính của mạng và n là số nút trong mạng. 3. Kết luận 11 Các kỹ thuật phân nhóm trong mạng cảm biến vô tuyến là những phương thức quản lý cấu hình mạng hiệu quả, góp phần làm giảm chi phí trao đổi thông tin, duy trì mạng hoạt động trong thời gian dài. Trong thời gian tới, chúng tôi sẽ tập trung tìm hiểu về các cách thức tính toán kích cỡ tối ưu của một nhóm, xác định tần suất hoán chuyển tối ưu vai trò làm nút chính giữa các nút trong mạng cảm biến …nhằm tối đa thời gian hoạt động của mạng cảm biến vô tuyến. Tài liệu tham khảo [1] D. J. Baker and A. Ephremides, “The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm,” IEEE Trans. Commun., vol. 29, no. 11, 1981, pp. 1694–701. [2] A. Ephremides J.E. Wieselthier and D.J. Baker, A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling, Proceedings of IEEE, vol. 75(1), 1987, pp. 56-73. [3] F. Kuhn, T. Moscibroda, and R. Wattenhofer, Initializing Newly Deployed Ad Hoc and Sensor Networks, Proc. ACM MOBICOM, Sept. 2004, pp. 260–74. [4] A. D. Amis et al., Max-Min D-Cluster Formation in Wireless Ad Hoc Networks, Proc. IEEE INFOCOM, Mar. 2000, pp. 32–41. [5] M. Gerla and J.T. Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, vol. 1, no. 3, 1995, pp. 255-265. [6] 0. Younis and S. Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE Trans. Mobile Comp., vol. 3, no. 4, Oct.–Dec. 2004, pp. 366–79. [7] H. Chan and A. Perrig, ACE: An Emergent Algorithm for Highly Uniform Cluster Formation, Proc. 1st Euro. Wksp. Sensor Networks, Jan. 2004, pp. 154–71. [8] Y. Xu, J. Heidemann, and D. Estrin, Geography-Informed Energy Conservation for Ad Hoc Routing, Proc. ACM MOBICOM, Rome, Italy, July 2001, pp. 70–84. [9] B. Chen et al., SPAN: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks, ACM Wireless Networks, vol. 8, no. 5, Sept. 2002, pp. 481–94. [10] S. Banerjee and S. Khuller, A Clustering Scheme for Hierarchical Control in Multihop Wireless Networks, Proc. IEEE INFOCOM, Apr. 2001, pp. 1028–37. [11] S. Basagni, Distributed Clustering Algorithm for Ad Hoc Networks, Proc. Int’l. Symp. Parallel Architectures, Algorithms, and Networks, 1999, pp. 310–15. [12] S. Basagni, Distributed and Mobility-Adaptive Clustering for Multimedia Support in Multi- Hop Wireless Networks, IEEE Proceedings of Vehicular Technology Conference, vol. 2, 1999, pp. 889-893. [13] W. Heinzelman, A.P. Chandrakasan and H. Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, IEEE Proceedings of the Hawaii International Conference on System Sciences, January 4-7, 2000, Maui, Hawaii. [14] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEETrans. Wireless Commun., vol. 1, no. 4, Oct. 2002, pp. 660–70.