Đồ án tốt nghiệp Mục lục
MỤC LỤC
SVTH: Nguyễn Trọng Dương, lớp: D06VT1 1
Đồ án tốt nghiệp Danh mục hình vẽ
DANH MỤC HÌNH VẼ
Đồ án tốt nghiệp Thuật ngữ viết tắt
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ã
CSMA
Carrier Sense Multiple
Access
Đa truy nhập cảm nhận theo sóng
mang
DS-SS
Direct Sequence - Spread
Spectrum
Trải phổ chuỗi trực tiếp
GAF
Geographic Adaptive
Fidelity
Chính xác tương thích địa lý
GEAR
Geographic and Energy-
Aware Routing
Định tuyến dựa theo sự nhận biết
về địa lý và năng lượng
IEEE
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
WSN Wireless Sensor Network Mạng cảm biến không dây
Đồ án tốt nghiệp Lời mở đầu
LỜI NÓI ĐẦU
Trong những năm gần đây, công nghệ và truyền thông đã đạt được những bước
phát triển ấn tượng và đang đóng vai trò thiết yếu trong cuộc sống của con người.
Chính sự phát triển nhanh chóng của công nghệ đã làm cho hoạt động trao đổi thông
tin trở thành một đặc trưng của xã hội hiện đại. Tuy nhiên, xã hội càng tiến bộ thì
những nhu cầu của con người ngày càng phong phú và khắt khe hơn. Để đáp ứng được
tốt yêu cầu đó, đòi hỏi những người trong lĩnh vực nghiên cứu khoa học phải không
ngừng sáng tạo để tìm ra những giải pháp công nghệ mới, không những chỉ đáp ứng
tốt nhu cầu hiện tại của xã hội, mà còn định hướng cho những ứng dụng mới trong
tương lai. Sự ra đời của mạng cảm biến không dây WSN được đánh giá là một trong
những ví dụ điển hình của những giải pháp công nghệ như vậy.
Mạng WSN có những ưu thế vượt trội như khả năng ứng dụng phong phú, chi
phí triển khai thấp do các nút mạng có giá thành rẻ, tiêu thụ ít năng lượng nhưng vẫn
đảm bảo khả năng cảm biến và truyền thông tốt. Tuy nhiên, bất cứ một hệ thống nào
có tính linh hoạt và ứng dụng rộng rãi cũng đều phải đối mặt với rất nhiều thách thức,
và WSN cũng không phải là một ngoại lệ. Một trong những thách thức lớn nhất của
mạng cảm biến là nguồn năng lượng của các nút cảm biến bị giới hạn và không thể
nạp lại. Để giải quyết vấn đề đó, hiện nay, rất nhiều hướng nghiên cứu đang tập trung
vào việc tìm ra giải pháp để cải thiện khả năng sử dụng hiệu quả nguồn năng lượng
cho mạng cảm biến nhưng đáng chú ý nhất là phương pháp sử dụng giao thức định
tuyến phù hợp. Kết quả là rất nhiều giao thức định tuyến đã được đưa ra, trong đó,
những giao thức định tuyến phân cấp được đánh giá là rất hiệu quả.
Để nắm bắt được một công nghệ mới là một việc rất khó khăn, do đó, quyển đồ
án này không nghiên cứu toàn bộ các giao thức định tuyến phân cấp mà tập trung vào
nghiên cứu “Giao thức định tuyến LEACH trong WSN”. Đặc biệt chú trọng vào
những ưu điểm nổi trội của giao thức LEACH, đồng cũng chỉ ra những nhược điểm
còn tồn tại, từ đó, đề xuất những giải pháp nhằm nâng cao hiệu quả hoạt động của giao
thức thông qua mô phỏng trên nền OMNeT++ trong ba chương:
Chương một sẽ trình bày những thông tin khái quát về ý tưởng và những ứng
dụng của mạng cảm biến không dây (WSN – Wireless Sensor Network), đồng thời
cũng chỉ ra những thách thức về mặt kỹ thuật mà mạng WSN phải đối mặt và các giải
pháp công nghệ hiện tại được đưa ra để giải quyết các vấn đề đó. Trong đó, tập trung
chủ yếu vào vấn đề thiết kế giao thức định tuyến.
Bên cạnh đó, chương này cũng trình bày khái quát một số giao thức định tuyến
được sử dụng phổ biến trong WSN. Để từ đó, nhận thấy được vai trò và khả năng ứng
dụng của đề tài nghiên cứu “giao thức định tuyến LEACH trong WSN” vào thực tiễn
xây dựng và triển khai mạng WSN.
1.1. Giới thiệu chung
1.1.1. Tổng quan về WSN
Mạng cảm biến không dây (WSN – Wireless Sensor Network) được định nghĩa
là một mạng lưới được hình thành từ số lượng lớn các nút cảm biến và có ít nhất một
trạm gốc. Nút cảm biến là những thiết bị nhỏ gọn, có khả năng tự hành và hoạt động
trong một số điều kiện đặc biệt như: sử dụng nguồn năng lượng pin, tiêu tốn ít năng
lượng và có đầy đủ các tính năng để thực hiện nhiệm vụ cảm nhận, đo đạc, tính toán,
lưu trữ dữ liệu nhằm đưa ra các nhận định toàn cục về môi trường xung quanh. Ngoài
ra, chúng cũng được trang bị bộ thu, phát vô tuyến để truyền thông với trạm gốc, là nơi
mà các thông số từ nút gửi về sẽ được phân tích, tính toán, lưu trữ và luôn sẵn sàng
cho người sử dụng [1][18].
Hình 1.1: Mô
hình mạng
cảm biến
thông thường
Có rất
nhiều lý do
khiến WSN
trở thành
một trong
những đề tài
được những vấn đề như: các nút có thể hết năng lượng hoặc bị hỏng, hoặc
truyền thông vô tuyến giữa hai nút bị ngắt.
Thời gian sống: Trong hầu hết các kịch bản, nút cảm biến đều hoạt động nhờ
vào một nguồn cung cấp năng lượng có giới hạn (sử dụng pin). Việc thay thế
nguồn năng lượng của nút trên thực tế thường là không thực hiện được, đồng
thời, một mạng WSN phải duy trì được trong một khoảng thời gian yêu cầu
hoặc càng lâu càng tốt. Do đó, thời gian sống của mạng WSN trở thành một vấn
đề rất quan trọng.
Khả năng mở rộng: Mạng WSN có thể bao gồm một số lượng rất lớn nút cảm
biến, do đó, kiến trúc và giao thức mạng được áp dụng phải có khả năng mở
rộng dễ dàng.
Nguyễn Trọng Dương - D06VT1 9
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Khả năng duy trì: Cả môi trường hoạt động của WSN và bản thân nó luôn luôn
thay đổi, do đó, hệ thống phải có khả năng thích nghi tốt. Điều này đòi hỏi phải
có cơ chế giám sát trạng thái của các nút để điều chỉnh các thông số hoạt động
(ví dụ như chấp nhận cung cấp dữ liệu với chất lượng kém hơn khi nguồn năng
lượng yếu). Theo hướng này, mạng lưới phải tự bảo trì hoặc nó cũng có thể
tương tác với các cơ chế bảo trì bên ngoài để đảm bảo rằng nó có thể hoạt động
và đáp ứng được những tiêu chuẩn như yêu cầu.
Như vậy, 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 đó là làm sao để tìm ra được các cơ chế có thể đáp ứng được tất cả
yêu cầu về đặc điểm trên. 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ù hợp để tìm đường đi giữa các nút mạng, qua đó kéo dài đáng kể
thời gian sống của mạng WSN, đây chính là mục tiêu nghiên cứu của đồ án này.
1.1.2. Những hướng nghiên cứu WSN
Những nghiên cứu trong lĩnh vực WSN đã được thực hiện ở một vài mức độ, bắt
biến. Tuy nhiên, việc thiết kế lớp giao thức mạng trong quá trình triển khai mạng
WSN lại vô cùng phức tạp, vì mỗi một ứng dụng khác nhau, mạng cảm biến có những
đặc điểm, yêu cầu và thách thức khác nhau, nên đỏi hỏi phải có những giao thức định
tuyến phù hợp với nó. Chính vì vậy, những nghiên cứu ở mức độ hệ thống[3][4][5] tập
chung chủ yếu vào lớp mạng nhằm mục đích thiết kế các giao thức định tuyến tiết
kiệm năng lượng.
Kết quả của hướng nghiên cứu này là phát minh ra hàng loạt những thuật toán
định tuyến mới nhằm giải quyết vấn đề định tuyến dữ liệu trong mạng cảm biến. Các
giao thức định tuyến có thể phân chia thành ba loại: Giao thức định tuyến trung tâm dữ
liệu, giao thức định tuyến phân cấp và giao thức định tuyến căn cứ vào vị trí.
Mức độ ứng dụng: Mạng cảm biến không dây WSN được đánh giá là có thể
cung cấp nhiều ứng dụng trong các lĩnh vực như: quân sự, y học, môi trường,…
Những nghiên cứu ở mức độ ứng dụng chủ yếu tập trung tìm hiểu các thông số
liên quan tới vấn đề lắp đặt và vận hành mạng cảm biến theo cách hiệu quả
nhất.
1.1.3. Vấn đề định tuyến
Mặc dù mạng cảm biến có nhiều đặc điểm tương đồng với mạng Adhoc, nhưng
chúng cũng có một số đặc trưng riêng, đòi hỏi phải có các giải pháp công nghệ hoàn
toàn khác với mạng Adhoc. Do vậy, WSN yêu cầu thiết kế các giao thức định tuyến
mới, khác xa so với các giao thức định tuyến đã tồn tại trong mạng Adhoc. Quá trình
thiết kế giao thức định tuyến để WSN có thể đáp ứng được tốt những đặc trưng riêng
đó đã dẫn đến hàng loạt thách thức lớn và riêng có đối với WSN. Phần này, sẽ trình
bày những thách thức phải đối mặt trong quá trình thiết kế giao thức định tuyến cho
WSN [9].
Mục đích chính của mạng cảm biến là truyền thông dữ liệu trong mạng, đồng
thời, cố gắng kéo dài thời gian sống của mạng và ngăn chặn sự cố ngắt 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 những vấn đề sau:
Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng:
Nguyễn Trọng Dương - D06VT1 11
Mô hình dữ liệu trong mạng cảm biến:
Mô hình dữ liệu mô tả luồng thông tin giữa các nút cảm biến và sink. Mô hình
này phụ thuộc nhiều vào đặc điểm của các ứng dụng cụ thể, mà như ta đã biết, mạng
WSN được thiết kế nhằm đáp ứng một số lượng lớn ứng dụng thực tiễn. Trong một số
ứng dụng, yêu cầu mô hình thu thập dữ liệu mà dựa trên việc lấy mẫu theo chu kỳ hay
khi xảy ra các sự kiện trong môi trường quan sát, trong các ứng dụng khác, dữ liệu có
thể được cảm biến và lưu trữ, hoặc có thể được xử lý, tập hợp tại một nút trước khi
chuyển tiếp đến sink.
Nguyễn Trọng Dương - D06VT1 12
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
1.2. Khảo sát một số thuật toán định tuyến
Như đã nêu ở phần trên, có rất nhiều vấn đề phải xem xét khi thiết kế một giao
thức định tuyến trong WSN. Một giao thức định tuyến thỏa mãn được các yêu cầu đó
có nghĩa là đã tạo ra được sự cân bằng giữa khả năng phản ứng với môi trường xung
quanh và hiệu quả của mạng, tức là phải đảm bảo thông tin dữ liệu đầy đủ trong khi
vẫn tối ưu hóa công suất truyền và xem xét đến tài nguyên hạn chế của các nút mạng,
đặc tính thay đổi theo thời gian của kênh truyền vô tuyến. Trên cơ sở đó, nhiều giao
thức đã được đưa ra, phần này sẽ giới thiệu một số giao thức định truyến đã được thiết
kế cho mạng cảm biến.
1.2.1. Phân loại các giao thực định tuyến
Căn cứ vào mô hình dữ liệu trong mạng cảm biến, chúng ta có thể phân chia các
giao thức định tuyến thành 3 loại: Giao thức trung tâm dữ liệu, giao thức phân cấp và
giao thức dựa trên vị trí.
Giao thức định tuyến trung tâm dữ liệu
Trong nhiều ứng dụng của mạng cảm biến thì việc xác định số nhận dạng toàn
cầu cho từng nút là không khả thi. Việc thiếu số nhận dạng toàn cầu cùng với việc
triển khai ngẫu nhiên các nút gây khó khăn trong việc chọn ra một tập hợp các nút
chuyên dụng. Vì thế, dữ liệu được truyền từ mọi nút trong vùng triển khai tới sink.
Tuy nhiên, các nút sẽ gửi dữ liệu với độ dư thừa đáng kể vì không có cơ chế quản lý vị
trí. Do vậy, người ta đã đưa ra các giao thức định tuyến mà có khả năng chọn ra tập
Hầu hết các ứng dụng mạng cảm biến đều yêu cầu thông tin về vị trí của các nút
để phục vụ cho những mục đích khác nhau. Vì mạng cảm biến không có chế độ địa chỉ
nào như địa chỉ IP và chúng được triển khai trong một vùng không gian rộng lớn, vì
vậy thông tin về vị trí cần phải được sử dụng trong các dữ liệu định tuyến theo cách
hiệu quả về mặt năng lượng, từ đó, các giao thức định tuyến dựa trên vị trí được phát
triển.
Trong loại giao thức định tuyến này, GAF và GEAR là hai giao thức rất đáng
được chú ý.
1.2.2. Các giao thức định tuyến
1.2.2.1. Giao thức định tuyến trung tâm dữ liệu
SPIN
SPIN (Sensor Protocol for Information via Negotiation) là giao thức trung tâm dữ
liệu đầu tiên, dựa trên sự thỏa thuận về dữ liệu được quan tâm trước khi chuyển tiếp
dữ liệu nhằm giảm sự dư thừa và tiết kiệm năng lượng. Mục tiêu chính của giao thức
này là tập trung quan sát môi trường một cách hiệu quả vào một số nút cảm biến riêng
biệt trên toàn bộ mạng.
Nguyên lý của giao thức này là dựa trên sự thích ứng về tài nguyên và sắp xếp dữ
liệu. Trong SPIN, tất cả các loại dữ liệu khác nhau đều được đánh dấu bằng một bộ
miêu tả dữ liệu hay còn gọi là meta-data. Khi một nút cảm biến nhận được một một
gói tin dữ liệu mới, nó phát quảng bá meta-data của bản tin dữ liệu đó tới các nút lân
cận (chứ không chuyển tiếp ngay gói dữ liệu) và chờ phản hồi từ các nút này. Khi
nhận được bản tin request từ nút lân cận nào thì gửi gói data cho nút đó.
Nguyễn Trọng Dương - D06VT1 14
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Các nút lân cận khi nhận được một bản tin quảng bá có chứa meta-data từ nút
hàng xóm, nó sẽ quyết định xem có cần loại dữ liệu đó không, nếu cần thì gửi trả lại
bản tin request.
Ý nghĩa của việc dàn xếp dữ liệu (data negotiation) là các nút trong giao thức
SPIN sẽ biết về loại dữ liệu trước khi bất kỳ dữ liệu nào được truyền trong mạng . Nơi
nhận dữ liệu bày tỏ mối quan tâm đến nội dung dữ liệu bằng cách gửi yêu cầu để lấy
Directed Diffussion – giao thức 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. Mục đích của giao thức là giải quyết vấn đề giới hạn
trong khả năng mở rộng mạng lưới của các giao thức trung tâm dữ liệu, tuy nhiên,
Directed Diffussion cố gắng tìm ra một giải pháp đơn giản, thay vì phụ thuộc vào khả
năng định vị toàn cầu của các nút, giao thức này tạo ra sự tương tác giữa các nút trong
một vùng [8].
Cấu trúc của truyền tin trực tiếp bắt nguồn từ chính cách thức hoạt động bên
trong của một mạng cảm biến: Người vận hành hệ thống sẽ thông qua sink, tạo ra một
yêu cầu tới một vùng xác định nào đó trong mạng theo hướng nhất định, các nút trong
vùng đó sẽ thu thập dữ liệu cần thiết và gửi trả lại để hoàn thành yêu cầu. Mỗi khi dữ
liệu được thu thập, mỗi nút cảm biến sẽ kết hợp với các nút lân cận để truyền kết quả
trở về sink.
Giao thức Directed Diffusion bao gồm 4 thành phần: interest (thông tin yêu cầu),
data message (các bản tin dữ liệu), gradient và reinforcements. Hoạt động của Directed
Dissfusion có thể được mô tả như sau:
Nguyễn Trọng Dương - D06VT1 16
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Hình 1.4: Hoạt động của Directed Diffusion
Truyền interest: Dữ liệu được gán nhãn bằng các cặp giá trị thuộc tính. Một yêu
cầu cảm biến tạo bởi sink sẽ được gửi trên toàn mạng dưới dạng các interest.
Bản tin này sẽ truyền qua tất cả các nút trong mạng thể hiện sự quan tâm đến
một loại dữ liệu nào đó. Mục đích của việc thăm dò này là để xem xét xem có
nút cảm biến nào đó có thể tìm kiếm dữ liệu tương ứng với interest không.
Mỗi một nhiệm vụ do sink gửi đi được miêu tả bằng một danh sách các cặp giá
trị thuộc tính, ví dụ, danh sách này có thể chứa kiểu dữ liệu được yêu cầu, chu kỳ thời
gian mà sink muốn nhận thông tin về nhiệm vụ được yêu cầu, thời gian tồn tại của
toàn bộ nhiệm vụ, vùng mạng được chỉ định… Như vậy, mỗi một nhiệm vụ cảm biến
do sink yêu cầu được mô tả trong một bản tin interest.
Tất cả các nút đều duy trì một ngăn xết interest gọi là interest cache để lưu trữ
các interest khác nhau. Mỗi một mục interest lại có nhiều trường khác nhau gồm: Một
tin dữ liệu nhận được khớp với một mục trong cache dữ liệu thì bản tin đó cũng bị loại
bỏ. Ngược lại, bản tin dữ liệu sẽ được thêm vào cache dữ liệu và gửi tới nút lân cận.
Trước khi gửi một bản tin dữ liệu, một nút cần kiểm tra danh sách đường truyền
trong mục interest. Nếu tất cả các đường truyền có tốc độ dữ liệu lớn hơn hoặc bằng
tốc độ yêu cầu của gói tin đến, nút này sẽ có thể chuyển tiếp gói tin dữ liệu vừa nhận
được tới nút lân cận dự phòng. Nếu một vài đường truyền có tốc độ dữ liệu thấp hơn
những đường truyền khác, nút sẽ chuyển những đường truyền đó xuống thành đường
truyền dự phòng.
Như vậy, Directed disffusion có ưu điểm là nếu một đường dẫn nào đó giữa sink
và một nút bị lỗi, một đường dẫn có tốc độ dữ liệu thấp hơn sẽ được thay thế. Kỹ thuật
định tuyến này ổn định và phù hợp với mạng yêu cầu tính linh hoạt cao. Loại giao thức
định tuyến này tiết kiệm năng lượng đáng kể.
1.2.2.2. Giao thức định tuyến phân cấp
Nguyễn Trọng Dương - D06VT1 18
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
LEACH
LEACH (Low-Energy Adaptive Clustering Hierarchy-Centralized) là giao thức
phân cấp theo cụm thích ứng năng lượng thấp. Trong giao thức LEACH, các nút cảm
biến được tập hợp thành từng cụm, thực hiện chức năng thu thập và truyền dữ liệu tới
các sink hoặc trạm gốc thông qua nút chủ.
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 năng lượng tiêu thụ của mỗi nút
Tập trung dữ liệu để giảm bản tin truyền trong mạng
LEACH thông qua mô hình phân cấp để tổ chức mạng thành các cụm, mỗi cụm
được quản lý bởi nút chủ. Nút chủ thực hiện nhiều nhiệm vụ, trong đó nhiệm vụ đầu
tiên là thu thập dữ liệu theo chu kỳ từ các nút thành viên, trong quá trình nhận dữ liệu,
nút chủ sẽ cố gắng tập hợp dữ liệu để giảm dư thừa do có nhiều dữ liệu giống nhau.
Nhiệm vụ thứ hai của nút chủ là trực tiếp truyền dữ liệu đã được tập hợp lại đến trạm
gốc, quá trình truyền dữ liệu này có thể được thực hiện theo kiểu single-hop hoặc
nút hàng xóm gần nhất.
Để xác định được nút lân cận gần nhất, mỗi nút 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ó. Sau khi xác định xong, nó 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.
Hình 1.5: Xây dựng chuỗi sử dụng thuật toán Greedy
Chọn nút chủ: Sau khi chuỗi được thành lập, bước tiếp theo là chọn nút chủ.
Trong một chuỗi chỉ có một nút được chọ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ẽ được thay
đổi trong chuỗi theo vị trí sau mỗi vòng. Việc quay vòng nút chủ trong chuỗi
nhằm đảm bảo sự cân bằng trong tiêu thụ năng lượng giữa các nút mạng. Tuy
nhiên, trong nhiều trường hợp, việc thay đổi có thể làm khoảng cách giữa nút
chủ và trạm gốc lớn, khi đó nút này lại yêu cầu công suất cao để truyền dữ liệu
đến trạm cơ sở.
Nút chủ được chọn theo cách sau: ở vòng thứ i thì nút thứ i mod N (N là số nút
trong mạng) sẽ làm chủ.
Truyền dữ liệu: Quá trình tập hợp dữ liệu trong mạng được tiến hành dọc theo
chuỗi. Trong một vòng, mỗi nút nhận dữ liệu từ nút hàng xóm và kết hợp với
dữ liệu mà nó thu nhận được rồi chuyển tiếp đến nút hàng xóm kế tiếp trong
chuỗi.
Nguyễn Trọng Dương - D06VT1 20
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Trong một vòng, PEGASIS sử dụng cơ chế điều khiển token passing được khởi
tạo bởi nút chủ để bắt đầu truyền dữ liệu từ hai đầu của chuỗi. Chi phí cho các bản tin
điều khiển này là rất nhỏ vì kích thước thẻ bài nhỏ. Đầu tiên nút chủ sẽ gửi một thẻ bài
tới nút cuối cùng bên phải của chuỗi. Khi nhận được tín hiệu này nút cuối sẽ gởi dữ
liệu nó cảm biến được đến nút lân cận theo chiều xuôi trong chuỗi, nút hàng xóm này
tiến hành tập hợp dữ liệu và tiếp tục chuyển tiếp đến nút lân cận gần nó nhất, cứ như
vậy cho đến khi dữ liệu được gửi đến nút chủ. Sau đó, nút chủ tập hợp dữ liệu và gửi
đến sink.
Hình 1.6: Mô hình truyền dữ liệu trong PEGASIS
cải thiện được nút hiệu năng sử dụng năng lượng của các nút mạng bằng cách tắt các
nút lân cận của nút được lựa chọn. Nút ở trạng thái hoạt động sẽ đảm nhận vai trò thu
thập dữ liệu trong vùng của nó, truyền và chuyển tiếp dữ liệu về trạm gốc hoặc tới các
nút đang hoạt động khác.
Như vậy, mặc dù GAF là một giao thức định tuyến dựa trên vị trí, nhưng cũng có
thể được coi là một giao thức phân cấp, trong đó, những phân vùng được xác định
bằng lưới ảo tương đương với các cụm và tiêu chí để phân cụm là căn cứ vào vị trí của
nút. Tuy nhiên, nút chủ không thực hiện bất cứ chức năng tổng hợp, phân tích dữ liệu
nào như trong giao thức phân cấp thông thường khác.
Nguyễn Trọng Dương - D06VT1 22
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Để cân bằng tải và năng lượng tiêu thụ giữa các nút trong cùng một phân vùng,
nút cảm biến lần lượt chuyển từ trạng thái nghỉ sang trạng thái hoạt động. Sự thay đổi
này được thực hiện thông qua ba trạng thái: Tìm kiếm (Discovery), hoạt động (active)
và nghỉ (sleep).
Discovery: Trạng thái Discovery là trạng thái khi một nút tìm kiếm hàng xóm
của nó trong cùng một phân vùng. Khi ở trong trạng thái discovery, một nút sẽ
bật sóng radio và trao đổi bản tin discovery để tìm nút khác trong cùng phân
vùng. Một bản tin discovery chứa ID của nút, ID của phân vùng, năng lượng
còn lại của nút và trạng thái của nút.
Active: Trạng thái Active được sử dụng để định tuyến dữ liệu trong mạng. Khi
một nút bắt đầu trạng thái active, nó thiết lập một khoảng thời gian T
a
để xác
định nó sẽ tồn tại ở trạng thái này trong bao lâu, và khi khoảng thời gian này kết
thúc, nó quay trở lại trạng thái Discovery. Một nút đang ở trạng thái Discovery
hoặc Active có thể chuyển thành trạng thái Sleep khi nó phát hiện ra có một
hoặc vài nút tương đương khác sẽ đảm nhiệm nhiệm vụ định tuyến.
Hình 1.8: Sự chuyển trạng thái trong GAF
Sleep: Trong suốt thời gian nút tồn tại ở trạng thái sleep, nó tắt sóng vô tuyến.
mức năng lượng còn lại của nút lân cận. Để có được các thông tin này, nút có thể sử
dụng giao thức hello đơn giản với nút hàng xóm.
Hình 1.9: Hoạt động của GEAR
Quá trình chuyển tiếp một gói tin tới tất cả các nút thuộc một vùng đích nhất định
bao gồm hai bước:
Nguyễn Trọng Dương - D06VT1 24
Đồ án tốt nghiệp Chương 1: Định tuyến trong mạng WSN
Bước thứ nhất là làm sao để truyền được gói tin tới vùng đích: GEAR sử dụng
một bộ nhận biết năng lượng và vị trí hàng xóm để định tuyến gói tin tới vùng
đích, nút nguồn sẽ định tuyến dữ liệu của nó tiến gần tới vùng đích, đồng thời
cố gắng cân bằng lượng năng lượng tiêu thụ của các nút hàng xóm.
Bước thứ hai là chuyển phát gói tin trong một vùng: Trong hầu hết trường hợp,
GEAR sử dụng thuật toán chuyển tiếp vị trí đệ quy để truyền gói tin trong cùng
một vùng. Tuy nhiên, khi mật độ nút cảm biến thưa, restricted flooding được sử
dụng.
Để mô tả hoạt động của bước một, chúng ta giả định rằng nút N cần gửi một gói
tin tới vùng đích là R với trung tâm là D. N tạo ra sự cân bằng giữa mục đích định
tuyến gói tin tới vùng đích và yêu cầu cân bằng năng lượng tiêu thụ của các nút trung
gian thông qua việc tối thiểu hóa hàm tính cost, gọi là Learned cost. Hàm này là sự kết
hợp giữa năng lượng tiêu thụ để truyền gói tin tới vùng đích R và khoảng cách tới
vùng R.
Mỗi một nút N đều chứa một cờ h(N,R), cờ này được gọi khi cần tìm cost tới
vùng R cho nút N. Các nút sẽ định kỳ cập nhật cờ h(N,R) của nó đối với các nút lân
cận. Nếu một nút không có chứa thông tin về cờ h(N
i
,r) của nút lân cận N
i
, nó sẽ tính
toán giá ước lượng c(N
i
Khi một gói tin đã ở trong vùng đích, một luồng flooding có thể được sử dụng để
phát tán gói tin đó trong vùng R. Tuy nhiên, flooding sử dụng rất nhiều năng lượng,
đặc biệt là với những mạng có mật độ nút cảm biến cao. Do đó, phương pháp chuyển
tiếp vị trí đệ quy được sử dụng để phát tán gói tin trong vùng R.
Nguyễn Trọng Dương - D06VT1 25
Copyright: Tài liệu đại học ©