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à Nội,
T11/2010
ĐỊNH TUYẾN PHÂN CẤP TRONG
MẠNG CẢM BIẾN KHÔNG DÂY WSN
Đề tài
NCKHSV:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA VIỄN THÔNG I
==========
MỤC LỤC

2
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
DANH MỤC HÌNH

3
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
THUẬ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ã

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
Negotiation - Broadcast media
Giao thức thông tin cảm biến thông qua
sự đàm phán – môi trường quảng bá
SPIN-EC
SPIN-PP with a low energy
threshold
Giao thức thông tin cảm biến thông qua
sự đàm phán – điểm điểm với mức
ngưỡng năng lượng thấp
SPIN-PP
Sensor Protocols for Information via
Negotiation – Point to Point
Giao thức thông tin cảm biến thông qua
sự đàm phán – điểm điểm
SPIN-RL SPIN-BC for lossy networks

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ế.
Trước thực tế đó, được sự định hướng và chỉ dẫn của ThS. Nguyễn Thị Thu Hằng, nhóm
sinh viên chúng em đã chọn tên đề tài “Định tuyến phân cấp trong mạng cảm biến không
dây WSN”. Đề tài được trình bày trong 4 chương:
 Chương I: Tổng quan về mạng cảm biến.
 Chương II: Định tuyến trong mạng cảm biến.
 Chương III: Giao thức định tuyến phân cấp LEACH và PEGASIS.
 Chương IV: Mô phỏng hoạt động định tuyến trong mạng WSN.
Chúng em xin bày tỏ lòng biết ơn tới các thầy cô giáo trong khoa Viễn Thông 1, đặc biệt
tới ThS. Nguyễn Thị Thu Hằng và ThS. Nguyễn Ngọc Điệp, các thầy cô đã tận tình chỉ bảo
và cho chúng em những lời khuyên quan trọng trong suốt quá trình chúng em nghiên cứu đề
tài này.
Do kiến thức và khả năng của chúng em còn hạn chế nên đề tài này không tránh khỏi
thiếu sót, chúng em rất mong nhận được sự góp ý của các thầy cô, các bạn sinh viên để nội
dung của đề tài được hoàn thiện hơn nữa.
Hà Nội, ngày 19 tháng 11 năm 2010

5
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
Nhóm sinh viên

6
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
Chương I: TỔNG QUAN VỀ MẠNG CẢM BIẾN
1.1. Khái niệm mạng cảm biến

Một trong những ưu điểm lớn của WNS là chi phí triển khai và lắp đặt được giảm
thiểu, dễ dàng lắp đặt vì kích thước nhỏ gọn, dễ sử dụng. Mạng có thể được mở rộng
theo ý muốn và tùy theo mục đích sử dụng mà có thể thiết kế các nút mạng sao cho
phù hợp. Các nút cảm nhận có bộ vi xử lý bên trong thay vì gửi dữ liệu thô tới nút đích
có thể xử lý đơn giản và gửi dữ liệu đã được xử lý theo yêu cầu.
Các nút mạng có thể hoạt động trong các điều kiện môi trường khắc nghiệt chính
vì vậy ngày nay WSN đã trở thành một giải pháp hấp dẫn vì mang đến sự tiện lợi về
nhiều phương diện và đặc điểm trong nhiều trường hợp kể cả việc làm giảm sự nguy
hiểm cho con người trong những điều kiện môi trường khắc nghiệt. Một hệ thống
WSN hoàn thiện có khả năng theo dõi và cảnh báo mức độ an toàn của môi trường
hoặc định vị sự di chuyển của các đối tượng trong phạm vi của nó.
1.1.4. Một số chuẩn mạng cảm biến
Do phạm vi ứng dụng cua WSN rất rộng lớn, tính chất, đặc trưng của mạng phụ
thuộc vào ứng dụng triển khai cụ thể. Do vậy, các công ty, các phòng thí nghiệm vẫn
thường phát triển, triển khai giao thức riêng (MAC, Routing, synchronisation ) phù
hợp cho từng ứng dụng cụ thể dựa trên các thiết bị phần cứng (transceiver chip) trên
thị trường. Một số chuẩn WSN được biết đến là:
 ALOHA system (U. of Hawaii)
 PRNET system (U.S. Defense)
 WINS (U. of California)
 PicoRadio (U. of California)
 MicroAMPS (M.I.T)
 MANET (Mobile ad-hoc Network)
 Zigbee: dựa trên physical layer và MAC layer của chuẩn WPAN 802.15.4
1.2. Mô hình giao thức mạng
Mô hình giao thức bao gồm lớp vật lý, lớp liên kết dữ liệu, lớp mạng, lớp truyền tải,
lớp ứng dụng và khi chia theo mặt phẳng quản lý thì bao gồm phần quản lý năng
lượng, phần quản lý di động và phần quản lý nhiệm vụ. Mô hình giao thức mà nút chủ
và các nút cảm biến sử dụng được trình bày như trong hình 1.2:


n

l
ý

d
i

đ
ộ
n
g
q
u
ả
n

l
ý

n
h
i
ệ
m

v
ụ
Hình 1.2: Mô hình giao thức của mạng cảm biến


điều khiển lỗi và truy nhập môi trường. Nó đảm bảo giao tiếp điểm - điểm, điểm - đa
điểm tin cậy. Môi trường có tạp âm và các nút cảm biến có thể di động nên giao thức
điều khiển truy nhập môi trường (MAC) phải xét đến vấn đề công suất và phải có khả
năng tối thiểu hoá việc va chạm với thông tin quảng bá của các nút lân cận.
- Lớp vật lý: chịu trách nhiệm lựa chọn tần số, phát tần số sóng mang, điều chế, lập
mã và tách sóng.
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.

10
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
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ó.

12
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
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.

13
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
Hình 1.7: Cấu trúc mạng phân cấp logic
Khi các nút có khả năng tính toán cao hơn hoạt động, các nhiệm vụ tính toán sẽ
được chuyển sang các nút này từ các nút ít khả năng hơn. Nếu không có “computer
servers” như vậy, một cụm các sensor cần chọn ra một nút để thực hiện các nhiệm vụ
như tập trung dữ liệu. Tuy nhiên trong một số trường hợp chỉ có nút có tài nguyên vật
lý thích hợp thích hợp cho việc thực hiện các nhiệm vụ định sẵn. Một nút với hệ thống
định vị toàn cầu (global positioning system - GPS) đóng vai trò chủ chốt trong việc

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
nhau nằm trong 3 mức năng lượng:
• Mức 3 (1 mW): phổ biến nhất cho phép kết nối trong phạm vi 10m
• Mức 2 (2,5 mW): ít thấy nhất, cho phép kết nối trong phạm vi 20m
• Mức 3 (100 mW): là mức có phạm vi kết nối xa nhất, tối đa là 100m
Tuy nhiên Bluetooth cũng có những nhược điểm nhất đinh như tốc độ truyền tin
thấp (khoảng 720kbps).
1.4.2. WLAN
Là mạng LAN không dây với đặc điểm nổi bật là tính linh động, tốc độ cao hơn và
cung cấp cho số lượng người dùng với mật độ cao. Chuẩn IEEE802.11g và 802.11n là
cần thiết cho ứng dụng băng thông rộng và mật độ cao. Chuẩn IEEE802.11e là công

giám sát an ninh

16
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
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.
Hình 1.10: Mạng WSN cảnh báo cháy rừng
1.6. Khả năng mở rộng và phát triển
Tiếm năng của WSN là rất lớn nhưng những ứng dụng thực tế của nó thì chưa được
khai thác triệt để. Một hệ thống mạng giao tiếp thông minh, tiện dụng, tiết kiệm năng
lượng cùng với những ích lợi mà WSN đem lại sẽ khiến WSN trở nên phổ biến và là

17
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
mối quan tâm lớn của con người trong thế kỷ 21. Khả năng mở rộng của mạng cảm
biến không dây phụ thuộc vào sự khắc phục các nhược điểm của chính nó.
Nhược điểm đầu tiên đó là năng lượng, vì các node sensor có kích thước nhỏ, nên
nguồn của nó cũng ít, nếu như chúng ta có thể nạp lại năng lượng cho các sensor thì
thời gian hoạt động và công suất phát của các node sẽ tăng lên.
Nhược điểm thứ hai là dải thông bị giới hạn do nguồn cung cấp cho việc phát tín
hiệu bị hạn chế, hiện nay việc truyền dữ liệu giữa các node là khoảng 10-100Kbits/s.
Do sự giới hạn băng thông gây nên sự khó khăn trong giao tiếp giữa các sensor, ảnh
hướng đến việc đồng bộ hóa.

 Các nút cảm biến bị ràng buộc khá chặt chẽ về mặt năng lượng, tốc độ xử lý, lưu
trữ.
 Hầu hết trong các ứng dụng mạng cảm biến các nút nói chung là tĩnh sau khi
được triển khai ngoại trừ một vài nút có thể di động.
 Mạng cảm biến là những ứng dụng riêng biệt.
 Việc nhận biết vị trí là vấn đề rất quan trọng vì việc tập hợp dữ liệu thông
thường dựa trên vị trí.
 Khả năng dư thừa dữ liệu rất cao vì các nút cảm biến thu lượm dữ liệu dựa trên
hiện tượng chung.
Mục đích chính của mạng cảm biến là truyền thông dữ liệu trong mạng trong khi cố
gắng kéo dài thời gian sống của mạng và ngăn chặn việc giảm các kết nối bằng cách
đưa ra những kỹ thuật quản lý năng lượng linh hoạt. Trong khi thiết kế các giao thức
định tuyến, chúng ta thường gặp phải các vấn đề sau:
 Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng
 Ràng buộc về tài nguyên
 Mô hình dữ liệu trong mạng cảm biến
 Cách truyền dữ liệu

19
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
2.2. Các giao thức định tuyến
2.2.1. Định tuyến truyền trực tiếp
Truyền tin trực tiếp là một giao thức định tuyến dữ liệu ở trung tâm mạng WSN.
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ữ

và gossiping. Flooding yêu cầu mỗi node gửi một bản sao dữ liệu cho tất cả các node
lân cận cho tới khi dữ liệu được truyền tới đích. Gossiping dùng tính ngẫu nhiên để
giảm số bản sao và yêu cầu chỉ một node nhận được một gói dữ liệu và sau đó chuyển
tiếp tới các node đã được chọn trước.
Sự đơn giản của flooding và gossiping do quy luật hoạt động đơn giản và không đòi
hỏi cấu hình mạng phức tạp. Tuy nhiên, do các node được chọn trước nên có thể
đường truyền dữ liệu không phải là đường có năng lượng cao nhất dẫn đến việc gây
lãng phí tài nguyên mạng. Đặc điểm của giao thức này là các node cùng gửi bản sao
dữ liệu gây ra bùng nổ các gói, sự trễ gói là giảm chất lượng của mạng.
Các gói sau khi nhận được gói quảng cáo, nếu muốn nhận gói dữ liệu phải gửi một
gói yêu cầu cho các node nguồn. Do đó các node chỉ gửi dữ liệu cho các các node
quan tâm, hạn chế khả năng bị bùng nổ gói như trong flooding và giảm đáng kể lưu
lượng dư thừa trong mạng. Đây là đặc điểm của giao thức SPIN nhằm giải quyết hạn
chế của giao thức truyền thống. Trong giao thức này, mỗi node mạng có thể theo dõi
sự tiêu thụ năng lượng trước khi phát hay xử lý dữ liệu. Khi mức năng lượng xuống
thấp, node sẽ ngừng gửi dữ liệu, việc truyền dữ liệu sẽ do một node khác có năng
lượng cao hơn đảm nhiệm do đó SPIN giúp kéo dài thời gian sống của các node.
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

WSN
03-SV-2010-RD-VT
Hình 2.5: Giải thuật định tuyến không hiệu quả
Định tuyến theo vị trí phù hợp với mạng WSN vì yêu cầu ít thông tin cho điều khiển
và tương tác, tuy nhiên các liên kết bất đối xứng và các đường giao nhau làm tăng độ
phức tạp của giao thức.
2.2.4. Định tuyến phân cấp.
Định tuyến phân cấp là loại định tuyến dự trên sự phân cấp theo cụm hoặc theo
chuỗi, lợi dụng cấu trúc của mạng để đạt được hiệu quả về năng lượng, sự ổn định, sự
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.

24
§Þnh tuyÕn ph©n cÊp trong
WSN
03-SV-2010-RD-VT
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