Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

Mục lục

Nhóm 2

1


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

Danh mục hình vẽ và bảng

Nhóm 2

3


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

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.

5


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
nội dung của đề tài được hoàn thiện hơn nữa.
Hà Nội, ngày 08 tháng 03 năm 2015
Nhóm sinh viên

Nhóm 2

7


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

CHƯƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY
Trong những năm gần đây, rất nhiều mạng cảm biến không dây đã 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à hoá học, chuẩn đoá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, theo dõi và điều khiển giao thông, các phương tiện xe cộ... Hơn nữa với sự tiến
bộ công nghệ gần đây và hội tụ của hệ thống các công nghệ như kỹ thuật vi điện tử,
công nghệ nano, giao tiếp không dây, công nghệ mạch tích hợp, vi mạch phần cảm
biến, xử lý và tính toán tín hiệu...đã tạo ra những con cảm biến có kích thước nhỏ, đa
chức năng, giá thành thấp, công suất tiêu thụ thấp, làm tăng khả năng ứng dụng rộng
rãi của mạng cảm biến không dây.
Chương này sẽ giới thiệu tổng quan về mạng cảm biến không đây, bao gồm khái
niệm, đặc điểm, cấu trúc mạng, mô hình phân lớp, quản lý năng lượng, ứng dụng của
mạng cảm biến không dây trong đời sống.

nhiên, trong một số trường hợp, việc truyền các gói tin theo chu kỳ lại được đặt
Nhóm 2

9


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

-

-

-

-

lên hàng đầu, hoặc trong một số trường hợp khác, độ tin cậy của thông tin, trễ,…
lại là vấn đề rất quan trọng.
Khả năng chịu lỗi: Yếu tố đặc biệt quan trọng là WSN phải có khả năng xử lý
đượ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.

Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

Hình 1: Cấu trúc mạng cảm biến không dây phân cụm

Như vậy, việc phân cụ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ủ hình thành nên một bậc cao còn các nút thành viên của cụ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ủ của cụm. Nút chủ 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.

1.4 Mô hình phân lớp trong mạng cảm biến không dây
Mô hình phân lớp của mạng cảm nhận không dây bao gồm các lớp: Lớp ứng dụng,
lớp vận chuyển, lớp mạng, lớp liên kết dữ liệu và lớp vật lý. Trong đó lớp vận chuyển
đảm bảo luồng dữ liệu khi lớp ứng dụng yêu cầu, lớp mạng hỗ trợ định tuyến cho lớp
vận chuyển trong truyền dữ liệu đa bước, thủ tục thâm nhập môi trường của lớp liên
kết dữ liệu nhằm hạn chế xung đột với các nút hàng xóm, cuối cùng lớp vật lý đảm
nhận truyền nhận gói tin một cách hiệu quả. Trong nội dung của bài tập nhóm này chỉ
tìm hiểu về 3 lớp dưới cùng trong mô hình phân lớp của mạng WSN, đó là lớp vật lý,
lớp liên kết dữ liệu, mạng nhằm phục vụ cho việc tìm hiểu giao thức định tuyến trong
lớp mạng sẽ được trình bày ở chương 2.

Nhóm 2

13

năng lượng hạn chế, tính không đồng nhất về khả năn xử lý, liên kết, năng lượng… Do
vậy thiết kế lớp mạng trong mạng cảm biến hải tuân thủ các nguyên tắc sau:
Tính hiệu quả về mặt năng lượng phải đặt lên hàng đầu.
Các mạng cảm biến gần như là tập chung 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í
Nhận biết được các thuộc tính của mạng, tính đồng nhất, không đồng nhất.
Nhìn chung, lớp mạng được chia thành ba loại dựa vào cấu trúc mạng định tuyến
ngang hàng, định tuyến phân cấp , định tuyến dựa theo vị trí. Về mặt hoạt động, chúng
được chia thành định tuyến dựa trên đa đường (multipath-based), định tuyến theo truy
vấn (query- based), định tuyến negotiation-based, định tuyến theo chất lượng dịch vụ
(QoS-based), định tuyến kết hợp (coherent-based).
•
•
•
•
•

Nhóm 2

15


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
1.5 Quản lý năng lượng của các thiết bị
1.5.1 Chế độ hoạt động và năng lượng tiêu thụ
Như các phần trên đã trình bày thì năng lượng trong mạng cảm biến không dây là
vấn đề đặc biệt quan trọng bởi vậy điều khiển tiết kiệm năng lượng là vấn đề rất được
quan tâm, năng lượng tiêu thụ chủ yếu trong hoạt động vi điều khiển, thiết bị vô tuyến,
và một phần trong bộ nhớ và phụ thuộc vào kiểu của cảm biến. Chế độ hoạt động của

1.5.6 Mối liên hệ giữa việc tiền xử lý và truyền – nhận dữ liệu.
Sau khi đã có cái nhìn khái quát về năng lượng tiêu thụ trên vi xử lý và truyền nhận
dữ liệu thì câu hỏi đặt ra là: kết hợp giữa việc xử lý dữ liệu và truyền dữ liệu như thế
nào để tiết kiệm năng lượng nhất ? Ví dụ: dữ liệu mà ta nhận được tại mỗi nút mạng
thường ở dạng thô, nếu ta gửi dữ liệu này về trạm gốc mà không xử lý trước thì kích
thước dữ liệu này rất lớn, như vậy sẽ kéo theo một loạt các nút khác cũng phải truyền
– nhận một lượng dữ liệu lớn dẫn tới tiêu tốn rất nhiều nút này. Kết quả là năng lượng
Nhóm 2

17


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
tiêu thụ khi truyền dữ liệu chưa xử lý sẽ lớn hơn rất nhiều năng lượng mà nút sử dụng
để xử lý dữ liệu thô trước khi truyền đi. Việc lựa chọn có xử lý dữ liệu thô trước khi
truyền đi hay không thường dựa trên loại ứng dụng (loại dữ liệu), và kích thước mạng,
phương pháp tiền xử lý thường được sử dụng trong các mạng có kích thước lớn.

1.6 Những thách thức trong mạng cảm biến
Những khó khăn khi thiết kế phần cứng, giao thức truyền thông và các ứng dụng là
vấn đề để triển khai mạng cảm biến thành hiện thực. Duy trì đời sống của mạng cảm
biến và xây dựng một mô hình mạng thông minh là hai thách thức chung, những thách
thức cơ bản là:
- Cấu trúc liên kết trong mạng cảm biến thay đổi thường xuyên.
- Mạng cảm biến sử dụng mô hình truyền thông quảng bá, khác với hầu hết các mạng
-

-

khác thường dựa trên cách truyền thông cơ sở là point to point.

Nhóm 2

19


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
có khả năng tổng hợp dữ liệu, làm một số tính toán (ví dụ tính giá trị trung bình …)
và sau đó phát đi những thông tin tóm tắt mới.
- Tự tổ chức mạng: Do trong mạng cảm biến số lượng các nút lớn và tiềm năng của
từng nút với những đăc điểm điển hình nên yêu cầu khả năng tự tổ chức là thiết yếu.
Hơn nữa, các nút cảm biến có thể bị hỏng (do thiếu năng lượng hoặc rủi ro ngoài),
và các nút mới có thể được đưa vào mạng. Do đó, mạng phải có khả năng định kỳ
tái cấu hình chính nó để có thể tiếp tục hoạt động. Một nút riêng lẻ có thể bị ngắt
kết nối với phần còn lại của mạng nhưng nhìn trên tổng thể mạng cần duy trì một
mức độ kết nối cao.
- Xử lý tín hiệu hợp tác: Một yếu tố để phân biệt với các mạng di động tùy biến
(MANET) là mạng cảm biến cần dự đoán và phát hiện một số sự kiện quan trọng
chứ không chỉ nhằm mục đích truyền thông. Để cải thiện hiệu suất mạng thì giải
pháp hiệu quả nhất là tích hợp dữ liệu từ nhiều cảm biến. Việc tích hợp dữ liệu này
kéo theo việc truyền dữ liệu và bản tin điều khiển. Điều này lại đưa thêm những
giới hạn vào kiến trúc mạng.
- Khả năng truy vấn: Có 2 loại địa chỉ trong mạng cảm biến đó là data-centric (trung
tâm dữ liệu) với truy vấn được gửi tới những vùng đặc biệt trong mạng và addresscentric (trung tâm địa chỉ) với các truy vấn được gửi đến một nút riêng biệt.

1.8 Ứng dụng của mạng cảm biến không dây
Mạng cảm nhận không dây có rất nhiều ứng dụng nhưng hầu hết các ứng dụng
đều thuộc ba dạng: thu thập dữ liệu môi trường, giám sát an ninh, và theo dõi đối
tượng.
1.8.1 Quân sự
Dựa trên ưu điểm có thể triển khai nhanh chóng ( Dải từ máy bay), với khả năng tự

đồng thời, chi phí triển khai mạng WSN cũng nhờ đó mà giảm xuống, mở ra tiềm năng
phát triển mạnh mẽ cho WSN.
Chương1 đã trình bày tổng quan về mạng cảm biến, các vấn đề về khái niệm, cấu
trúc, mô hình phân lớp, quản lý năng lượng, những thách thức, yêu cầu và ứng dụng
của mạng cảm biến.

CHƯƠNG 2: KHẢO SÁT MỘT SỐ GIAO THỨC ĐỊNH
TUYẾN TRONG MẠNG CẢM BIẾN KHÔNG DÂY
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, mạng cảm biến không dây 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 để mạng cảm biến không dây
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 mạng cảm biến không dây. Chương này sẽ trình bày ba loại giao
thức định tuyến chính hay được dùng trong mạng cảm biến, đó là :
+ Định tuyến trung tâm dữ liệu (data - centric protocol).
+ Định tuyến phân cấp (hierarchical protocol).
+ Định tuyến dựa vào vị trí (location - based protocol).

2.1 Phân loại và so sánh các giao thức đị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.
Ngoài ra, một mạng cảm biến có thể dựa trên cấu trúc mạng hoặc cách thức hoạt
động của giao thức để phân loại các giao thức định tuyến khác nhau. Dựa trên cấu trúc
mạng có thể chia thành: Giao thức định tuyến phẳng, giao thức định tuyến phân cấp,

phát triển và là một giao thức rất đáng chú ý trong loại định tuyến trung tâm dữ liệu.
 Giao thức định tuyến phân cấp
Khi công nghệ điện tử phát triển làm cho giá thành của các bộ cảm biến giảm đáng
kể thì khả năng và nhu cầu triển khai một mạng WSN trên pham vi rộng xuất hiện. Khi
đó, một vấn đề nảy sinh là yêu cầu về khả năng mở rộng của mạng. Một cấu trúc mạng
Nhóm 2

25


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
phẳng với số lượng lớn nút cảm biến thường hạn chế về khả năng mở rộng và rất khó
để có thể liên kết hoạt động của các nút trong toàn mạng với nhau. Để giải quyết vấn
đề này, cấu trúc mạng phân cấp (clusters) được đề xuất nhằm giải quyết vấn đề này.
Hướng tiếp cận này có thể giảm thiểu đáng kể yêu cầu với các nút trong cảm biến, xử
lý dữ liệu và truyền thông trong cùng một cụm, do đó, tạo ra khả năng sử dụng hiệu
quả năng lượng và kéo dài thời gian sống của mạng. Ngoài ra, cấu trúc phân cấp cũng
có thể cung cấp khả năng cân bằng tải nếu cần thiết.
Tuy nhiên, mục đích chính của định tuyến phân cấp là để đạt được và duy trì tính
hiệu quả trong việc tiêu thụ năng lượng của các nút cảm biến bằng cách đặt chúng
trong giao tiếp multihop thuộc phạm vi một cụm cụ thể, đồng thời, thực hiện tập trung
và hợp nhất dữ liệu để giảm số bản tin được truyền đến sink. Sự hình thành các cụm
chủ yếu dựa trên năng lượng dự trữ của nút cảm biến và vùng lân cận của nút so với
các nút chủ của cụm.
LEACH là một trong số những cách tiếp cận định tuyến phân cấp đầu tiên cho
mạng cảm ứng. Ý tưởng của LEACH là động lực cho rất nhiều giao thức định tuyến
phân cấp khác phát triển.
 Giao thức định tuyến dựa trên vị trí

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 để

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 được
dữ liệu đang được quảng bá. Điều này tạo ra sự giàn xếp dữ liệu để đảm bảo rằng dữ
liệu chỉ được truyền đến nút quan tâm loại dữ liệu này. Do đó mà loại trừ khả năng bản
tin kép và giảm thiểu đáng kể việc truyền dữ liệu dư thừa qua mạng.
Việc sử dụng bộ miêu tả dữ liệu cũng loại trừ nguy cơ chồng chất vì các nút có thể
giới hạn số lượng loại dữ liệu mà chúng quan tâm đến. Mỗi nút theo dõi mức tiêu thụ
năng lượng của mình trước khi truyền hoặc xử lý dữ liệu. Khi mức năng lượng còn lại
thấp các nút này có thể giảm số lượng dữ liệu mà nó quan tâm hoặc loại bỏ một số
hoạt động như là truyền meta-data hoặc các gói. Chính khả năng thay đổi để thích nghi
với nguồn năng lượng hiện có của các nút đã làm tăng thời gian sống của toàn mạng.
Để truyền và sắp xếp dữ liệu, giao thức SPIN sử dụng ba loại bản tin.

Hình 4: Ba tín hiệu bắt tay của SPIN

Hình 5: Hoạt động của SPIN

Hoạt động của SPIN gồm 6 bước:
- Bước 1: Gửi ADV (Advertise) để thông báo dữ liệu mới tới các nút.
- Bước 2: Gửi REQ (Request) để yêu cầu dữ liệu mà nút quan tâm. Sau khi nhận

được ADV các nút quan tâm đến dữ liệu này sẽ gửi REQ để yêu cầu lấy dữ liệu.
- Bước 3: Bản tin DATA, bản tin này thực sự chứa dữ liệu được cảm biến và kèm
theo mào đầu miêu tả dữ liệu.
Nhóm 2

29


31


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông

Hình 6: 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
trường nhãn thời gian timestamp chứa thời điểm cuối cùng nhận được interest tương
thích, một số trường gradient tương ứng với các nút hàng xóm (mỗi một gradient có
một trường tốc độ dữ liệu chứa tốc độ dữ liệu yêu cầu bởi nút hàng xóm và hướng
truyền), một trường chu kỳ chỉ ra khoảng thời gian tồn tại của interest.
Khi nút cảm biến nhận được một interest, nó kiểm tra trong bộ nhớ cache của nó,
nếu không có mục interest nào tương ứng thì nút sẽ tạo ra một mục interest mới với
các thông số có trong interest vừa nhận được. Ngược lại, nếu như interest nhận được
Nhóm 2

33


đượ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ể.
2.2.2 Giao thức định tuyến phân cấp
 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ủ.
Nhóm 2

35


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
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

Nhóm 2

37


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
thăm lại, nút mạng được thêm dần vào chuỗi làm cho chuỗi lớn dần, kể từ 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 7: 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.
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


41


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
Hình 9: Hoạt động của GAF

Lưới ảo được xây dựng theo cách thức nhất định nhằm đảm bảo rằng, với hai vùng
lân cận G1 và G2 bất kỳ, thì một nút ở vùng G1 phải có khả năng truyền thông với tất
cả nút ở vùng G2, nhờ đó mà tất cả nút trong cùng một vùng là ngang hàng nhau khi
định tuyến. Giả sử rằng bán kính vùng phủ vô tuyến tối đa của nút mạng là như nhau
và bằng R, độ dài một cạnh của phân vùng hình vuông theo các lưới ảo bằng nhau và
bằng l, theo nguyên tắc thiết lập lưới ảo, khoảng cách xa nhất có thể giữa hai nút thuộc
hai phân vùng liền kề bất kỳ phải nhỏ hơn R. Từ đó, suy ra:
(1)
GAF đảm bảo tính tương đương của tất cả nút trong cùng một phân vùng bằng cách
giữ ít nhất một nút trong mỗi phân vùng ở trạng thái hoạt động trong suốt một chu kỳ
thời gian và thiết lập tất cả nút còn lại trong phân vùng đó ở trạng thái nghỉ. Nút cảm
biến trong cùng một phân vùng có thể tương tác với nhau để quyết định xem nút nào
sẽ nghỉ và trong thời gian là bao lâu. Cách thiết lập này không làm ảnh hưởng tới kết
nối của toàn mạng và tính chính xác của thuật toán định tuyến, trong khi đó lại 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.

thuộc vào một số thông số liên quan được thiết lập trong quá trình định tuyến. Để
lựa chọn nút mới thực hiện nhiệm vụ định tuyến, tức là chuyển nút đó sang trạng
thái Active, các nút thực hiện thủ tục Ranking. Quyết định này được thực hiện
căn cứ vào một số nguyên tắc và thông tin về cân bằng tải cũng như năng lượng
còn lại của các nút nhằm mục đích kéo dài tối đa thời gian sống của mạng.
Giao thức GAF cũng có thể hỗ trợ mạng chứa nút di động: Mỗi nút trong một phân
vùng sẽ ước lượng thời gian rời khỏi phân vùng đó của mình và gửi cho nút lân cận
của nó. Theo đó, nút lân cận mà đang trong trạng thái Sleep sẽ điều chỉnh thời gian
nghỉ của mình nhằm đảm bảo việc định tuyến luôn chính xác và không bị ngắt quãng.
Trước khi khoảng thời gian rời phân vùng của một nút đang Active kết thúc, các nút
nghỉ sẽ hoạt động trở lại và một trong số chúng sẽ chuyển trạng thái thành Active.
- GEAR

Giao thức GEAR (Geographic and Energy Aware Routing) là giao thức định tuyến
nhận biết năng lượng và vị trí. Trong một số ứng dụng, mạng cảm biến thường yêu cầu
những thông tin dữ liệu có bao gồm cả những thông số về vị trí địa lý, từ đó giao thức
GEAR ra đời.
Rất nhiều hệ thống định vị sử dụng giao thức này để truyền thông tin tới một vùng
địa lý nhất định, ví dụ như một ứng dụng mạng cảm biến quan tâm tới nhiệt độ trung
bình của khu vực R nhất định trong khoảng thời gian Δt. Khi đó, nếu sử dụng giao
thức Directed Diffusion thì phải gửi bản tin Interest trên toàn mạng lưới, làm lưu
lượng thông tin trên mạng tăng lên và lãng phí tài nguyên mạng. GEAR giới hạn số
lượng bản tin Interest bằng cách định tuyến trực tiếp yêu cầu cảm biến này tới vùng
đích. Theo đó, GEAR có thể tiết kiệm nhiều năng lượng hơn.
Trong giao thức GEAR, mỗi một gói tin yêu cầu có một vùng đích nhất định. Mỗi
nút biết được chính xác vị trí và mức năng lượng còn lại của nó cũng như vị trí và mức
Nhóm 2

45


Nhóm 2

47


Bài tập nhóm cơ sở kỹ thuật mạng truyền thông
là một tham số có thể điều chỉnh được.
d là khoảng cách từ tới D. Được xác định bằng giá trị lớn nhất trong số tất cả
khoảng cách từ các nút lân cận của N tới D.
e(Ni) là năng lượng tiêu thụ tại nút N i, được tính bằng giá trị năng lượng tiêu thụ
lớn nhất trong số các hàng xóm của N.
Nút N lựa chọn nút hàng xóm N min làm nút chuyển tiếp tiếp theo khi nút này có giá
trị hàm h(Nmin,R) + C(N, Nmin) nhỏ nhất, trong đó, C(N, Nmin) thể hiện chi phí truyền
một gói tin từ N tới Nmin. Như vậy, thông qua việc cập nhật cờ chi phí hoặc một hàm
chi phí ước lượng mặc định cho mỗi hàng xóm của nút, nút thực hiện truyền tiếp gói
tin tới vùng đích theo đường dẫ tối ưu.
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.
Giả sử rằng nút Ni nhận được một gói tin cho vùng R và nhận thấy nó cũng nằm
trong R. Ni copy bản tin này thành bốn bản khác nhau và định hướng chúng tới 4 phân
vùng nhỏ trong R. Quá trình phân chia và chuyển tiếp đệ quy này được lặp lại cho đến
khi nút hiện tại là nút cuối cùng trong một phân vùng. Tiêu chuẩn để xác định đó có
phải là nút cuối cùng không như sau: khi điểm xa nhất thuộc vùng vẫn nằm trong vùng
phủ sóng của nút nhưng không có nút hàng xóm nào của nó nằm cùng phân vùng với
nó, và khi đó, gói tin sẽ bị loại bỏ.

Hình 12: Chuyển tiếp địa lý đệ quy