B. Mạng cảm biến không dây
IV. Các giao thức định tuyến
2. Giao thức phân cấp
2.1. LEACH
LEACH là một thuật toán định tuyến được thiết kế để thu thập và phân phối dữ liệu đến các bộ góp dữ liệu, thường là các trạm gốc (base station). Đối tượng chính của LEACH là:
Kéo dài thời gian sống của mạng Giảm năng lượng tiêu thụ tại các node mạng Dùng sự tập hợp dữ liệu để giảm số thông điệp cần truyền đi LEACH xây dựng cấu trúc mạng thành các cluster. Mỗi cluster được quản lý bởi các nút chính gọi là cluster head.
LEACH lựa chọn ngẫu nhiên một số node cảm biến để trở thành các node chính và quay vòng vai trò này để phân bố đều tải năng lượng giữa các node cảm biến trong mạng. Ở LEACH, các node 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
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 node 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ủapha ổ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, bắt đầu quá trình chọn lựa các node chính (cluster head). Một số lượng nhỏ các node được xác định trước, P, tự quyết định chúng trở thành các node chính, một node (n) chọn lấy một số ngẫu nhiên, v, trong phạm vi 0 và 1 và so sánh với giá trị ngưỡng T(n). Nếu số ngẫu nhiên này nhỏ hơn giá trị ngưỡng T(n), thì node đó sẽ trở thành node 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 hay xác suất trở thành nút chính
- P, vòng hiện tại - r, và tập hợp các node chưa được lựa chọn làm node chính ở 1/P vòng trước đó - tập G. T(n) được xác định theo công thức:
T(n) = 0 với n còn lại Trong đó, p: tỉ lệ phần trăm nút chủ r: chu kì hiện tại G: tập hợp các nút không được lựa chọn làm nút chủ trong 1/p chu kì cuối.
Tất cả các node 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 node còn lại trong mạng rằng chúng là các node chính mới. Các node khác, không phải là node 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à node chính sẽ thông báo cho các node 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 node muốn gia nhập nhóm và dựa trên số lượng các node thành viên của nhóm, node chính sẽ tạo ra một định thời TDMA, và cấp cho mỗi node 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 node của nhóm. LEACH dùng kỹ thuật đa truy cập theo.
LEACH làm giảm năng lượng tiêu thụ. Các node không phải gởi dữ liệu trực tiếp đến trạm gốc. Yêu cầu năng lượng trong LEACH phân bố đều cho tất cả các node bởi vì chúng đóng vai trò như nhau trong việc lựa chọn node chính. LEACH thực sự là một thuật toán phân bố, không yêu cầu thông tin điều khiển từ trạm gốc. Quản lý các nhóm cục bộ không cần các thông tin chung của toàn mạng. Các kết quả mô phỏng cho thấy, LEACH vượt trội hơn so với các giao thức định tuyến truyền thống như định tuyến đa chặng và truyền trực tiếp, định tuyến năng lượng tối thiểu, và giải thuật định tuyến phân nhóm tĩnh.
2.2. PEGASIS
PEGASIS (Power-Efficient Gatheringin Sensor Information Systems), PEGASIS phân cấp là một họ các giao thức định tuyến và tập trung thông tin trong mạng cảm biến.
Giao thức này đầu tiên hỗ trợ việc kéo dài thời gian sống của mạng nhờ đạt được việc tiêu thụ năng lượng đồng nhất và hiệu suất năng lượng cao qua tất cả các nút trong mạng, thứ hai làm giảm trễ truyền dữ liệu đến sink. Giao thức này xem xét mô hình mạng bao gồm tập hợp các nút đồng nhất được triển khai qua một vùng địa lý. Các nút này có s ự hiểu biết về vị trí các nút khác trong toàn mạng và chúng còn có khả năng điều khiển công suất và bao phủ một vùng tùy ý. Các nút này cũng được trang bị bộ thu phát sóng hỗ trợ CDMA.
Trách nhiệm của các nút này là thu lượm và truyền dữ liệu đến các sink, thông thường là các trạm cơ sở. Mục đích để phát triển một cấu trúc định tuyến và một sơ đồ tập trung dữ liệu để giảm thiểu sự tiêu thụ công suất và truyền dữ liệu được tập trung đến trạm cơ sở với trễ truyền dẫn nhỏ nhất trong khi vẫn cân bằng sự tiêu thụ công suất giữa các nút trong mạng.
được nút lân cận gần nhất mỗi nút sẽ sử dụng cường độ tín hiệu để đo khoảng cách tới các nút lân cận của nó. Sử dụng dữ kiện này các nút sẽ điều chỉnh cường độ tín hiệu sao cho chỉ có nút lân cận gần nhất nghe được.
Một nút trong chuỗi sẽ được trọn làm nút chủ, trách nhiệm của nút chủ là truyền dữ liệu tập hợp được tới trạm cơ sở. Vai trò nút chủ sẽ bị dịch chuyển vị trí trong chuỗi sau mỗi vòng chu kỳ. Chu kỳ này được quản lý bởi sink và việc chuyển trạng thái từ vòng này đến vòng tiếp theo có thể được khởi tạo bởi việc đưa ra dấu hiệu công suất cao bởi sink. Việc quay vòng nút chủ trong chuỗi nhằm đảm bảo công bằng trong tiêu thụ năng lượng giữa các nút trong mạng. Tuy nhiên cũng cần chú ý rằng việc thay đổi có khi dẫn đến nút chủ rời xa trạm cơ sở, sink, khi đó nút này lại cần yêu cầu công suất cao để truyền đến trạm cơ sở. Việc tập trung dữ liệu trong mạng dọc theo chuỗi. Đầu tiên chain leader sẽ gửi một thẻ bài tới nút cuối cùng bên phải cuối chuỗi. Trong khi nhận được tín hiệu này nút cuối sẽ gởi dữ liệu nó thu lượm được đến nút lân cận theo chiều xuôi trong chuỗi, sau đó nút này tập trung dữ liệu và lại tiếp tục gửi đến nút lân cận gần nó nhất, cứ như vậy cho đến khi gửi đến nút chủ. Sau đó nút chủ sẽ lại tập trung dữ liệu và gửi đến sink. Mặc dù đơn giản nhưng mô hình tập trung dạng chuỗi dễ gây ra trễ trước khi dữ liệu tập trung được truyền đến sink. Một phương pháp để giảm độ trễ này là tập trung dữ liệu song song dọc theo chuỗi, và sẽ càng giảm nhiều hơn nếu các nút được trang bị bộ thu phát sử dụng CDMA.
Dùng PEGASIS sẽ giải quyết được vấn đề về mào đầu gây ra bởi việc hình thành các cụm động trong LEACH và giảm được số lần truyền và nhận bằng việc tập hợp dữ liệu. Tuy nhiên PEGASIS lại có độ trễ đường truyền lớn đối với các nút ở xa trong chuỗi.
Hơn nữa ở nút chính có thể xảy ra hiện tượng thắt cổ chai.