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

Chia sẻ: Xuan Truong | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

394
lượt xem 100
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong những năm gần đây, rất nhiều mạng cảm biến vô tuyến đã và đang được phát triển và triển khai cho nhiều các ứng dụng khác nhau như: theo dõi sự thay đổi của môi trường, khí hậu, giám sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học, chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng như quản lý thuốc trong các bệnh viên, phát hiện và theo dấu các phương tiện xe...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các kỹ thuật phân nhóm trong các mạng cảm biến vô tuyến

Các kỹ thuật phân nhóm trong các mạng cảm biến vô tuyến TS. Lê Nhật Thăng, TS. Nguyễn Quý Sỹ 1. Giới thiệu chung Trong những năm gần đây, rất nhiều mạng cảm biến vô tuyến đã và đang được phát triển và triển khai cho nhiều các ứng dụng khác nhau như: theo dõi sự thay đổi của môi trường, khí hậu, giám sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học, chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng như quản lý thuốc trong các bệnh viên, phát hiện và theo dấu các phương tiện xe cộ… Một mạng cảm biến vô tuyến diện rộng bao gồm nhiều nút cảm biến nhỏ có giá thành thấp, và tiêu thụ năng lượng ít. Thông qua các kết nối vô tuyến, số liệu thu thập được từ các nút cảm biến sẽ được gửi đến một trạm gốc gần nhất, rồi sau đó, các số liệu này lại được chuyển tới các trung tâm xử lý dữ liệu cho các bước phân tích tiếp theo. Một trong những yếu điểm hạn chế liên quan đến thời gian tồn tại của các mạng cảm biến không dây chính là những nguồn năng lượng giới hạn phục vụ cho hoạt động của các nút cảm biến được triển khai trong mạng. Để đạt được hiệu quả sử dụng năng lượng cao và duy trì thời gian hoạt động lâu dài của mạng, các nút cảm biến thường được tổ chức phân bậc bằng cách gộp chúng lại thành các nhóm riêng biệt mà ở đó số liệu được thu thập và xử lý nội bộ tại các nút chính (cluster head nodes) trước khi chúng được gửi về một trạm gốc nào đó. Cấu trúc của mạng cảm biến không dây có phân nhóm được minh họa ở hình vẽ dưới đây. Base station (( )Cluster-head ) ( ( )) ( ( )) ( ( )) Cluster-head Cluster ( ( )) ( ( )) Cluster-head ( ( )) ( ( )) (( )) Cluster Cluster (( )) Sensor Hình 1: Cấu trúc mạng cảm biến không dây phân nhóm Như vậy, việc phân nhóm hình thành nên một cấu trúc phân cấp 2 mức mà ở đó các nút chính hình thành nên một bậc cao còn các nút thành viên của nhóm thuộc về một bậc thấp hơn. Lưu ý rằng, các nút trong một nhóm không truyền số liệu mà chúng thu thập được về trực tiếp trạm gốc mà phải thông qua nút chính của nhóm. Nút chính có nhiệm vụ: • Điều phối hoạt động giữa các nút trong nhóm và thu thập số liệu của các nút (Vì các nút có thể tạo ra các số liệu trùng lặp và thừa. Số liệu giống nhau từ nhiều nút có thể được tập hợp lại, sắp xếp, lọc loại bỏ số liệu thừa trùng lặp với mục đích giảm số lần truyền dẫn). 1
• Truyền trực tiếp các số liệu đã được tập hợp, tinh lọc về trạm gốc hoặc thông qua truyền dẫn nhiều chặng (multi-hop) nghĩa là qua các nút chính khác. Trên thực tế, thông tin trao đổi giữa các nút trong một nhóm cũng như giữa các nhóm khác nhau có thể được tổ chức như là một sự kết hợp giữa trao đổi thông tin một chặng (one-hop) và nhiều chặng. Ở trao đổi thông tin bằng một chặng, tất cả các nút cảm biến đều có thể trực tiếp truyền số liệu về đích, trong khi đó ở trao đổi thông tin qua nhiều chặng, các nút có phạm vi truyền dẫn hạn chế và do đó buộc phải định tuyến việc truyền số liệu của chúng qua một số chặng cho đến khi số liệu được truyền tới đích. Trong cả hai phương thức, có một vấn đề không thể tránh được đó là sự phân bố năng lượng tiêu thụ không đều giữa các nút. Điều này dẫn đến tình trạng một số nút bị mất năng lượng với tốc độ cao hơn, nhanh bị dừng hoạt động hơn một số nút khác và có thể làm giảm phạm vi cảm biến và chia cắt mạng. Đối với trao đổi thông tin một chặng, các nút xa trạm gốc thường là những nút ở trong tình trạng nguy cấp nhất do thiếu năng lượng hoạt động, trong khi ở trao đổi thông tin nhiều chặng, các nút gần trạm gốc nhất thường phải gánh chịu nhiều lưu lượng tải và thường bị dừng hoạt động trước tiên (đây là một vấn đề khá nguy hiểm và nghiêm trọng – “hot spot”). Các mạng cảm biến có phân nhóm có thể được phân chia thành các mạng không đồng nhất và các mạng đồng nhất tương ứng với kiểu và chức năng của các nút trong mạng. Với mạng đồng nhất, tất cả các nút đều có các khả năng xử lý và cấu trúc phần cứng như nhau. Vai trò của nút chính được hoán chuyển vòng tròn theo chu kỳ giữa các nút để cân bằng tải. Mặc dù hoán chuyển vòng tròn vai trò các nút chính để đảm bảo các nút cảm biến tiêu thụ năng lượng đồng đều hơn, nhưng vấn đề “hot spot” đã nêu ra ở trên không thể tránh khỏi hoàn toàn. Trong các mạng không đồng nhất, một số lượng nhất định các nút có những khả năng xử lý cao hơn và độ phức tạp phần cứng lớn hơn được triển khai trên toàn mạng cùng với một số các nút cảm biến thông thường khác. Đối với các nút chính, nhiều năng lượng hơn cần phải tiêu thụ để thực hiện một vài chức năng nào đó và chúng phục vụ như là các bộ thu thập số liệu và các trung tâm xử lý cho những số liệu thu thập bởi các nút cảm biến. Vì các mạng không đồng nhất cấp phát các nút chính ở dạng tĩnh, thời gian hoạt động của mạng được xác định phụ thuộc vào thời gian chức năng của các nút chính mà có liên quan trực tiếp tới hoạt động của nút chính và tiêu thụ năng lượng. Các nút chính có thể hình thành nên một mạng đường trục và sử dụng định tuyến nhiều chặng để định hướng số liệu tới trạm gốc. Hiện tượng “hot - spot” xảy ra trong mạng khi mà các nút chính sử dụng năng lượng cung cấp ở tốc độ cao hơn và ngừng hoạt động nhanh hơn các nút chính khác. Việc quản lý lưu lượng tải trở nên cần thiết để ngăn ngừa vấn đề suy giảm nguồn năng lượng cung cấp trước cho riêng từng nút chính của mạng. Các vị trí của các nút chính trên mạng có ảnh hưởng đến tiêu thụ năng lượng tổng cộng của tất cả các nút. Các nút chính có thể được phân tán trong trường cảm biến một cách ngẫu nhiên hoặc chúng có thể được triển khai theo một cách thức xác định trước. Trong trường hợp sau, ví dụ, các nút mạng có khả năng di chuyển và do vậy có thể thay đổi các vị trí của chúng cho tới khi chúng tới được một vài vị trí được xác định trước. Mặc dầu một mạng cảm biến không đồng nhất và được triển khai ngẫu nhiên là rất phổ biến và dễ dàng thực hiện, nhưng có nhiều khó khăn hơn để điều khiển kích cỡ thực sự của các nhóm và cân bằng có hiệu quả lưu lượng giữa các nút chính của nhóm. Do đó, vấn đề hot spot có thể dễ dàng nảy sinh do có sự tiêu thụ quá năng lượng ở một nút chính nào đó. Tuy còn có nhiều thảo luận liên quan đến vấn đề tiêu thụ và bảo toàn năng lượng, mạng cảm biến không dây phân nhóm có hai ưu điểm chính so với mạng không có sự phân nhóm: 2
• Mạng cảm biến không dây phân nhóm có khả năng làm giảm khối lượng thông tin trao đổi giữa các nút bằng việc khoanh vùng truyền dẫn số liệu trong phạm vi các nhóm và quan trọng hơn bằng việc giảm đáng kể số lượng truyền dẫn về trạm gốc. • Mạng cảm biến không dây phân nhóm có khả năng gia tăng thời gian không làm việc của các nút cảm biến qua việc cho phép các nút chính được điều phối và tối ưu các hoạt động của các nút thành viên 2. Phân loại các kỹ thuật phân nhóm trong các mạng cảm biến không dây Như đã phân tích ở trên, chúng ta thấy các nút chính thường phải truyền số liệu qua những khoảng cách xa và xử lý nhiều công việc khác nhau trong nhóm, nên chúng thường mất nhiều năng lượng hơn các nút thành viên khác. Do vậy mạng phải tái phân nhóm định kỳ để lựa chọn các nút có dư thừa năng lượng hơn làm nút chính của các nhóm và phân bố lưu lượng tải đều hơn cho toàn bộ các nút. Ngoài việc đạt được hiệu quả về sử dụng năng lượng, phân nhóm còn làm giảm sự tranh chấp kênh, xung đột gói và làm cho thông lượng của mạng tốt hơn ngay cả khi có lưu lượng tải cao. Phân nhóm được xem như là một giải pháp làm cải thiện “thời gian hoạt động của mạng” – một tham số cơ bản cho việc đánh giá hiệu năng của một mạng cảm biến. Mặc dầu vẫn chưa có định nghĩa thống nhất về “thời gian hoạt động của mạng” vì khái niệm này phụ thuộc mục tiêu của ứng dụng, các định nghĩa chung bao gồm thời gian cho đến khi nút đầu tiên/cuối cùng xả hết năng lượng của nó và thời gian cho đến khi nút không được kết nối với trạm gốc nữa. Lưu ý rằng, thậm trí mục tiêu của một số giao thức không phải để làm tối đa “thời gian hoạt động của mạng”. Các cải thiện về “thời gian hoạt động của mạng” có thể vẫn đạt được nếu việc thu thập số liệu được khai thác và mạng được tái phân lớp theo định kỳ. Phân nhóm được nghiên cứu rộng rãi trong xử lý số liệu và mạng cố định. Tuy nhiên, kỹ thuật phân nhóm được phát triển trong các lĩnh vực nêu trên đều không thể áp dụng trực tiếp cho mạng cảm biến không dây do sự triển khai duy nhất và các đặc tính hoạt động của những mạng này. Đặc biệt, các mạng cảm biến không dây được triển khai theo cách thức tùy biến (ad hoc) và có một số lượng lớn các nút. Các nút thường không nhận thức được về các vị trí của chúng. Do vậy, các giao thức phân bố mà dựa trên thông tin ở lân cận xung quanh thường được lựa chọn cho các mạng cảm biến không dây (tuy nhiên, phần lớn các nghiên cứu trong lĩnh vực này vẫn giả sử rằng cấu hình của mạng là đã được biết bởi một bộ điều khiển trung tâm). Hơn nữa, các nút trong các mạng cảm biến không dây hoạt động dựa trên nguồn năng lượng dự trữ có giới hạn (battery). Vì vậy, kỹ thuật phân nhóm triển khai trên thực tế phải có chi phí trao đổi thông tin thấp. Cuối cùng các điều kiện một trường khắc nghiệt cũng dẫn đến sự ngừng hoạt động không mong muốn của các nút mạng cảm biến. Cho nên, phân nhóm lại theo định kỳ là rất cần thiết để gắn kết các vùng bị mất liên lạc và phân bố sự tiêu thụ năng lượng ra toàn bộ các nút. Phân nhóm lại theo định kỳ cũng rất cần thiết khi mà các tham số sử dụng cho phân nhóm (ví dụ như: năng lượng còn lại, mức độ của nút…) là linh hoạt. Các kỹ thuật phân nhóm được đề xuất cho xử lý số liệu thường xem xét các tham số tĩnh như là khoảng cách giữa các nút và giả sử rằng các nút là rất xác thực. Phân nhóm trong mạng cảm biến không dây liên quan đến việc tập hợp các các nút lại thành các nhóm và lựa chọn ra một nút chính sao cho: • Các thành viên của một nhóm có thể trao đổi thông tin trực tiếp với nút chính của chúng. 3
• Một nút chính có thể chuyển dữ liệu thu thập được tới trạm gốc trung tâm thông qua các nút chính khác. Do vậy, việc tập hợp các nút chính trong mạng hình thành nên một tổ hợp các liên kết chi phối (connected dominating set) có ảnh hưởng lớn đến toàn mạng. Nghiên cứu về phân nhóm trong các mạng cảm biến không dây tập trung vào việc phát triển các thuật toán tập trung cũng như phân tán để tính toán xác định nên tổ hợp các liên kết chi phối. Ở đây, chúng tôi tập trung vào các hướng tiếp cận phân tán vì chúng là thực tế hơn cho những hiện trạng được triển khai trên phạm vi rộng. Vì để có được tổ hợp các liên kết chi phối là một vấn đề NP hoàn thiện, các thuật toán đề xuất thường mang tính chất heuristic. Chúng ta phân loại các kỹ thuật phân nhóm dựa trên hai tiêu chí: • Các tham số được sử dụng cho việc lựa chọn các nút chính. • Bản chất thực thi của một thuật toán phân nhóm (theo xác suất hay lặp). 2.1. Lựa chọn các nút chính Một loại trong số các kỹ thuật phân nhóm sử dụng nhận dạng của nút để lựa chọn các nút chính. Sự thành công của hướng tiếp cận này phụ thuộc vào hai giả thiết: • Tất cả các nút đều có một nhận dạng duy nhất • Những nhận dạng này được phân bố đều trong toàn mạng Do các nút chính duy trì và quyết định cấu hình của các mạng cảm biến nên việc lựa chọn tối ưu các nút chính là một vấn đề hết sức quan trọng. Trong mô hình của [1, 2], các tác giả thiên về lựa chọn các nút có chỉ số nhận dạng thấp thành các nút chính. Phương thức tiếp cận này có thể không phù hợp cho những mạng cảm biến có năng lượng giới hạn bởi vì nó tập trung chuyên vào một số lượng nhỏ các nút có chỉ số nhận dạng thấp mà không xem xét đến thời gian hoạt động mà chúng có thể tồn tại. Ngoài ra, nó không tạo ra được sự cân bằng về lưu lượng tải cho toàn bộ các nút trong mạng. Một phương pháp khác quan tâm đến các nút có bậc (degree) lớn hơn (ví dụ: Kuhn et. al. [3], Amis et. al. [4] và Gerla et. al. [5]) để tạo ra các nhóm và xây dựng tổ hợp các nút chính chi phối. Ở đây, bậc của một nút được tính toán dựa trên khoảng cách (phạm vi truyền dẫn) giữa nút này với các nút khác. Nói cách khác, bậc của một nút là số các nút lân cận trong một truyền dẫn được xác định trước gọi là phạm vi của nhóm. Nút có số lượng tối đa các nút lân cận sẽ được chọn làm nút chính. Tuy nhiêu, một nút chính không thể điều khiển được một số lượng lớn các nút của nhóm do hạn chế về nguồn năng lượng. Điều này có thể dẫn đến sự suy hao nhanh chóng nguồn ắc qui của các nút có bậc lớn. Hơn nữa, thông lượng của hệ thống sẽ giảm khi số lượng các nút trong nhóm tăng lên. Từ khía cạnh áp dụng, các nhóm có số lượng nút đồng đều sẽ làm giảm tải cho các nút chính. Nhưng vấn đề này làm nảy sinh chi phí cho việc có nhiều nhóm trong mạng và do vậy yêu cầu nhiều định tuyến hơn. Các kỹ thuật thuộc loại thứ ba chú trọng đến các nút có trọng số lớn hơn và được chọn làm các nút chính. Trọng số của một nút được dùng để xác định sự quan trọng của nút. Ví dụ, nó có thể là năng lượng ắc qui còn lại của nút (như trong giao thức HEED [6]), bậc của nút (như trong giao thức ACE [7]), hoặc kết hợp các tham số (ví dụ như năng lượng còn lại, phân bậc, tính di động, khoảng cách trung bình đến các nút lân cận). Kỹ thuật này có nhược điểm là không có một tiêu 4
chuẩn cụ thể để cấp trọng số cho các nút và nó khá phù hợp với mạng tĩnh mà ở đó các nút không di chuyển nhiều hoặc di chuyển rất chậm Một số các giao thức như GAF [8] và SPAN [9], được đề xuất cho việc điều khiển cấu hình mạng bằng việc khai thác các dư thừa của nút. Các giao thức này lựa chọn các nút nhất định nào đó thành các nút tích cực hoạt động (active) – tham gia vào quá trình cảm biến và truyền dẫn số liệu, trong khi các nút khác được bố trí tạm thời ngừng hoạt động để tiết kiệm năng lượng. Theo [8], ví dụ, một nút thuộc về một vùng nào đó được xác định bởi vị trí của nó. Khái niệm vùng trong ngữ cảnh này là được định nghĩa như là một phạm vi A mà ở đó bất kỳ một nút u nào đều có thể trao đổi thông tin qua một chặng với bất kỳ nút v nào thuộc B mà B là vùng lân cận của A. Do vậy, chỉ cần có một nút đại diện duy nhất trong bất kỳ một vùng nào để tham gia vào cơ chế định tuyến tại bất cứ thời điểm nào để đảm bảo sự liên kết kết nối mạng. Ở [9], một nút quyết định liệu nó ở chế độ hoạt động hoặc nghỉ tạm thời phụ thuộc vào kết nối giữa nó với các nút hai chặng lân cận. Mặc dầu những giao thức này không thuộc các kỹ thuật phân nhóm, nhưng ảnh hưởng của chúng lên cấu hình mạng tương tự như các kỹ thuật phân nhóm. 2.2. Thực thi của một thuật toán phân nhóm Việc thực thi một thuật toán phân nhóm có thể được tiến hành tại một căn cứ trung tâm (ví dụ như tại một trạm gốc) hoặc theo cách thức phân tán tại các nút nội bộ. Hướng tiếp cận tập trung thường yêu cầu thông tin về cấu hình mạng. Phương thức phân nhóm kinh điển K-Means (được đề xuất trong các tài liệu xử lý số liệu) có thể được áp dụng nếu số các nhóm yêu cầu có thể được xác định trước và các vị trí của nút là hiện hữu. Trong trường hợp này, một tập hợp ngẫu nhiên ban đầu của các nhóm được lựa chọn và một nút được chuyển đi từ một nhóm này sang các nhóm khác nếu sự di dời này làm giảm chức năng chi phí mục tiêu ban đầu cho toàn hệ thống. Banerjee at. al. [10] đề xuất một kỹ thuật tập trung mà không yêu cầu biết trước các vị trí của nút. Kỹ thuật của họ dựa trên việc xây dựng một cây mở rộng (spanning tree) của các nhóm mà được bắt đầu từ một người quan sát và việc cưỡng bức một giới hạn tối đa và tối thiểu cho kích cỡ của nhóm. Giao thức phân bố này được đề xuất ở [10] cho việc xây dựng cây mở rộng. Tính hiệu quả của các phương thức tiếp cận tập trung bị hạn chế ở các mạng có phạm vi rộng lớn nơi mà việc thu thập tất cả các thông tin cần thiết được thực hiện ở căn cứ trung tâm cả về mặt thời gian và tiêu thụ năng lượng. Phương thức tiếp cận phân tán thường phù hợp hơn cho các mạng có phạm vi rộng. Ở những phương thức tiếp cận phân tán này, một nút quyết định gia nhập một nhóm nào đấy hoặc trở thành nút chính dựa trên thông tin nhận được chủ yếu từ các nút lận cận một chặng với nó. Một số các kỹ thuật phân nhóm phân tán đã được đề xuất. Những kỹ thuật này có thể có tính chất lặp hoặc xác suất. 2.2.1. Các kỹ thuật phân nhóm lặp Trong các kỹ thuật phân nhóm lặp, một nút thường đợi một sự kiện cụ thể xuất hiện hoặc các nút nhất định nào đó để quyết định vai trò của chúng (ví dụ như trở thành nút chính) trước khi đưa ra một quyết định. Ví dụ, ở trong thuật toán phân nhóm phân tán (DCA – Distributed Clustering Algorithm) [11], trước khi đưa ra một quyết định, một nút thường đợi tất cả các nút lân cận nó có trọng số cao hơn để quyết định trở thành nút chính hoặc gia nhập các nhóm đang hoạt động. Các nút có trọng số cao nhất trong số các nút lân cận cách nhau một chặng được lựa chọn làm nút chính. Nếu một nút nhận được nhiều thông báo của các nút chính, nó sẽ phân xử giữa những nút chính bằng cách sử dụng điều kiện ưu tiên (tức là, nút có trọng số cao hơn sẽ thắng). Nếu không có nút nào trong số các nút lân cận của một nút có trọng số cao hơn quyết định trở thành nút chính, thì chính nút đó quyết định trở thành nút chính. Vấn đề với phần lớn các phương pháp lặp là ở chỗ tốc độ hội tụ của chúng phụ thuộc vào đường kính của mạng (đường có số lượng chặng nhiều nhất). Trong một trường hai chiều có n nút đang được triển khai hoạt động, 5
( ) thuật toán DCA yêu cầu O n bước lặp để kết thúc thuật toán. Tốc độ hội tụ trong tình huống xấu nhất có thể là n-1 trong một thiết lập một chiều (1D). Hiệu năng của các kỹ thuật lặp là khá nhạy cảm với những tổn thất gói. Ví dụ, nếu một nút u phát hiện thấy một trong số các nút lân cận với nó - nút v có trọng số cao hơn, thì nút u sẽ đợi nút v quyết định trước khi nó đưa ra quyết định. Nếu nút v hỏng ngay sau pha phát hiện của các nút lân cận, nút u sẽ đợi nút v vô thời hạn để đưa ra quyết định của chính nó. Thuật toán DCA khá phù hợp với những mạng mà ở đó các nút là tĩnh hoặc di chuyển với tốc độ rất chậm. Thuật toán phân nhóm phân tán và thích ứng di động – DMAC (The Distributed and Mobility-Adaptive Clustering Algorithm) [12] thay đổi thuật toán DCA để cho phép các nút di chuyển trong hoặc trước giai đoạn thiết lập nhóm. Thuật toán DCA và DMAC tạo ra các nhóm 1 chặng, yêu cầu các tín hiệu đồng hồ đồng bộ và có độ phức tạp O(n). Điều này làm cho chúng chỉ phù hợp với các mạng có số lượng nút nhỏ. Để cải thiện các vấn đề nêu trên, một số giao thức thiết lập một giới hạn về số các lần lặp cho mỗi một nút. Ví dụ, ở ACE [7], khi một nút thực hiện xong một số lần lặp (5 lần chẳng hạn) dựa trên bậc của nút như là một tham số chính, nó đưa ra một quyết định dựa trên thông tin hiện có. Các lần lặp này là đủ để có được kích cỡ nhóm trung bình ổn định. Giao thức ở [4], cho phép một nhóm bao gồm các nút có D chặng cách xa nút chính và một nút thường thực hiện 2D lần lặp trước khi đưa ra một quyết định. Điều này dẫn đến một số lần lặp không đổi cho hội tụ. Thuật toán Max-Min D cluster đề xuất bởi các tác giả của [4] đạt được sự cân bằng tải tốt hơn giữa các nút chính, tạo ít nhóm hơn hơn so với một số thuật toán khác như LCA (Linked Cluster Algorithm) [1] và LCA2 [2]. Tuy nhiên, thuật toán này không đảm bảo năng lượng sử dụng trong trao đổi thông tin tới trung tâm thông tin được tối thiểu hóa. 2.2.2. Các kỹ thuật phân nhóm có tính xác suất Phương thức tiếp cận theo xác suất hay ngẫu nhiên cho việc phân nhóm các nút đảm bảo sự hội tụ nhanh chóng mà vẫn có được một số các đặc tính quan trọng như kích cỡ các nhóm cân bằng. Nó cho phép các nút được quyết định độc lập về về vai trò của chúng trong mạng phân nhóm và vẫn duy trì tổng phí trao đổi bản tin thấp. Chúng ta sau đây thảo luận về một vài ví dụ của hướng tiếp cận này. Giao thức LEACH: Heinzelman et. al. [13] đã giới thiệu một thuật toán phân nhóm phân bậc cho các mạng cảm biến gọi là Phân nhóm phân bậc tương thích, năng lượng thấp – LEACH (Low Energy Adaptive Clustering Hierarchy). LEACH lựa chọn ngẫu nhiên một số nút cảm biến để trở thành các nút chính và quay vòng vai trò này để phân bố đều tải năng lượng giữa các nút cảm biến trong mạng. Ở LEACH, các nút chính nén các dữ liệu đến từ các nút khác trong nhóm của chúng và gửi các gói dữ liệu thu thập này tới trạm gốc nhằm mục đích giảm số lượng thông tin truyền phát về trạm gốc. Việc thu thập số liệu được thực hiện tập trung và theo chu kỳ. Do vậy giao thức này thực sự thích ứng khi có nhu cầu trao đổi theo dõi thường xuyên của mạng cảm biến. Thực tế, người sử dụng có thể không cần tất cả số liệu ngay lập tức, cho nên việc truyền phát số liệu theo chu kỳ là không cần thiết và có thể làm suy giảm nguồn năng lượng giới hạn của các nút cảm biến. Sau một khoảng thời gian cho trước, việc quay vòng ngẫu nhiên thay đổi vai trò của nút chính được tiến hành sao cho có sự tiêu tán năng lượng đều giữa các nút cảm biến trong mạng. Dựa vào mô hình mô phỏng mạng của các tác giả, chỉ có 5 % số nút cần thiết hoạt động ở dạng nút chính. 6
Hoạt động của LEACH được phân tách thành hai pha, pha thiết lập và pha ổn định trạng thái. Ở trong pha thiết lập, các nhóm được tổ chức và các nút chính được lựa chọn. Còn ở giai đoạn ổn định trạng thái, việc truyền số liệu thực sự về các trạm gốc được tiến hành. Khoảng thời gian tồn tại của pha ổn định trạng thái thường dài hơn so với thời gian thiết lập ban đầu để giảm tối thiểu tổng chi phí. Trong pha thiết lập, một số lượng nhỏ các nút được xác định trước, p, tự quyết định chúng trở thành các nút chính như sau. Một nút cảm biến chọn lấy một số ngẫu nhiên, r, trong phạm vi 0 và 1. Nếu số ngẫu nhiên này nhỏ hơn giá trị ngưỡng, T(n), thì nút đó sẽ trở thành nút chính ở vòng hiện tại. Giá trị ngưỡng được tính toán dựa trên một biểu thức toán học có sự kết hợp phần trăm mong muốn trở thành nút chính, vòng hiện tại, và tập hợp các nút chưa được lựa chọn làm nút chính ở vòng trước đó – tập G. T(n) được xác định: p T ( n) = nếu n ∈ G 1 − p (r mod (1 / p)) Tất cả các nút chính được lựa chọn phát quảng bá một bản tin thông báo tới tất cả các nút còn lại trong mạng rằng chúng là các nút chính mới. Các nút khác, không phải là nút chính sau khi nhận được bản tin thông báo này sẽ quyết định thuộc về một nhóm nào đó mà chúng muốn. Quyết định này dựa trên cường độ tín hiệu của bản tin thông báo. Các nút không phải là nút chính sẽ thông báo cho các nút chính thích ứng rằng chúng sẽ là thành viên của nhóm. Sau khi thu nhận được tất cả các bản tin từ các nút muốn gia nhập nhóm và dựa trên số lượng các nút thành viên của nhóm, nút chính sẽ tạo ra một định thời TDMA, và cấp cho mỗi nút một khe thời gian khi nó truyền phát. Định thời (Schedule) được quảng bá tới tất cả các nút của nhóm. Trong giai đoạn ổn định trạng thái, các nút cảm biến bắt đầu cảm biến và truyền phát số liệu về các nút chính. Các nút chính, sau khi thu tất cả các số liệu, tập hợp chúng lại trước khi gửi đến trạm gốc. Sau một khoản thời gian nhất định nào đó được xác định trước, mạng sẽ quay trở lại trạng thái thiết lập và bắt đầu một vòng lựa chọn các nút chính mới. Ở đây các nhóm trao đổi thông tin với nhau bằng việc sử dụng các mã CDMA để giảm nhiễu từ các nút thuộc các nhóm khác. LEACH cung cấp một mô hình tốt mà các thuật toán nội bộ và tập hợp dữ liệu có thể được thực hiện trong các nút chính được lựa chọn một cách ngẫu nhiên. Điều này làm giảm quá tải thông tin và cung cấp một tập hợp tin cậy các số liệu cho người sử dụng cuối cùng. Các tác giả của LEACH cũng đã chỉ ra rằng LEACH góp phần giảm đáng kể năng lượng tiêu thụ và kéo dài hơn thời gian hoạt động của mạng cảm biến so với trường hợp mạng gồm các nhóm cố định. Một phiên bản tập trung của LEACH, LEACH-C được đề xuất ở [14]. Không giống như LEACH, nơi mà các nút tự định hình chúng vào trong các nhóm, LEACH-C sử dụng trạm gốc cho việc hình thành các nhóm. Trong pha thiết lập của LEACH-C, trạm gốc thu các thông tin liên quan đến vị trí và mức năng lượng của từng nút trong mạng. Sử dụng những thông tin này, trạm gốc tìm số các nút chính được xác định trước và cấu hình mạng thành các nhóm. Tập hợp các nhóm được chọn để giảm tối thiểu năng lượng yêu cầu cho các nút không phải là nút chính để truyền phát số liệu của chúng đến tương ứng các nút chính. Mặc dầu các hoạt động khác của LEACH-C giống như LEACH, các kết quả được giới thiệu ở [14] chỉ cho thấy một sự cải thiện đáng kể của LEACH-C so với LEACH. Các tác giả của [14] đưa ra hai lý do chính cho sự tiến bộ: 7
• Trạm gốc sử dụng hiểu biết chung của nó về mạng để tạo ra các nhóm tốt hơn có yêu cầu năng lượng ít hơn cho việc truyền phát số liệu • Số lượng các nút chính trong mỗi vòng của LEACH-C bằng một giá trị tối ưu được xác định trước, trong khi đó ở LEACH, số lượng các nút chính thay đổi từ vòng nọ sang vòng kia do sự thiếu phối hợp chung giữa các nút. Tuy nhiên, LEACH có một số nhược điểm: • LEACH chưa xác định cụ thể được số lượng tối ưu các nút chính của mạng khi mà các mạng khác nhau có cấu hình, mật độ và số lượng nút khác nhau. • Chưa có gợi ý về khi nào thì việc tái tạo lại các nút chính cần được thực hiện. • Các nút chính ở xa trạm gốc sẽ tiêu thụ nhiều năng lượng hơn và nhanh chóng dừng hoạt động hơn các nút khác. Giao thức phân nhóm phân tán, hiệu quả năng lượng và lai ghép – HEED [6] giả sử rằng, các nút cảm biến không có bất kỳ khả năng đặc biệt 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. E 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 CH prob = C prob residual , ở E max đâ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. 8
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 ⎡ 1 ⎤ lặp cố định Niter = O(1) với N iter ≤ ⎢log 2 ⎥ + 1 . Điều này tương phản với một số phương thức ⎢ p min ⎥ 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 Rt ≥ 6 Rc . 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 9
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 Mục tiêu Các giả thiết Thời gian Bản tin phân nhóm (lặp) Các nhận dạng Barker et. I Nhận dạng Tối thiểu tổ nút duy nhất và O(Diam) O(1) al. [1] hợp chi phối phân bố đều các nút Biết trước cấu GAF [8] I Vị trí Loại bỏ sự dư hình và phạm O(1) O(1) thừa vi của mạng SPAN [9] I Kết nối hai Loại bỏ sự dư Tất cả các nút O(1) Phụ thuộc giao chặng thừa có một bảng thức định định tuyến tuyến Mỗi nút có một DCA [11] I Trọng số Tổ hợp chi giá trị trọng số O(Diam) O(1) phối các nút có thực và duy trọng số cao nhất Max-Min Hình thành nên Lớp MAC cung D-Cluster I Bậc nhóm có D cấp cơ chế O(D) O(D) [4] chặng, D là tránh xung đột không đổi Phân bố lưu ACE [7] I Bậc Hội tụ nhanh, lượng tải không O(1) O(1) nhiều nhóm đều Thay đổi Hội tụ nhanh Mạng một các nút và kéo dài tối chặng và phân LEACH P chính luân đa thời gian bố lưu lượng O(1) O(1) [13] phiên hoạt động của tải đều mạng Hội tụ nhanh Năng và kéo dài tối Phân bố lưu HEED [6] P lượng đa thời gian lượng tải không O(1) O(1) còn lại hoạt động của đều mạng Kuhn et. al. Tối thiểu tổ Ba kênh trao [3] P Bậc hợp chi phối đổi thông tin polylog(n) polylog(n) độc lập 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 10
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. 11