Đề tài Tìm hiểu về mạng cảm biến

rong WSN : Mặc dù các ứng dụng của mạng WSN là rất lớn, tuy nhiên những mạng này cĩ một số hạn chế như giới hạn về nguồn cơng suất, khả năng tính tốn và độ rộng băng thơng. Một trong những mục tiêu thiết kế chính của WSN là kéo dài thời gian sống của mạng và tránh suy giảm kết nối nhờ các kỹ thuật quản lý năng lượng. Việc thiết kế các giao thức chọn đường trong WSN bị ảnh hưởng bởi một số yếu tố. Vấn đề này phải được giải quyết triệt để thì mới đạt được hiệu quả truyền tin trong WSN. Dưới đây sẽ tĩm tắt một số khĩ khăn trong vấn đề chọn đường và thiết kế trong mạng WSN. Phân bố nút: Việc phân bố nút trong WSN phụ thuộc vào ứng dụng và cĩ thể được thực hiện bằng tay hoặc phân bố ngẫu nhiên. Khi phân bố bằng tay, số liệu được chọn đường thơng qua các đường xác định trước. Tuy nhiên khi phân bố các nút ngẫu nhiên sẽ tạo ra một cấu trúc chọn đường đặc biệt (ad-hoc). Liên lạc giữa các nút cảm biến thường cĩ cự ly ngắn do các hạn chế về năng lượng và băng thơng. Do đĩ việc chọn đường sẽ thực hiện qua nhiều bước nhảy. Tiêu thụ năng lượng khơng được làm mất độ chính xác: Các nút cảm biến cĩ thể sử dụng quá các giới hạn về cơng suất để thực hiện tính tốn và truyền tin trong mơi trường vơ tuyến. Thời gian sống của nút cảm biến phụ thuộc rất nhiều vào thời gian sử dụng của pin [1]. Trong WSN đa bước nhảy, mỗi nút đĩng hai vai trị là truyền số liệu và chọn đường. Một số nút cảm biến hoạt động sai chức năng do lỗi nguồn cơng suất cĩ thể gây ra sự thay đổi cấu hình mạng nghiêm trọng và phải chọn đường lại các gĩi hoặc tổ chức lại mạng. Phương pháp báo cáo số liệu: Việc báo cáo số liệu trong WSN phụ thuộc vào ứng dụng và cĩ thể được chia thành báo cáo theo thời gian, theo sự kiện, theo yêu cầu hoặc lai ghép những phương pháp này. Phương pháp báo cáo theo thời gian phù hợp với các ứng dụng yêu cầu giám sát số liệu định kỳ. Khi đĩ, các nút cảm biến sẽ bật bộ phận cảm biến và bộ phận phát theo định kỳ, cảm nhận mơi trường, phát số liệu yêu cầu theo chu kỳ thời gian xác định. Trong phương pháp báo cáo theo sự kiện và theo yêu cầu, các nút cảm biến sẽ phản ứng tức thì đối với những thay đổi giá trị của thuộc tính cảm biến do xuất hiện một sự kiện xác định nào đĩ hoặc để trả lời một yêu cầu được tạo ra bởi nút gốc hay các nút khác trong mạng. Do vậy, những phương pháp này phù hợp với các ứng dụng phụ thuộc thời gian. Cũng cĩ thể sử dụng kết hợp các phương pháp trên. Giao thức chọn đường chịu ảnh hưởng đáng kể từ phương pháp báo cáo số liệu về vấn đề sử dụng năng lượng và chọn đường. Tính khơng đồng nhất của nút/tuyến: Trong nhiều nghiên cứu, tất cả các nút cảm biến được giả thiết là đồng nhất (nghĩa là cĩ khả năng tính tốn, khả năng truyền tin và cĩ cơng suất như nhau). Tuy nhiên, tuỳ theo ứng dụng mà nút cảm cĩ thể cĩ vai trị hoặc khả năng khác nhau. Các nút cảm biến khơng đồng nhất tạo ra một số vấn đề kỹ thuật liên quan đến chọn đường. Ví dụ, một số ứng dụng cĩ thể cần kết hợp các bộ Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 10 -- cảm biến để giám sát nhiệt độ, áp suất, độ ẩm của mơi trường, phát hiện chuyển động nhờ âm thanh, chụp ảnh hoặc ghi hình các vật chuyển động. Ngồi ra, việc đọc hoặc báo cáo số liệu từ những bộ cảm biến này cĩ thể cĩ tốc độ khác nhau tuỳ theo QoS và cĩ thể thuộc nhiều mơ hình báo cáo số liệu khác nhau. Ví dụ, các giao thức phân cấp chỉ rõ nút chủ nhĩm khác so với các nút cảm biến bình thường khác. Những nút chủ nhĩm này cĩ thể được chọn từ các nút cảm biến phân bố hoặc các nút mạnh hơn các nút cảm biến khác về cơng suất, băng thơng và bộ nhớ. Do đĩ, nhiệm vụ truyền tin tới nút gốc được tập trung bởi một nhĩm các nút chủ nhĩm. Khả năng chống lỗi: Một số nút cảm biến cĩ thể bị lỗi hoặc bị ngắt do thiếu cơng suất, hỏng phần cứng hoặc bị nhiễu mơi trường. Sự cố của các nút cảm biến khơng được ảnh hưởng tới nhiệm vụ của tồn mạng cảm biến. Nếu cĩ nhiều nút bị lỗi, các giao thức chọn đường hoặc điều khiển truy nhập mơi trường (MAC) phải thành cập các tuyến mới tới nút gốc. Việc này cĩ thể cần thiết phải điều chỉnh cơng suất phát và tốc độ tín hiệu trên các tuyến hiện tại để giảm sự tiêu thụ năng lượng hoặc là các gĩi phải chọn đường lại qua các vùng mạng cĩ cơng suất khả dụng lớn hơn. Khả năng định cỡ: số lượng nút cảm biến cĩ thể là hàng trăm, hàng nghìn hoặc nhiều hơn. Bất kỳ phương pháp chọn đường nào cũng phải cĩ khả năng làm việc với một số lượng lớn các nút cảm biến như vậy. Tính động của mạng: Trong nhiều nghiên cứu, các nút cảm biến được giả thiết là cố định. Tuy nhiên trong một số ứng dụng, cả nút gốc và các nút cảm biến cĩ thể di chuyển [2]. Khi đĩ các bản tin chọn đường từ hoặc tới các nút di chuyển sẽ gặp phải các vấn đề như đường liên lạc, cấu hình mạng, năng lượng, độ rộng băng... Tuy nhiên, đối tượng thì cĩ thể di chuyển (ví dụ ứng dụng dị tìm/theo dõi mục tiêu). Các sự kiện cố định thì cho phép mạng làm việc ở chế độ phản ứng (tạo lưu lượng khi cần báo cáo) trong khi các sự kiện chuyển động thì trong hầu hết các ứng dụng đều yêu cầu phải báo cáo định kỳ cho nút gốc. Mơi trường truyền dẫn: Trong mạng cảm biến đa bước nhảy, các nút thơng tin được kết nối qua mơi trường vơ tuyến. Các đặc tính của kênh vơ tuyến như pha đinh, tỷ lệ lỗi cũng cĩ thể ảnh hưởng đến hoạt động của mạng cảm biến. Nĩi chung, độ rộng băng yêu cầu của số liệu cảm biến là thấp, khoảng từ 1-100 kb/s. Liên quan đến mơi trường truyền dẫn là việc thiết kế MAC. Một phương pháp thiết kế MAC cho các mạng cảm biến là sử dụng các giao thức đa truy nhập phân chia theo thời gian (TDMA) sẽ tiết kiệm năng lượng hơn so với các giao thức đa truy nhập khác như đa truy nhập theo sĩng mang (CSMA) (ví dụ IEEE 802.11). Cơng nghệ Bluetooth [3] cũng cĩ thể được sử dụng. Khả năng giám sát: Trong WSN, mỗi nút cảm biến giám sát một vùng xác định. Vùng giám sát mơi trường của nút cảm biến bị giới hạn bởi cự ly và độ chính xác, nĩ cĩ thể chỉ giám sát một phạm vi rất nhỏ. Do đĩ, vùng giám sát cũng là một tham số thiết kế quan trọng trong WSN. Kết hợp số liệu: Vì các nút cảm biến cĩ thể tạo ra số liệu dư thừa nên các gĩi tương tự nhau từ nhiều nút cĩ thể được kết hợp lại để giảm số lượng truyền dẫn. Việc kết hợp số liệu là từ nhiều nguồn khác nhau theo một hàm kết hợp xác định. Kỹ thuật Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 11 -- này được sử dụng để đạt hiệu quả về năng lượng và tối ưu hố việc truyền số liệu trong một số giao thức chọn đường. Chất lượng dịch vụ: Trong một số ứng dụng, số liệu cĩ thể được phân phối trong một khoảng thời gian xác định ngay khi nĩ cảm nhận được hiện tượng nếu khơng số liệu sẽ trở nên vơ dụng. Vì vậy, giới hạn trễ của việc phân phối số liệu là một chỉ tiêu khác trong các ứng dụng phụ thuộc thời gian. Tuy nhiên trong một số ứng dụng khác thì việc tiêu thụ cơng suất (ảnh hưởng trực tiếp đến thời gian sống của mạng) lại quan trọng hơn. Khi năng lượng gần hết, mạng cĩ thể yêu cầu giảm chất lượng các kết quả để giảm mức tiêu thụ năng lượng của nút và kéo dài thời gian sống của tồn mạng. II.Phân loại và so sánh các giao thức chọn đường trong WSN Nĩi chung, việc chọn đường trong WSN cĩ thể được chia thành chọn đường ngang hàng, chọn đường phân cấp và chọn đường dựa theo vị trí tuỳ thuộc vào cấu trúc mạng. Trong chọn đường ngang hàng, tất cả các nút thường cĩ vai trị hoặc chức năng như nhau. Trong chọn đường phân cấp, các nút sẽ đĩng vai trị khác nhau trong mạng. Trong chọn đường dựa theo vị trí thì vị trí của các nút cảm biến được sử dụng để chọn đường số liệu. Một giao thức chọn đường được coi là thích ứng nếu các tham số của hệ thống cĩ thể điều khiển được để thích ứng với các trạng thái mạng hiện tại và các mức năng lượng khả dụng. Những giao thức này cũng cĩ thể được chia thành các giao thức chọn đường đa đường, yêu cầu, hỏi/đáp, liên kết hoặc dựa vào QoS tuỳ theo cơ chế hoạt động của giao thức. Ngồi ra, các giao thức chọn đường cĩ thể được chia thành ba loại là chủ động, tương tác hoặc lai ghép tuỳ thuộc vào cách thức mà nguồn tìm đường tới đích. Trong các giao thức chủ động, tất cả các đường được tính tốn trước khi cĩ yêu cầu, trong khi đối với các giao thức tương tác thì các đường được tính tốn theo yêu cầu. Các giao thức lai ghép kết hợp cả hai quy tắc ở trên. Khi các nút cảm biến cố định, nĩ thích hợp với các giao thức chọn đường theo bảng hơn là với các giao thức tương tác. Một lượng cơng suất đáng kể được sử dụng để tìm đường và thiết lập các giao thức tương tác. Một số giao thức khác dựa vào định thời và thơng tin vị trí. Để khái quát, cĩ thể sử dụng phân loại theo cấu trúc mạng và cơ chế hoạt động của giao thức (tiêu chuẩn chọn đường) . Việc phân loại và so sánh các giao thức chọn đường trong WSN được chỉ ra trong hình 3 và bảng 1. Hình 3: Phân loại giao thức chọn đường trong WSN Bảng 1: Phân loại và so sánh các giao thức chọn đường trong mạng cảm biến vơ tuyến Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 12 -- Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 13 -- III. Đánh giá chỉ tiêu giao thức chọn đường LEACH Giao thức chọn đường LEACH Heinzelman [1] đã giới thiệu một giao thức phân cấp theo nhĩm cho phép tiết kiệm năng lượng trong mạng cảm biến được gọi là phân cấp nhĩm thích ứng cơng suất thấp (LEACH). Mục đích của LEACH là lựa chọn ngẫu nhiên các nút cảm biến làm các nút chủ, do đĩ việc tiêu hao năng lượng khi liên lạc với nút gốc được trải đều cho tất cả các nút cảm biến trong mạng. Quá trình hoạt động của LEACH được chia thành hai bước là bước thiết lập và bước ổn định. Thời gian của bước ổn định kéo dài hơn so với thời gian của bước thiết lập để giảm thiểu phần điều khiển. Trong bước thiết lập, một nút cảm biến lựa chọn một số ngẫu nhiên giữa 0 và 1. Nếu số này nhỏ hơn ngưỡng T(n) thì nút cảm biến là nút chủ. T(n) được tính như sau: (1) trong đĩ P là tỷ lệ phần trăm nút chủ, r chu kỳ hiện thời, và G là tập các nút khơng được lựa chọn là nút chủ trong 1/P chu kỳ cuối cùng. Sau khi các nút chủ được lựa chọn, những nút này sẽ thơng báo tới tất cả các nút cảm biến trong mạng rằng chúng là các nút chủ mới. Khi các nút cảm biến thu được thơng báo, chúng xác định nhĩm mà chúng sẽ tham gia dựa theo cường độ tín hiệu của thơng báo từ các nút chủ tới các nút cảm biến. Những nút cảm biến này sẽ khai báo với nút chủ thích hợp rằng chúng sẽ là thành viên của nhĩm. Sau đĩ các nút chủ ấn định thời gian cho các nút cảm biến gửi số liệu tới các nút chủ theo phương pháp TDMA. Trong bước ổn định, các nút cảm biến cĩ thể bắt đầu truyền số liệu tới các nút chủ. Các nút chủ cũng tập hợp số liệu từ các nút trong nhĩm của nĩ trước khi gửi những số liệu này tới nút gốc. Sau một thời gian quy định cho bước ổn định, mạng lại tiếp tục bước thiết lập và bước sang một chu kỳ khác trong việc lựa chọn nút chủ Mơ hình hố Việc mơ phỏng giao thức LEACH được thực hiện bằng phần mềm Visual C++ vì đây là một ngơn ngữ lập trình mạnh Thuật tốn mơ phỏng dựa vào cơ chế hoạt động của giao thức phân cấp nhĩm thích ứng cơng suất thấp (LEACH) là sử dụng bước phân nhĩm trước khi truyền số liệu. Một nút cảm biến được chọn làm nút chủ nhĩm và sẽ truyền tất cả số liệu của các nút cảm biến thuộc nhĩm đĩ tới nút gốc. Đây là điểm khác biệt so với các phương pháp thơng thường mà mỗi nút cảm biến sẽ truyền trực tiếp tới nút gốc. Giao thức LEACH giúp kéo dài thời gian sống của mạng bằng cách tối thiểu hố năng lượng sử dụng của mỗi nút cảm biến nhờ vào việc kết hợp số liệu Lưu đồ quá trình thiết lập như sau: Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 14 -- Lưu đồ quá trình ổn định như sau: Kết quả và đánh giá Đánh giá về mức tiêu thụ cơng suất Hình 4 là kết quả mơ phỏng là cho trường hợp mạng WSN gồm 160 nút phân bố đều, cơng suất ban đầu của nút là 3,0, sử dụng giao thức LEACH và Truyền trực tiếp tới nút gốc. Từ đĩ cĩ thể thấy rằng số nút truyền tin kết thúc sau khoảng 470 chu kỳ thời gian đối với trường hợp truyền trực tiếp và sau khoảng 685 chu kỳ thời gian đối với trường hợp sử dụng giao thức LEACH. Do đĩ cĩ thể rút ra nhận xét là sử dụng giao thức LEACH sẽ tiết kiệm cơng suất hơn so với truyền trực tiếp đến nút gốc. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 15 -- Hình 4: Khảo sát số nút truyền tin theo thời gian với 160 nút, phân bố đều, cơng suất ban đầu là 3,0 Ảnh hưởng của phân bố nút tới sự tiêu thụ cơng suất của mạng Hình 5 là kết quả mơ phỏng là cho trường hợp mạng WSN gồm 160 nút phân bố khơng đều, cơng suất ban đầu của nút là 3,0, sử dụng giao thức LEACH và Truyền trực tiếp tới nút gốc. Từ đĩ cĩ thể thấy rằng số nút truyền tin kết thúc sau khoảng 430 chu kỳ thời gian đối với trường hợp truyền trực tiếp và và sau khoảng 680 chu kỳ thời gian đối với trường hợp sử dụng giao thức LEACH. So sánh với trường hợp trong hình 4 cĩ thể rút ra nhận xét là phân bố nút cũng ảnh hưởng đến cơng suất tiêu thụ của mạng. Tuy nhiên, ảnh hưởng này là khơng nhiều. Hình 5: Khảo sát số nút truyền tin theo thời gian với 160 nút, phân bố khơng đều, cơng suất ban đầu là 3,0. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 16 -- Tổng quát : Các đặc tính như độ linh động, chi phí thấp, triển khai nhanh chĩng... của các mạng cảm biến đã tạo ra rất nhiều ứng dụng mới. Trong tương lai, phạm vi ứng dụng rộng lớn này sẽ làm cho các mạng cảm biến trở thành một phần quan trọng trong cuộc sống của chúng ta. Tuy nhiên, việc thực hiện các mạng cảm biến cần phải giải quyết được các vấn đề về khả năng chống lỗi, định cỡ, chi phí, phần cứng, thay đổi cấu hình , mơi trường và cơng suất. Do những giới hạn chặt chẽ và mang tính đặc thù của các mạng cảm biến nên cần thiết phải cĩ các kỹ thuật mạng vơ tuyến đặc biệt (ad-hoc) mới. Chọn đường trong các mạng cảm biến là một lĩnh vực mới, các kết quả nghiên cứu cịn chưa nhiều nhưng đang rất được quan tâm phát triển. Những kỹ thuật này cĩ mục tiêu chung là kéo dài thời gian sống của mạng. Các giao thức chọn đường được phân loại dựa vào cấu trúc mạng gồm cĩ các giao thức chọn đường ngang hàng, phân cấp và theo vị trí. Ngồi ra, các giao thức chọn đường cịn được phân loại theo đa đường, theo yêu cầu, theo hỏi/đáp và theo QoS phụ thuộc vào cơ chế hoạt động của nĩ. Các kết quả mơ phỏng giao thức LEACH của mạng WSN cho thấy đây là một phương pháp chọn đường phân cấp cĩ khả năng tiết kiệm được cơng suất sử dụng và kéo dài thời gian sống của mạng cảm biến. Tuy nhiên, cơ chế hoạt động của giao thức LEACH là lựa chọn số liệu được tập trung và thực hiện theo chu kỳ. Do đĩ, giao thức này chỉ thích hợp với yêu cầu giám sát liên tục bởi mạng cảm biến. Với ứng dụng mà người sử dụng khơng cần tất cả số liệu ngay lập tức thì việc truyền số liệu theo chu kỳ là khơng cần thiết và cĩ thể làm tiêu tốn năng lượng vơ ích. Giao thức LEACH cần tiếp tục được cải tiến để khắc phục hạn chế này. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 17 -- Chương 4: CÁC KỸ THUẬT PHÂN NHĨM TRONG CÁC MẠNG CẢM BIẾN VƠ TUYẾN I. 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à hố học, chuẩn đố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. Hình 1: Cấu trúc mạng cảm biến khơng dây phân nhĩm Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 18 -- 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). • 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 hố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ù hố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 hồn tồ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 tồ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. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 19 -- 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 tồ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: • 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. II. 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 tồn bộ các nút. Ngồ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 Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 20 -- 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 tồ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. • 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 tồ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 tốn tập trung cũng như phân tán để tính tố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 hồn thiện, các thuật tố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 tốn phân nhĩm (theo xác suất hay lặp). II.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 tồ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. Ngồi ra, nĩ khơng tạo ra được sự cân bằng về lưu lượng tải cho tồ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], Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 21 -- 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 tố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 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. II.2. Thực thi của một thuật tốn phân nhĩm Việc thực thi một thuật tố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 tồ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 Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 22 -- 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. II.2.a. 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 tố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, thuật tốn DCA yêu cầu u O( n ) bước lặp để kết thúc thuật tố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 tố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 tố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 tố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 tố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. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 23 -- 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 tố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 tốn khác như LCA (Linked Cluster Algorithm) [1] và LCA2 [2]. Tuy nhiên, thuật tố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. II.2.b. 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 tố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. 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 tốn dựa trên một biểu thức tố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: Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 24 -- 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 tố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ộ: • 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ị Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 25 -- 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 ở đâ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. 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 Đ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 t c R ≥ 6R . Ngồ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ỏ. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 26 -- 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 tố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 tố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 tố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 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 Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 27 -- 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à 3. KẾT LUẬN 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 tốn kích cỡ tối ưu của một nhĩm, xác định tần suất hố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ìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 28 -- Nhận Xét Của Giáo Viên Hướng Dẫn …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… ……………………………………………………. Tìm hiểu về Mạng Cảm Biến GVHD: Lê Nguyễn Mai Duyên Lớp:K12T3 -- 29 -- Mục Lục Lời nĩi đầu 02 Chương 1:SỰ PHÁT TRIỂN CÙA MẠNG CẢM BIẾN 03 I. GIỚI THIỆU 03 II. ĐẶC TRƯNG VÀ CẤU HÌNH MẠNG CẢM BIẾN : 03 III. MƠT SỐ CHUẨN MẠNG CẢM BIẾN 04 IV. ỨNG DỤNG CỦA MẠNG CẢM BIẾN 05 Chương 2: CẤU TRÚC & KIẾN TRÚC GIAO THỨC 06 I. GIỚI THIỆU : 06 II. CẤU TRÚC MẠNG CẢM BIẾN VƠ TUYẾN : 07 III. KIẾN TRÚC GIAO THỨC MẠNG 07 Chương 3:CHỌN ĐƯỜNG TRONG WSN 09 I. Thách thức đối với phương pháp chọn đường trong WSN 09 II.Phân loại và so sánh các giao thức chọn đường trong WSN 11 III. Đánh giá chỉ tiêu giao thức chọn đường LEACH 13 Chương 4:CÁC KỸ THUẬT PHÂN NHĨM TRONG CÁC MẠNG CẢM BIẾN VƠ TUYẾN 17 I. GIỚI THIỆU CHUNG 17 II. 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 19 2.1. Lựa chọn các nút chính 20 2.2. Thực thi của một thuật tốn phân nhĩm 21 II.2.a. Các kỹ thuật phân nhĩm lặp 22 II.2.b. Các kỹ thuật phân nhĩm cĩ tính xác suất 23 3. KẾT LUẬN 27