Đề tài NCKHSV:
ĐỊNH TUYẾN PHÂN CẤP TRONG
MẠNG CẢM BIẾN KHÔNG DÂY WSN
Sinh viên:
Nguyễn Hoàng Sơn – D07VT3 (chủ trì)
Nguyễn Đình Quang – D07VT3
Lê Minh Ngọc – D08VT3
Vũ Mạnh Thắng – D08VT3
GVHD: ThS. Nguyễn Thị Thu Hằng
Bộ môn: Mạng Viễn Thông

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA VIỄN THÔNG I
==========
Hà Nội, T11/2010 ii

§Þnh tuyÕn ph©n cÊp trong WSN
03-SV-2010-RD-VTMỤC LỤC

MỤC LỤC ii
DANH MỤC HÌNH iv
THUẬT NGỮ VIẾT TẮT v
LỜI NÓI ĐẦU vi
Chương I: TỔNG QUAN VỀ MẠNG CẢM BIẾN 1

03-SV-2010-RD-VT

Chương III: GIAO THỨC ĐỊNH TUYẾN PHÂN CẤP LEACH VÀ PEGASIS 18
3.1. LEACH 18
3.1.1. Tổng quan về LEACH: 18
3.1.2. Hoạt động của LEACH: 18
3.2. PEGASIS 24
3.2.1. Tổng quan về PEGASIS 24
3.2.2. Hoạt động của PEGASIS 24
3.3. So sánh PEGASIS với LEACH 29
3.3.1. Ưu điểm 29
3.3.2. Nhược điểm 30
Chương IV: MÔ PHỎNG HOẠT ĐỘNG ĐỊNH TUYẾN TRONG WSN 31
4.1. Công cụ mô phỏng OMNet++ 31
4.1.1. Giới thiệu OMNeT++ 31
4.1.2. Mô hình trong OMNeT++ 32
4.1.3. Hướng dẫn cài đặt OMNET trên Windows 35
4.2. Thực hiện mô phỏng 36
4.2.1. LEACH 38
4.2.2. PEGASIS 40
4.3. Kết luận 43
PHỤ LỤC 44
A1. LEACH topo 44
A2. PEGASIS topo 45
TÀI LIỆU THAM KHẢO 46

iv

HÌNH 4.1. MÔ PHỎNG MẠNG TRONG OMNET++ 31
HÌNH 4.2. CẤU TRÚC PHÂN CẤP MODULE TRONG OMNET++ 32
HÌNH 4.3. CÁC KẾT NỐI TRONG OMNET++ 34
HÌNH 4.4. TRUYỀN BẢN TIN 35
HÌNH 4.5. MÔ HÌNH MÔ PHỎNG NÚT CẢM BIẾN 37
HÌNH 4.6. CHỌN NODE CHỦ VÀ THU THẬP DỮ LIỆU BẰNG LEACH 39
HÌNH 4.7. TẠO CHUỖI VÀ CHỌN NODE CHỦ TRONG PEGASIS 40
HÌNH 4.8. THUẬT TOÁN CHỌN NODE CHỦ CHẠY TRONG TỪNG NODE 41
HÌNH 4.9. THUẬT TOÁN THU THẬP DỮ LIỆU BẰNG TOKEN 42

v

§Þnh tuyÕn ph©n cÊp trong WSN
03-SV-2010-RD-VTTHUẬT NGỮ VIẾT TẮT

Từ viết tắt
Tiếng Anh
Tiếng Việt
CDMA
Code Division Multiple Access
Đa truy nhập phân chia theo mã
CSMA
Carrier Sense Multiple Access
Đa truy nhập cảm nhận theo sóng mang

Hierarchy-Fixed
Phân nhóm phân bậc tương thích năng
lượng thấp - Cố định
MAC
Media Access Control
Điều khiển truy nhập môi trường
PAN
Personal Area Network
Mạng vùng cá nhân
PEGASIS
Power-efficient Gathering in Sensor
Information System
Tập trung hiệu suất năng lượng trong
hệ thống thông tin cảm biến
QoS
Quality of Service
Chất lượng dịch vụ
SAR
Sensor Aggregates Routing
Giao thức cảm biến kết hợp
SMP
Sensor Management Protocol
Giao thức quản lý cảm biến
SPIN
Sensor Protocols for Information via
Negotiation
Giao thức thông tin cảm biến thông qua
sự đàm phán
SPIN-BC
Sensor Protocols for Information via

Wireless Sensor Network
Mạng cảm biến không dây

vi

§Þnh tuyÕn ph©n cÊp trong WSN
03-SV-2010-RD-VTLỜI NÓI ĐẦU

Ngày nay xã hội phát triển mạnh mẽ nên song song với đó là nhu cầu trao đổi thông
tin, giải trí, tự động hóa… không ngừng tăng lên. Những hệ thống dây cáp phức tạp lại
không thể đáp ứng đầy đủ ở những khu vực xa xôi chật hẹp, và nhu cầu “mọi lúc mọi
nơi” của người sử dụng. Do đó nhờ có những tiến bộ nhanh chóng trong khoa học kỹ
thuật và công nghệ, sự phát triển của mạng cảm biến không dây WSN được tạo nên từ
những cảm biến giá thành rẻ, đa chức năng và tiêu thụ ít năng lượng đã nhận được
những sự chú ý đáng kể.
Bên cạnh những ưu thế có được, mạng WSN đang phải đối mặt với rất nhiều thách
thức, một trong những thách thức lớn nhất đó là nguồn năng lượng bị giới hạn và
không thể nạp lại. Hiện nay rất nhiều nhà nghiên cứu đang tập trung vào việc cải thiện
khả năng sử dụng hiệu quả năng lượng của mạng cảm biến trong từng lĩnh vực khác
nhau. Trong đó đáng chú ý nhất là phương pháp sử dụng giao thức định tuyến phân
cấp để tìm đường đi giữa các node mạng qua đó kéo dài đáng kể thời gian sống của
mạng WSN. Việc nghiên cứu này sẽ góp phần từng bước làm rõ hoạt động của giao
thức định tuyến phân cấp đồng thời hướng tới cải thiện phương pháp định tuyến trong
WSN đáp ứng nhu cầu ứng dụng của mạng thực tế.

không dây linh hoạt, trong đó các node thường là các thiết bị đơn giản và nhỏ gọn, giá
thành rẻ… tạo nên sự kết hợp các khả năng cảm biến, xử lý thông tin và các thành
phần liên lạc để tạo khả năng quan sát, phân tích, phản ứng lại với các sự kiện, hiện
tượng xảy ra trong môi trường xung quanh.
1.1.2.Cấu trúc cơ bản của mạng cảm biến
Một mạng cảm biến cơ bản bao gồm 4 phần:
 Các cảm biến được phân bố theo mô hình tập trung hay phân bố rải rác.
 Mạng lưới liên kết giữa các cảm biến (hữu tuyến hay vô tuyến).
 Điểm trung tâm tập hợp dữ liệu (Clustering)
 Bộ phận xử lí dữ liệu trung tâm Hình 1.1: Mô hình mạng cảm biến thông thường
1.1.3. Đặc trưng cơ bản của mạng cảm biến
Một node trong mạng WSN thông thường bao gồm 2 phần: phần cảm biến
(Sensor) hoặc điều khiển (MCU - Micro Controller Unit) và phần giao tiếp vô tuyến 2

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN
(RF transceiver). Do số lượng node trong WSN là lớn và không cần các hoạt động bảo
trì, nên yêu cầu thông thường đối với 1 node mạng là giá thành thấp (10 – 50 USD) và
kích thước nhỏ gọn (diện tích bề mặt vài đến vài chục cm
2
).
Do giới hạn về nguồn năng lượng cung cấp, giá thành và yêu cầu hoạt động trong
một thời gian dài, nên vấn đề tiêu thụ năng lượng là tiêu chí thiết kế quan trọng nhất

và các nút cảm biến sử dụng được trình bày như trong hình 1.2: 3

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN

Hình 1.2: Mô hình giao thức của mạng cảm biến
1.2.1. Theo mô hình OSI
- Lớp ứng dụng: Tùy từng nhiệm vụ của mạng cảm biến mà các phần mềm ứng
dụng khác nhau được xây dựng và sử dụng trong lớp ứng dụng. Trong lớp ứng dụng
có một số giao thức quan trọng như giao thức quản lí mạng sensor (SMP), giao thức
quảng bá dữ liệu và chỉ định nhiệm vụ cho từng sensor (TADAP), giao thức phân phối
dữ liệu và truy vấn cảm biến (SQDDP).
- Lớp truyền tải: Lớp truyền tải giúp duy trì luồng số liệu khi ứng dụng mạng cảm
biến yêu cầu. Giao thức lớp vận chuyển giữa sink với người dùng (nút quản lý nhiệm
vụ) có thể là giao thức UDP hay TCP thông qua internet hoặc vệ tinh. Còn giao tiếp
giữa sink và các nút cảm biến yêu cầu các giao thức kiểu UDP do các nút cảm biến
hạn chế về bộ nhớ. Hơn nữa các giao thức này còn phải tính đến sự tiêu thụ công suất,
tính mở rộng và định tuyến tập trung dữ liệu .
- Lớp mạng: Lớp mạng quan tâm đến định tuyến dữ liệu cung cấp bởi lớp truyền
tải. Việc định tuyến trong mạng cảm biến ẩn chứa rất nhiều thách thức như mật
độ các nút dày đặc, năng lượng hạn chế… Do vậy thiết kế lớp mạng trong mạng cảm
biến phải tuân thủ các nguyên tắc sau:
 Tính hiệu quả về năng lượng phải được đặt lên hàng đầu.
 Các mạng cảm biến gần như là tập trung dữ liệu.
 Tích hợp dữ liệu và giao thức mạng.
 Phải có cơ chế địa chỉ theo thuộc tính và biết về vị trí.

Bên cạnh đó, các phần quản lý công suất, quản lý di chuyển và quản lý nhiệm vụ sẽ
giám sát việc sử dụng công suất, sự di chuyển và thực hiện nhiệm vụ giữa các nút cảm
biến. Những phần này giúp các nút cảm biến phối hợp nhiệm vụ cảm biến và tiêu thụ
công suất tổng thể thấp hơn.
1.2.1. Theo mặt phẳng quản lý
-Phần quản lý năng lượng: điều khiển việc sử dụng công suất của nút cảm biến. Ví
dụ, nút cảm biến có thể tắt khối thu của nó sau khi thu được một bản tin từ một nút lân
cận tránh tạo ra các bản tin giống nhau. Tương tự, khi mức công suất của nút cảm biến
thấp, nút cảm biến phát quảng bá tới các nút lân cận để thông báo nó có mức công suất
thấp và không thể tham gia vào các bản tin chọn đường. Công suất còn lại sẽ được
dành riêng cho nhiệm vụ cảm biến.
- Phần quản lý di động: phát hiện và ghi lại sự di chuyển của các nút cảm biến để
duy trì tuyến tới người sử dụng và các nút cảm biến có thể lưu vết của các nút cảm
biến lân cận. Nhờ đó, các nút cảm biến có thể cân bằng giữa công suất của nó và
nhiệm vụ thực hiện.
- Phần quản lý nhiệm vụ: cân bằng và lên kế hoạch các nhiệm vụ cảm biến trong
một vùng xác định. Không phải tất cả các nút cảm biến trong vùng đó đều phải thực
hiện nhiệm vụ cảm biến tại cùng một thời điểm nên một số nút cảm biến thực hiện
nhiệm vụ nhiều hơn các nút khác tuỳ theo mức công suất của nó.
Những phần quản lý này cần thiết để các nút cảm biến có thể làm việc cùng nhau sử
dụng hiệu quả công suất, chọn đường số liệu trong mạng cảm biến di động và phân
chia tài nguyên giữa các nút cảm biến.

1.3. Các cấu trúc đặc trưng của mạng cảm biến
1.3.1. Cấu trúc phẳng (flat architecture)
Trong cấu trúc phẳng (flat architecture) (hình 1.3), tất cả các nút đều ngang hàng và
đồng nhất về mặt hình dạng và chức năng. Chúng giao tiếp với sink qua multihop sử
dụng các nút ngang hàng làm bộ tiếp sóng. Hình 1.5: Cấu trúc mạng phân cấp chức năng theo lớp

Nói cách khác, những nhiệm vụ xác định có thể được chia không đồng đều giữa các
lớp, mỗi lớp có thể đảm nhận một nhiệm vụ xác định trong tính toán. Khi đó, các
sensor ở cấp thấp nhất có vai trò là một bộ lọc thông dải đơn giản, tách nhiễu khỏi dữ
liệu, đồng thời các nút ở cấp cao hơn ngừng lọc dữ liệu này. Sự phân tích chức năng
của các mạng cảm biến phản ánh các đặc điểm tự nhiên của các nút, còn gọi là sự phân
biệt theo logic. Ví dụ, một tập hợp con các nút với khả năng truyền thông ở phạm vi
rộng có thể tạo nên cấu hình mạng kiểu phân lớp xếp chồng vật lý (hình 1.6).

Hình 1.6: Cấu trúc mạng phân lớp xếp tầng

Như vậy, một tập hợp con các nút trong mạng có thể được phân biệt một cách logic
bởi chúng đại diện thực hiện một nhiệm vụ cho các nút khác. Những chức năng như
vậy phải bao gồm sự tập trung dữ liệu, truyền thông qua mạng xương sống, hoặc kết
hợp định tuyến giữa các nút. Những qui tắc logic này tạo nên mạng phân cấp logic
(hình 1.7). và có thể thay phiên nhau định kì để đảm bảo sự công bằng.
7

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN Hình 1.7: Cấu trúc mạng phân cấp logic

là độ rộng băng tần của kênh chia sẻ. 8

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN
- Tính kinh tế của cấu trúc tầng: định vị các tài nguyên ở vị trí hoạt động hiệu quả
nhất. Quả thực, nếu triển khai các phần cứng thống nhất, chỉ cần một lượng tài nguyên
tối thiểu để mỗi nút thực hiện tất cả nhiệm vụ. Do số lượng các nút cần thiết phụ thuộc
vào vùng phủ sóng xác định, nên chi phí toàn mạng sẽ không cao. Thay vào đó, nếu
một số lượng lớn các nút với chi phí thấp thực hiện nhiệm vụ cảm nhận, một số lượng
nhỏ hơn các nút với chi phí cao hơn được chỉ định phân tích dữ liệu, định vị và đồng
bộ thời gian, chi phí toàn mạng sẽ giảm.
Tóm lại, dùng cấu trúc tầng đem lại sự tương thích giữa các chức năng trong mạng.

1.4. Các kĩ thuật truyền dẫn sử dụng trong mạng cảm biến
1.4.1. Bluetooth
Bluetooth là công nghệ không dây cho phép các thiết bị điện điện tử giao tiếp với
nhau trong khoảng cách ngắn bằng song vô tuyến thông qua băng tần chung ISM
(Industrial Scientific Medical) trong dải tần 2,4 – 2,8 GHz dành riêng cho các thiết bị
không dây trong công nghiệp, khoa học, y tế.
Đặc điểm của Bluetooth là công suất tiêu thụ thấp, giá thành rẻ . Bluetooth dùng kỹ
thuật trải phổ, song công hoàn toàn . Khi kết nối điểm điểm .cho phép cùng lúc kết nối
với 7 thiết bị đồng thời trong đó Bluetooth đóng vai trò như “master” còn các thiết bị
khác đóng vai trò “slave”.
Bluetooth có thể giúp các thiết bị giao tiếp được với nhau ngay cả khi chúng không
được để chung trong một phòng chỉ cần chúng được để trong khoảng cách tối đa là
100m, và tùy thuộc vào mức năng lượng của thiết bị đó. Các thiết bị có thể kết nối với

 Tốc độ truyền dữ liệu thấp
 Phạm vi hoạt động tốt của Zigbee là 10m – 75m.
 Sử dụng cấu hình chủ tớ cho phép kết nối tối đa 254 node mạng.
 Node mạng Zigbee vận hành tốn ít năng lượng, nó có thể gửi và nhận các gói
tin trong khoảng 15ms.

1.5. Ứng dụng
WSN có rất nhiều ứng dụng trong thực tế:
- Quân sự : theo dõi, định vị các mục tiêu, chiến trường, các nguy cơ tấn công nguyên
tử, sinh hóa, ….

Hình 1.8: Ứng dụng trong quân sự
- Y tế : giám sát bệnh nhân trong bệnh viện, quản lý thuốc, điều khiển các trang thiết
bị từ xa
- Gia đình : thiết kế ngôi nhà thông minh, điều khiển các thiết bị điện, thiết bị sưởi ấm,
giám sát an ninh 10

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN

Hình 1.9: Ngôi nhà thông minh sử dụng cảm biến

- Môi trường : giám sát cháy rừng, thiên tai và các biến đổi khí hậu
- Thương mại : điều khiển trong môi trường công nghiệp và văn phòng, giám sát các
phương tiện giao thông.
- Giám sát và cảnh báo các hiện tượng địa chấn.

1.7. Kết luận
Khả năng ứng dụng của WSN là gần như vô hạn nhưng những ứng dụng thiết thực
của nó lại chưa được khai thác triệt để. Một hệ thống mạng giao tiếp thông minh, tiết
kiệm năng lượng cùng với khả năng áp dụng thực tế cao sẽ là một ưu thế tốt để WSN
có thể phổ biến rộng khắp với giá thành rẻ - một chuẩn cho tương lai.
12

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN

Chương II: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN

2.1. Thách thức trong vấn đề định tuyến
Mặc dù mạng cảm biến có khá nhiều điểm tương đồng so với các mạng adhoc có
dây và không dây nhưng chúng cũng biểu lộ một số các đặc tính duy nhất mà tạo cho
chúng tồn tại thành mạng riêng. Chính những đặc tính này làm cho tập trung mũi nhọn
vào yêu cầu thiết kế các giao thức định tuyến mới mà khác xa so với các giao thức
định tuyến trong các mạng adhoc có dây và không dây. Việc nhằm vào đặc tính này đã
đưa ra một tập các thách thức lớn và riêng đối với WSN.
Chính vì những đặc điểm riêng biệt của mạng cảm biến mà việc định tuyến trong
mạng cảm biến phải đối mặt với rất nhiều thách thức sau:
 Mạng cảm biến có một số lượng lớn các nút, cho nên ta không thể xây dựng
được sơ đồ địa chỉ toàn cầu cho việc triển khai số lượng lớn các nút đó vì lượng
mào đầu để duy trì ID quá cao.
 Dữ liệu trong mạng cảm biến yêu cầu cảm nhận từ nhiều nguồn khác nhau và
truyền đến sink.

Chức năng chính của giao thức là tiết kiệm năng lượng cho mạng bằng cách tạo ra sự
tương tác giữa các node qua sự trao đổi thông điệp trong phạm vi lân cận.
Thành phần chính của giao thức này là gồm các thông điệp interests, data messages,
gradients và reinforcements. Khi một node nào đó cần giữ liệu, nó sẽ phát quảng bá
theo chu kỳ gói interests đến các node xung quanh để xác định xem có node nào có dữ
liệu mà nó đang cần không. Hình 2.1 miêu tả quá trình truyền thông điệp interest. Hình 2.1: Truyền thông điệp Interest.

Sau khi truyền thông điệp interest, trong mạng hình thành việc xây dựng gradient
(có thể xem như hướng và tốc độ truyền) tại các node mạng hình thành liên kết giữa
trạm gốc và các node có dữ liệu. Trong quá trình cài đặt gradient trạm gốc sẽ tạo ra
nhiều tuyến. Đường có chất lượng tốt nhất sẽ được giữ lại trong khi các đường có năng
lượng thấp hơn sẽ bị loại bỏ. Hình 2.2 mô tả quá trình pha cài đặt gradient. 14

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN

Hình 2.2: Pha cài đặt Gradient
Sau khi thiết lập được đường truyền, quá trình truyền dữ liệu bắt đầu. Trong suốt
quá trình truyền dữ liệu, nếu đường truyền bị hỏng hoặc năng lượng của mạng không
đáp ứng được yêu cầu thì một đường truyền khác có năng lượng thấp hơn sẽ được sử
dụng. Hình 2.3 mô tả đường truyền dữ liệu được chọn có năng lượng cao nhất.

2.2.3. Định tuyến theo vị trí
Mục tiêu của giao thức này là dùng thông tin về vị trí để tìm ra tuyến liên lạc
hiệu quả nhất từ nguồn tới đích. Trong giao thức này, một gói dữ liệu từ node nguồn sẽ
được gửi tới các node trong phạm vi lân cận đã được khoanh vùng trước. Vùng giới
hạn này sẽ do node nguồn quyết định hoặc cũng có thể do các node trung gian đảm
nhiệm để tránh việc gói dữ liệu bị gửi lòng vòng trong mạng. Đặc điểm nổi bật của
giao thức này là mỗi node chỉ cần biết thông tin về node lân cân trực tiếp của nó do đó
giao thức này giảm đáng kể overhead và năng lượng tiêu thụ do quá trình truyền chỉ
qua một chặng. Vì vậy giao thức này phù hợp với cấu hình mạng có năng lượng thấp.
Tuy nhiên hiệu quả truyền tin còn phụ thuộc vào mật độ mạng, vị trí xác suất của các
node và quan trọng hơn là quy ước truyền gói tới đích.
Phần quan trọng của giao thức này là quy ước truyền gói tới đích cuối cùng.
Trong quá trình truyền tin, mỗi node sẽ quyết định bước tiếp theo dựa vào vì trí của
nó, vị trí của các node lân cận và node đích. Do chất lượng của việc truyền tin phụ
thuộc vào sự hiểu biết của node đó về cấu hình toàn mạng, điểu này không phù hợp 16

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN
trong mạng WSN do năng lượng trong mạng là hạn chế. Để giải quyết vấn đề này một
số các giải pháp đã được đưa ra. Dưới đây là một ví dụ cụ thể.
Xét mô hình như trên hình 2.4, node hiện tại có dữ liệu cần truyền là MH. Quá
trình chọn lựa các node trung gian tiếp theo trên nguyên tắc node gần node đích hơn
MH sẽ được chọn.
Chiến thuật most – forward - within – R (MFR) sẽ chọn node nằm xa MH nhất
trong số các node nằm trong vùng được định sẵn. Theo đó, bước kế tiếp được chọn bởi

mở rộng. Trong loại giao thức này các nút mạng được chỉ định hoặc tự tổ chức thành
các cụm (hoặc chuỗi) trong đó một nút có mức năng lượng cao hơn các nút khác sẽ
đóng vai trò là nút chủ. Nút chủ thực hiện phối hợp hoạt động trong cụm và chuyển
tiếp thông tin giữa các cụm (hoặc chuỗi) với nhau. Việc tạo thành các cụm (hoặc
chuỗi) có khả năng làm giảm tiêu thụ năng lượng và mở rộng thời gian sống của mạng.
Định tuyến phân cấp gồm 2 thuật toán tiêu biểu là : LEACH và PEGASIS. Cụ thể
về 2 thuật toán này sẽ được đề cập rõ hơn trong chương III.
18

03-SV-2010-RD-VT

§Þnh tuyÕn ph©n cÊp trong WSN

Chương III: GIAO THỨC ĐỊNH TUYẾN PHÂN CẤP
LEACH VÀ PEGASIS

3.1. LEACH
3.1.1. Tổng quan về LEACH:
LEACH (Low Energy Adaptive Clustering Hierarchy) là giao thức phân cấp theo
cụm thích ứng năng lượng thấp dùng trong mạng cảm biến WSN. Đây là giao thức thu
thập và phân phát dữ liệu tới các sink, đặc biệt là các trạm cơ sở. Với mục tiêu chính
của LEACH là:
 Kéo dài thời gian sống của mạng
 Giảm sự tiêu thụ năng lượng bởi mỗi nút mạng
 Sử dụng tập trung dữ liệu để giảm số bản tin truyền trong mạng
3.1.2. Hoạt động của LEACH:
Hoạt động của LEACH được chia thành các vòng (round), mỗi vòng được bắt đầu









P = tỉ lệ phần trăm mong muốn trở thành cluster-heads
r = vòng hiện tại
G là tập các node chưa trở thành cluster-heads ở 1/P vòng trước đó.

Sử dụng ngưỡng này, mỗi node sẽ trở thành cluster-head ở một vài điểm trong 1/p
vòng. Trong suốt vòng thứ 0 (r=0) mỗi node có một xác suất P để trở thành cluster-
head. Các node là cluster-head ở vòng thứ 0 sẽ không thể là cluster-head ở 1/P vòng
tiếp theo. Do đó, xác suất để các node còn lại trở thành cluster-head cần được tăng lên,
và có ít node hơn có đủ điều kiện để trở thành cluster-head. Sau 1/P -1 vòng, T=1 cho
các node chưa trở thành cluster-head, và sau 1/p vòng, tất cả các node một lần nữa đủ
điều kiện để trở thành cluster-head. Phiên bản tiếp theo của giao thức này sẽ bao gồm
một ngưỡng dựa trên năng lượng để tính toán cho các node có năng lượng không đồng
đều. Trong trường hợp này, chúng ta giả sử rằng tất cả các node bằng đầu với năng
lượng bằng nhau đồng đều giữa các node.
Mỗi node mà đã chọn chính nó trở thành cluster-head cho vòng hiện tại, nó quảng
bá một bản tin Advertisement (ADV) cho các node còn lại, sử dụng giao thức non-
persistent CSMA. Bản tin này là một bản tin nhỏ chứa ID của nút đó và một tiêu đề để
phân biệt bản tin này như là một bản thông báo. Đối với pha “cluster-head-
advertisement”, cluster-heads sử dụng giao thức CSMA MAC, và tất cả cluster-heads
truyền bản tin Advertisement cùng năng lượng truyền dẫn. Các node non-cluster-head
phải giữ bộ thu trong suốt quá trình pha thiết lập để lắng nghe bản tin advertisements
của các node là cluster-head. Sau đó, mỗi non-cluster-head quyết định cluster mà nó