Header Page 1 of 126.

đại học thái nguyên
Tr-ờng đại học công nghệ thông tin và truyền thông

Nguyễn thành trung

Nghiên cứu một số kỹ thuật định tuyến
của mạng cảm biến không dây dựa trên
bảng băm phân tán và ứng dụng

luận văn thạc sĩ khoa học máy tính

thái nguyên 2013
Footer Page 1 of 126.

S húa bi Trung tõm Hc liu

/>

Header Page 2 of 126.

đại học thái nguyên
Tr-ờng đại học công nghệ thông tin và truyền thông

Nguyễn thành trung

Nghiên cứu một số kỹ thuật định tuyến
của mạng cảm biến không dây dựa trên
bảng băm phân tán và ứng dụng


thiết kế tốt nghiệp của ngƣời khác.
Thái Nguyên, ngày 20 tháng 09 năm 2013

Nguyễn Thành Trung

Footer Page 3 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 4 of 126.

LỜI CẢM ƠN
Trƣớc hết, tôi vô cùng biết ơn sâu sắc đến Nhà giáo ƣu tú - TS Phạm
Việt Bình, ngƣời thầy đã trực tiếp dành nhiều thời gian tận tình hƣớng dẫn,
cung cấp những thông tin, tài liệu quý báu giúp đỡ tôi hoàn thành bản luận
văn này.
Tôi xin chân thành cảm ơn Ban lãnh đạo Trung tâm Dự án quốc tế
VLIR – Trƣờng Đại học Công nghệ thông tin và Truyền thông đã tạo nhiều
điều kiện giúp tôi hoàn thành luận văn này.
Sau cùng tôi xin bày tỏ lòng biết ơn đến ngƣời thân, cùng bạn bè, đồng
nghiệp cơ quan, những ngƣời luôn cổ vũ động viên tôi hoàn thành bản luận
văn tốt nghiệp này.
Thái Nguyên, ngày 20 tháng 09 năm 2013

Nguyễn Thành Trung

Footer Page 4 of 126.


1.5.1. Bảng băm (Hash Table) ................................................................... 15
1.5.2. Bảng băm phân tán (Distributed Hash Table) ................................. 16
1.6. Định tuyến sử dụng Bảng băm phân tán ................................................18
1.6.1.Sử dụng ý tƣởng định tuyến của mạng P2P trong mạng cảm biến
không dây ................................................................................................... 18
1.6.2. Ánh xạ giữa mạng ngang hàng với mạng cảm biến thông qua Bảng
băm phân tán .............................................................................................. 19
CHƢƠNG 2: MỘT SỐ KỸ THUẬT ĐỊNH TUYẾN SỬ DỤNG BẢNG BĂM . 22
Footer Page 5 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 6 of 126.

PHÂN TÁN TRONG MẠNG CẢM BIẾN KHÔNG DÂY.................................... 22
2.1. Kỹ thuật Chord cho mạng cảm biến – CSN ( Chord for Sensor
Netwworks ) ..................................................................................................22
2.1.1. Nghiên cứu về CSN ......................................................................... 22
2.1.2. Phƣơng thức chuỗi (Chain method) ................................................. 26
2.1.3. Phƣơng thức lấy trung bình (Set-Average Method) ........................ 26
2.1.4. EEmode và Rmode .......................................................................... 27
2.1.5. Lƣu đồ kỹ thuật Chord cho mạng cảm biến không dây................... 29
2.1.6. Nhận xét về kỹ thuật Chord cho mạng cảm biến ............................. 30
2.2. Kỹ thuật định tuyến băm ô – CHR ( Cell Hash Routing) ......................31
2.2.1 Nghiên cứu về CHR .......................................................................... 31
2.2.2. Phần bên trong của một ô ................................................................ 32
2.2.3. Định tuyến trong CHR ..................................................................... 34
2.2.4. Lƣu đồ kỹ thuật định tuyến băm ô ................................................... 36

3.2. Khảo sát một số mô phỏng sử dụng cho mạng cảm biến ......................63
3.2.1. Tiêu chí phân loại............................................................................. 63
3.2.2. Phân loại các công cụ mô phỏng theo chức năng ............................ 63
3.3 Xây dựng mô phỏng theo kỹ thuật GHT ................................................64
3.3.1. Xây dựng chƣơng trình mô phỏng ................................................... 64
3.3.2. Kết quả mô phỏng mạng cảm biến .................................................. 66
KẾT LUẬN .................................................................................................................... 69
Tài liệu tham khảo.......................................................................................................... 70

Footer Page 7 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 8 of 126.

DANH MỤC THUẬT NGỮ
Viết tắt

Viết đầy đủ

Nghĩa tiếng Việt

WSN

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

DHT



tán dựa theo cấu trúc mạng

Virtual Ring Routting

Kỹ thuật định tuyến dựa theo cấu

VRR

trúc vòng ảo
P2P

Peer to peer

Mạng ngang hàng

DSC

Data Store Center

Lƣu trữ dữ liệu trung tâm

LEACH

Low-energy adaptive

Giao thức phân cấp theo cụm thích

clustering hierarchy


DANH MỤC HÌNH VẼ
Hình 1.1 Biểu tƣợng của mạng cảm biến .......................................................................2
Hình 1.2 Nút cảm biến không dây của Zolertia Z1 .......................................................4
Hình 1.3 Các thành phần của một nút cảm ứng .............................................................6
Hình 1.4: Cấu trúc phẳng của một mạng cảm biến .......................................................7
Hình 1.5: Cấu trúc tầng của mạng cảm biến không dây ...............................................8
Hình 1.6: Cấu trúc mạng đƣợc phân cấp theo chức năng .............................................8
Hình 1.7: Mô tả hoạt động của bảng băm.................................................................... 15
Hình 1.8: Lƣu trữ và tìm kiếm dữ liệu trong DHT ..................................................... 17
Hình 1.9: Kiến trúc bảng băm phân tán ....................................................................... 18
Hình 1.10: Mô hình định tuyến cơ bản của DHTs ..................................................... 20
Hình 2.1 : Một mạng Chord với 3 nút......................................................................... 23
Hình 2.2: Alpha-1 và Alpha-m sẽ không thực hiện giao tiếp trực tiếp ..................... 24
Hình 2.3: Thuật toán mô phỏng phƣơng thức chuỗi (Chain) .................................... 26
Hình 2.4: Thuật toán theo phƣơng thức lấy trung bình .............................................. 27
Hình 2.5: Sự giao thoa về xử lý giữa Rmode và EEmode ......................................... 28
Hình 2.6: Phân chia không gian thành các ô với kích thƣớc cố định ........................ 32
Hình 2.7: Định nghĩa về đồ thị của các cụm ............................................................... 33
Hình 2.9: Home cell và Home perimetter.................................................................... 34
Hình 2.10: Vị trí địa lý của các nút............................................................................... 41
Hình 2.11: Không gian của các nút trên hệ toạ độ ảo ................................................. 41
Hình 2.12: Kết quả sau khi phân chia khu vực mỗi nút vào các hình chữ nhật và đƣa
thông tin toàn mạng vào bảng băm phân tán hai chiều .............................................. 42
Hình 2.13: Liên kết giữa cấu trúc mạng vòng ảo và .................................................. 46
Hình 2.14: Một ví dụ về GHT ...................................................................................... 52
Hình 2.15: Phƣơng pháp chuyển tiếp tham lam.......................................................... 54
Hình 2.16: Một ví dụ về việc x không có hàng xóm gần nhất đến D ....................... 55
Hình 2.17: Quy tắc bàn tay phải ................................................................................... 55
Hình 3.1: Thử nghiệm mạng cảm biến không dây trên phạm vi 100x100 m .......... 66
Footer Page 9 of 126.

đƣợc nhiều sự quan tâm. Mạng cảm biến không dây đƣợc ứng dụng rất nhiều
trong đời sống hàng ngày với các lĩnh vực nhƣ: môi trƣờng, y tế, quân sự,
kinh doanh, cảnh báo tự động… Tuy nhiên, việc nghiên cứu và xây dựng
mạng cảm biến không dây cũng gặp nhiều những khó khăn và thách thức. Và
một trong những thách thức lớn nhất trong mạng cảm biến không dây là vấn
đề duy trì năng lƣợng của các thiết bị trong mạng. Với nguồn năng lƣợng giới
hạn của WSN. Hiện nay đang có rất nhiều nghiên cứu 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 WSNs trong nhiều lĩnh vực
khác nhau. Nghiên cứu của nhiều tác giả đã khẳng định, nâng cao sự tồn tại
(thời gian sống) của mạng, hay giảm thiểu tổn hao năng lƣợng trong hoạt động
của mạng WSNs chính là quá trình truyền thông. Do đó, việc tối ƣu kỹ thuật
định tuyến trong WSNs luôn là chủ đề nghiên cứu mang tính thời sự.
Luận văn nghiên cứu chia làm ba phần.
Chƣơng 1: Đƣa ra khái niệm tổng quan mạng cảm biến không dây.
Chƣơng 2: Phân tích một số kỹ thuật định tuyến sử dụng bảng băm
phân tán (DHTs – Distribute Hash Table) nhƣ: GHT, CSN, CHR, T-DHT,
VRR và việc nghiên cứu, kế thừa kỹ thuật DHTs trong việc định tuyến với
mạng WSNs.
Chƣơng 3: Dựa trên những kết quả phân tích đạt đƣợc, cài đặt, thử
nghiệm và đánh giá kết quả kỹ thuật định tuyến.

Footer Page 11 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 12 of 126.

2

3

đơn giản, nhỏ gọn, giá thành thấp,… và có số lƣợng lớn. Đƣợc phân bố không
có hệ thống và triển khai trên một phạm vi rộng, nguồn năng lƣợng đƣợc sử
dụng trong WSNs là pin nên không tránh khỏi việc hạn chế về mặt thời gian
trong những hoạt động lâu dài.
Các mạng vô tuyến khác bao gồm mạng Cellular, mạng WLAN, và
mạng phạm vi nhỏ (Bluetooth). Các gói chuyển từ mạng này sang mạng khác
sẽ đƣơc hỗ trợ qua internet không dây. Mạng Cellular đích đến là những ngƣời
sử dụng với tính di động cao. Tốc độ dữ liệu cho tính di động tại mức này bị
giới hạn do dịch tần Dopper. Mặt khác,WLAN có tốc độ dữ liệu cao.
Bluetooth và Home RF đích đến là tại phạm vi nhỏ. Tốc độ dữ liệu mong
muốn cho dải radio thấp hơn và ngắn hơn nhiều, tính di động cũng thấp.
WSNs khác với các mạng trên, nó có một số lƣợng lớn các nút. Khoảng
cách giữa các nút liền kề là ngắn hơn so với các mạng trên. Do WSN hoàn
toàn chỉ là các nút, chi phí cho mỗi nút là nhỏ. Mức tiêu thụ năng lƣợng cũng
thấp hơn nhiều, nhƣng với số lƣợng lớn các nút việc thay thế pin cho mỗi nút
rất vất vả, thậm chí cả khi là một tháng phải có thay thế một lần cũng là quá
vất vả.
Một số đặc điểm của mạng cảm biến không dây:
 Có khả năng tự tổ chức, yêu cầu ít hoặc không có sự can thiệp của
con ngƣời
 Truyền thông tin cậy, quảng bá trọng phạm vi hẹp và định tuyến
đa bƣớc nhảy
 Triển khai dày đặc và khả năng kết hợp giữa các nút cảm biến
 Cấu hình mạng có thể thay đổi thƣờng xuyên phụ thuộc vào yêu
cầu và việc hƣ hỏng ở các nút.
 Các giới hạn về mặt năng lƣợng, công suất phát, bộ nhớ và công
suất tính toán
Chính những đặc tính này đã đƣa ra những chiến lƣợc mới và những


Footer Page 14 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 15 of 126.

5

-

–

1.
:
2x

.
3.6V

3V.

ngu

3.6V.

3V.
đề xuất sử dụng pin 2xAA khi tr

Các bộ phận cảm ứng (Sensing units) bao gồm cảm biến và bộ chuyển
đổi tƣơng tự sang số (ADC – Analog to Digital Converter). Dựa trên những
hiện tƣợng quan sát đƣợc, tín hiệu tƣơng tự tạo ra bởi sensor đƣợc chuyển
sang tín hiệu số bằng bộ ADC, sau đó đƣợc đƣa vào bộ xử lý.
Bộ xử lý thƣờng đƣợc kết hợp với bộ lƣu trữ nhỏ (Storage units), quyết
định các thủ tục cho các nút kết hợp với nhau để thực hiện các nhiệm vụ
định sẵn.
Phần thu phát vô tuyến kết nối các nút vào mạng. Chúng gửi và nhận
các dữ liệu thu đƣợc từ chính nó hoặc các nút lân cận tới các nút khác.
Phần quan trọng nhất của một nút mạng cảm biến là bộ nguồn. Bộ
nguồn có thể là một số loại pin. Để các nút có thời gian sống lâu thì bộ nguồn
rất quan trọng, nó phải có khả năng nạp điện từ môi trƣờng nhƣ là năng lƣợng
ánh sáng mặt trời.

Footer Page 16 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 17 of 126.

7

Hầu hết các kỹ thuật định tuyến và các nhiệm vụ cảm biến của mạng
đều yêu cầu cần có độ chính xác cao về vị trí. Vì vậy cần phải có các bộ định
vị. Các bộ phận di động, đôi lúc cần để dịch chuyển các nút cảm biến khi cần
thiết để thực hiện các nhiệm vụ đã ấn định nhƣ cảm biến theo dõi sự chuyển
động của một vật nào đó.
Tất cả những thành phần này cần phải phù hợp với kích cỡ từng

ở đó mỗi nút xác định thực hiện các nhiệm vụ định sẵn.

Hình 1.5: Cấu trúc tầng của mạng cảm biến không dây

Hình 1.6: Cấu trúc mạng được phân cấp theo chức năng
Trong cấu trúc tầng thì chức năng cảm nhận, tính toán và phân phối dữ
liệu không đồng đều các nút. Những chức năng này có thể phân theo cấp, cấp
thấp nhất thực hiện tất cả nhiệm vụ cảm nhận, cấp giữa thực hiện tính toán,
cấp trên cùng thực hiện phân phối dữ liệu (hình 1.6)

Footer Page 18 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 19 of 126.

9

Mạng cảm biến xây dựng theo cấu trúc tầng hoạt động hiệu quả hơn cấu
trúc phẳng, do các lý do sau:
 Cấu trúc tầng có thể giảm chi phí mạng cảm biến bằng việc định
vị các tài nguyên ở vị trí mà chúng hoạt động hiệu quả nhất. Rõ ràng là
nếu triển khai các phần cứng thống nhất, mỗi nút chỉ cần một lƣợng tài
nguyên tối thiểu để thực hiện các nhiệm vụ. Vì số lƣợng các nút cần
thiết phụ thuộc vào vùng phủ sóng xác định, chi phí của toàn mạng vì
thế sẽ không cao. Thay vào đó, nếu một số lƣợng lớn các nút có chi phí
thấp đƣợc chỉ định vào nhiệm vụ cảm biến, một số lƣợng nhỏ hơn các
nút có chi phí cao hơn đƣợc chỉ định làm nhiệm vụ phân tích dữ liệu,


10

cụm xung quanh trạm gốc. Mỗi một trạm gốc đóng vai trò là cầu nối
với cấp cao hơn, cấp này đảm bảo việc giao tiếp trong cụm thông qua
các bộ phận hữu tuyến. Trong trƣờng hợp này, dung lƣợng của mạng
tăng tuyến tính với số lƣợng các cụm, với điều kiện là số lƣợng các cụm
phải tăng ít nhất phải nhanh bằng n . Các nghiên cứu khác đã thử cách
dùng các kênh khác nhau ở các mức khác nhau của cấu trúc phân cấp.
Trong trƣờng hợp này dung lƣợng của mỗi lớp trong cấu trúc tầng và
dung lƣợng của mỗi cụm trong mỗi lớp xác định là độc lập.
Tóm lại, việc tƣơng thích các chức năng trong mạng có thể đạt đƣợc khi dùng
cấu trúc tầng. Đặc biệt là ngƣời ta đang tập trung nghiên cứu về các tiện ích
tìm địa chỉ. Những chức năng nhƣ vậy có thể phân phối đến mọi nút, một
phần phân bố đến tập con của các nút. Giả thiết rằng các nút đều không cố
định và phải thay đổi địa chỉ một cách định kỳ, sự cân bằng giữa những lựa
chọn này phụ thuộc vào tần số thích hợp của các chức năng cập nhật và tìm
kiếm. Hiện nay cũng có rất nhiều mô hình tìm kiếm địa chỉ trọng mạng cấu
trúc tầng.
1.2.2.3. Một số chuẩn của mạng cảm biến không dây
Do phạm vi ứng dụng của mạng cảm biến không dây là rất lớn. Với
những tính chất và đặc trƣng của mạng phụ thuộc vào từng ứng dụng đƣợc
triển khai trong từng trƣờng hợp 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, Routting,
Synchronisation…), phù hợp cho từng thiết bị phần cứng (transceiver chip)
trên thị trƣờng.
Một số chuẩn WSN đƣợc biết đến:
ALOHA system (U. Hawaii)
PRNET system (U.S. Defense)
WINS (U. of California)

hình mạng và giao thức truyền thông cần tránh sử dụng các thành phần đắt
tiền và tối thiểu hoá độ phức tạp của giao thức truyền thông. Trong mạng cảm
biến, số lƣợng các nút mạng sử dụng là khá lớn và chi phí để sản xuất từng nút
con đƣợc giảm đi thì giá thành của toàn bộ hệ thống giảm đi đáng kể.
Ngoài các yếu tố trên thì một phần khá lớn tác động tới giá thành đó là
chi phí quản trị và bảo trì hệ thống. Mạng cảm biến không dây đã làm tốt hai
chức năng cơ bản đó là tự cấu hình và bảo trì. Tự cấu hình có nghĩa là tự động
dò tìm vị trí các nút lân cận và tổ chức thành một cấu trúc xác định. Tự bảo trì
có nghĩa là tự động phát hiện và sửa lỗi phát sinh trong hệ thống (ở các nút
mạng hoặc các liên kết giữa các nút) mà không cần sự tác động của con ngƣời.

Footer Page 21 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 22 of 126.

12

Với các tính năng ƣu việt này thì mạng cảm biến không dây ngày càng tỏ rõ
những ƣu việt của mình.
1.3.3. Loại hình mạng
Với một số ứng dụng đơn giản trong phạm vi hẹp thì mạng hình sao
(star network) có thể đáp ứng đƣợc các yêu cầu truyền nhận và xử lý dữ liệu.
Trong mạng hình sao, một nút sẽ đóng vai trò nút chủ, các nút còn lại là nút
con kết nối tới nút chủ. Tuy nhiên khi mạng đƣợc mở rộng thì cấu hình sao
đơn thuần sẽ không đáp ứng đƣợc, mạng sẽ phải có cấu hình đa chặng (multihop). Cấu hình này sẽ đòi hỏi nhiều tài nguyên bộ nhớ và xử lý tính toán hơn
do mật độ của các nút mạng tăng và diện tích của mạng đƣợc phủ trên một

Các ứng dụng thông thƣờng của mạng cảm biến không có yêu cầu cao
về thời gian thực khi truyền mà chủ yếu chú trọng vào chất lƣợng nguồn tin
(trừ một số trƣờng hợp đặc biệt nhƣ hệ thống báo cháy). Tuy nhiên trong một
mạng lƣới khá lớn, các thông tin của các nút con đƣợc tập hợp ở một nút chủ
để xử lý và đƣa về trạm trung tâm thì yếu tố đồng bộ hoá là rất quan trọng.
1.3.6. Tính di động
Nhìn chung các ứng dụng trong mạng cảm biến không dây không đòi
hỏi tính di động nhiều vì khi triển khai các nút mạng thƣờng ở các vị trí cố
định. Các phƣơng thực định tuyến trong mạng cảm biến không dây cũng đơn
giản hơn so với các mạng ad-hoc khác (nhƣ MANET).
1.4. Những thách thức trong việc triển khai mạng cảm biến không dây
Tuy rằng mạng cảm biến không dây WSNs có rất nhiều ƣu điểm và ứng
dụng hữu ích, nhƣng khi triển khai trên thực tế sẽ gặp phải một số hạn chế,
khó khăn và thách thức về mặt kỹ thuật. Nắm rõ những khó khăn, thách thức
này sẽ giúp chúng ta có những giải pháp để khắc phục, cải tạo và tối ƣu hoá
những ứng dụng của mạng cảm biến hơn nữa.
1.4.1 Giới hạn về năng lượng
Đây có thể coi là một trong những vấn đề đƣợc quan tâm nhiều nhất
trong khi triển khai xây dựng mạng cảm biến. Thông thƣờng, các thiết bị trong
mạng cảm biến không dây thƣờng sử dụng các nguồn năng lƣợng có sẵn (pin
năng lƣợng). Khi số lƣợng nút mạng là rất lớn, yêu cầu sử dụng các nguồn
năng lƣợng rất cần đƣợc tính toán. Liên quan đến khoảng cách truyền lớn thì
năng lƣợng tiêu thụ lại càng cao. Chính vì vậy, các giải pháp nghiên cứu nhằm
tối ƣu hoá việc xử lý và truyền dữ liệu với một năng lƣợng ban đầu xác định
của các nút nhằm kéo dài thời gian sống cho mạng là rất cần thiết.
1.4.2. Giới hạn về phần cứng
Yêu cầu của mạng cảm biến không dây là kích thƣớc của các nút phải
nhỏ vì có một số ứng dụng đòi hỏi phải triển khai một số lƣợng lớn các nút
Footer Page 23 of 126.


Xây dựng và duy trì các bảng định tuyến với các tuyến thay thế (để phù
hợp với những thay đổi của điều kiện truyền) dựa trên những bộ xử lý chi phí
thấp và tiêu tốn ít năng lƣợng là một khó khăn thực sự lớn. Độ khó khăn của
phƣơng pháp này tỉ lệ thuận với kích cỡ và số lƣợng của các chặng.
Nhiều kỹ thuật mới và phức tạp đã đƣợc đề xuất để giải quyết vấn đề này. Để
giảm thiểu tiêu thụ năng lƣợng, công nghệ định tuyến ứng dụng một vài công
nghệ đặc trƣng riêng của WSN nhƣ phƣơng pháp tập hợp dữ liệu, xử lý nội bộ
Footer Page 24 of 126.

Số hóa bởi Trung tâm Học liệu

/>

Header Page 25 of 126.

15

mạng, tạo nhóm, phân cấp chức năng cho các điểm nút khác nhau…
Công nghệ định tuyến tìm kiếm sự trung hòa giữa những giải pháp đơn giản
và những giải pháp có tính phức tạp nhất định. Ngay cả trong những phƣơng
pháp khá tinh vi, trong những mạng có phạm vi rộng và các tin nhắn ngắn,
việc định tuyến vẫn tiêu thụ khá nhiều tài nguyên nhƣ băng thông và năng
lƣợng, đôi khi gây tắc nghẽn đƣờng truyền. Tồi tệ hơn, khi các yếu tố này kết
hợp lại có thể làm giảm hiệu suất, lƣu lƣợng của đƣờng truyền, và làm tăng độ
trễ.
1.5. Tổng quan về Bảng băm phân tán
1.5.1. Bảng băm (Hash Table)
Bảng băm là cấu trúc dữ liệu sử dụng hàm băm để truy vấn dữ liệu, các
dữ liệu đƣợc ánh xạ từ từ khóa đến các giá trị tƣơng ứng với khóa đó. Do đó
bảng băm là một mảng kết hợp và các hàm băm đƣợc sử dụng để băm các giá