S húa bi Trung tõm Hc liu
đạ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
S húa bi Trung tõm Hc liu
đạ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


Nguyễn Thành Trung

Số hóa bởi Trung tâm Học liệu
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 Số hóa bởi Trung tâm Học liệu
MỤC LỤC
Ở 1
CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY VÀ 2
ĐỊNH TUYẾN SỬ DỤNG BẢNG BĂM PHÂN TÁN 2
1.1. Tổng quan về mạng cảm biến không dây -WSN 2
1.2 Cấu trúc của WSNs 5

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
2.2.5. Nhận xét về CHR 37
2.3 Kỹ thuật bảng băm phân tán dựa theo cấu trúc của mạng 39
2.3.1 Nghiên cứu về T-DHT 39
2.3.2 Cấu trúc mạng cảm biến theo định hƣớng bảng băm 40
2.3.3. Lƣu đồ kỹ thuật bảng băm phân tán dựa theocấu trúc mạng 43
2.3.4. Nhận xét về T-DHT 44
2.4. Kỹ thuật định tuyến dựa theo cấu trúc vòng ảo – VRR 45
2.4.1. Nghiên cứu về VRR 45
2.4.2. Định tuyến với VRR 47
2.4.3. Lƣu đồ kỹ thuật dựa theo cấu trúc vòng ảo 48
2.4.4. Nhận xét về kỹ thuật dựa theo cấu trúc vòng ảo 49
2.5. Kỹ thuật bảng băm theo vị trí địa lý – GHT (Goegraphic Hash Table) 50
2.5.1.Nghiên cứu về kỹ thuật bảng băm theo vị trí địa lý 50
2.5.2.GPSR 53
2.5.3. Home node và Home perimetter 55
Số hóa bởi Trung tâm Học liệu
2.5.4. Giao thức làm tƣơi chu vi mạng 56
2.5.5. Lƣu đồ kỹ thuật bảng băm theo vị trí địa lý 58
2.5.6. Đánh giá về kỹ thuật bảng băm theo vị trí địa lý 60
2.6. Đánh giá và so sánh tổng quan về các kỹ thuật định tuyến 60
CHƢƠNG 3: CÀI ĐẶT, THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ KỸ
THUẬT ĐỊNH TUYẾN DỰA TRÊN VỊ TRÍ ĐỊA LÝ 62


GPSR
Wireless Sensor Network
Distributed Hash Table
Goegrapphic Hash Table
Chord for Sensor
Network
Cell Hash Routting
Topology based
Distributed Hash Table
Virtual Ring Routting

Peer to peer
Data Store Center
Low-energy adaptive
clustering hierarchy
Analog to Digital
Converter
Greedy Perimetter
Statelees Routting
Mạng cảm biến không dây
Bảng băm phân tán
Bảng băm phân tán theo vị trí địa lý
Kỹ thuật Chord cho mạng cảm biến

Kỹ thuật định tuyến băm ô
Kỹ thuật định tuyến bảng băm phân
tán dựa theo cấu trúc mạng
Kỹ thuật định tuyến dựa theo cấu
trúc vòng ảo

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
Số hóa bởi Trung tâm Học liệu
Hình 3.2: Hiển thị số ID và liên kết giữa các nút trong mạng cảm biến. 67
Hình 3.3: Hiển thị phạm vi phủ sóng của các nút cảm biến. 67
Hình 3.4: Đánh giá về việc tiêu thụ năng lƣợng trong toàn mạng 68
Hình 3.5: Đánh giá về độ lớn trung bình của các đƣờng truyền định tuyến 68
Hình 3.6: Đánh giá độ chính xác ngay cả khi các nút mạng xảy ra mất liên kết hay di
động 68 1
Số hóa bởi Trung tâm Học liệu
Ở
Nhờ có sự tiến bộ trong lĩnh vực truyền thông vô tuyến, trong những
năm gần đây, mạng cảm biến không dây (WSN –Wireless Sensor Network)
với giá thành rẻ, mức tiêu thụ năng lƣợng thấp và đa chức năng đang rất đƣợc
chú ý trong lĩnh vực thông tin. Hiện nay, việc tập trung vào nghiên cứu, ứng
dụng mạng cảm biến không dây vào trong cuộc sống hàng ngày càng nhận
đƣợ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ạng cảm biến không dây là một trong những lĩnh vực công nghệ
thông tin mới và đang phát triển nhanh chóng, với nhiều ứng dụng trong nhiều
lĩnh vực khác nhau: điều khiển quá trình công nghiệp, bảo mật và giám sát,
cảm biến môi trƣờng, kiểm tra sức khỏe… Những nghiên cứu tổng quan nhất
của mạng cảm biến không dây đƣợc đề cập chi tiết tại [2] của những tài liệu
sử dụng trong luận văn.

Hình 1.1 Biểu tượng của mạng cảm biến
Mạng cảm biến không dây là mạng liên kết các nút với nhau nhờ sóng
radio. Nhƣng trong đó, mỗi nút mạng bao gồm đầy đủ các chức năng để cảm
nhận, thu thập, xử lý và truyền dữ liệu. Các nút mạng thƣờng là các thiết bị
3
Số hóa bởi Trung tâm Học liệu
đơ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ả.

Hình 1.2 Nút cảm biến không dây của Zolertia Z1
th
5
Số hóa bởi Trung tâm Học liệu
- –
1.
:
2x
.
3.6V
3V.
ngu 3.6V.
3V.
Với đề xuất sử dụng pin 2xAA khi tr
nghiệm.
1.2 Cấu trúc của WSNs
1.2.1 Cấu trúc một node mạng WSNs
Để xây dựng mạng cảm biến trƣớc hết phải chế tạo và phát triển các nút
cấu thành mạng với các cảm biến. Các nút này phải thỏa mãn một số yêu cầu
nhất định tùy theo ứng dụng. Chúng phải có kích thƣớc nhỏ, giá thành rẻ, hoạt
động hiệu quả về năng lƣợng, có các thiết bị cảm biến chính xác có thể cảm
nhận, thu thập các thông số môi trƣờng, có tính toán và có bộ nhớ đủ để lƣu
trữ,… Và quan trọng nhất đó là phải có khả năng thu phát sóng để truyền
thông với các nút lân cận. Mỗi nút cảm biến đƣợc cấu thành bởi 4 thành phần
6
Số hóa bởi Trung tâm Học liệu
cơ bản. Đó là: bộ cảm nhận (Sensing unit), bộ xử lý (Processing unit), bộ thu
phát (Transceiver unit) và bộ nguồn (Power unit). Ngoài ra có thể có thêm
những thành phần khác tùy vào từng ứng dụng cụ thể. Nhƣ là hệ thống định vị
(Location Finding System), bộ phát nguồn (Power Generator) và bộ phận di

ngang hàng và đồng nhất, có cùng hình dạng và chức năng. Các nút 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. Với
phạm vi truyền cố định, các nút gần sink hơn sẽ đảm bảo vai trò của bộ tiếp
sóng đối với một số lƣợng lớn nguồn. Giả thiết rằng tất cả các nguồn đều dùng
cùng một tần số để truyền dữ liệu, vì vậy có thể chia sẻ thời gian. Tuy nhiên
cách này chỉ có hiệu quả với điều kiện là có nguồn chia sẻ đơn lẻ, ví dụ nhƣ
thời gian, tần số…

Hình 1.4: Cấu trúc phẳng của một mạng cảm biến
8
Số hóa bởi Trung tâm Học liệu
1.2.2.2. Cấu trúc tầng
Trong cấu trúc tầng (tiered architacture), (hình 1.5 ) các cụm đƣợc tạo
ra giúp các tài nguyên trong cùng một cụm gửi dữ liệu single hay multihop
(tùy thuộc vào kích cỡ của cụm) đến một nút định sẵn, thƣờng gọi là nút chủ
(cluster head). Trong cấu trúc này các nút tạo thành một hệ thống cấp bậc mà
ở đó 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)
9
Số hóa bởi Trung tâm Học liệu
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

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)
PicoRadio (U. of California)

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.
12
Số hóa bởi Trung tâm Học liệu
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 (multi-
hop). 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
phạm vi lớn.
1.3.4. Tính bảo mật
Trong các ứng dụng của mạng cảm biến không dây thì tính bảo mật rất
quan trọng, đặc biệt là các ứng dụng trong quân sự. Không giống nhƣ các
mạng có dây rất khó có thể lấy đƣợc thông tin khi truyền đi giữa hai đối
tƣợng, khi truyền tín hiệu không dây đƣợc truyền đi trong không gian và có
thể đƣợc thu lại bởi bất kỳ ai. Những mối hiểm hoạ không chỉ là việc đánh cắp
thông tin mà còn ở chỗ những thông tin đó có thể bị chỉnh sửa và phát lại để
phía thu hoặc nhận có đƣợc thông tin không chính xác.
Nhƣ vậy bảo mật trong mạng cảm biến không dây cần đảm bảo các yếu
tố: dữ liệu đƣợc mã hoá, có mã xác thực và nhận dạng giữa ngƣời gửi và
ngƣời nhận. Việc này sẽ đƣợc thực hiện kết hợp giữa cả phần mềm và phần
cứng bằng việc mã hoá các tập tin, điều chỉnh các bit thông tin, thêm các bit
xác thực…
Các chức năng này sẽ làm tiêu tốn thêm tài nguyên của hệ thống về mặt
năng lƣợng và băng thông, tuy nhiên bảo mật là một yếu tố bắt buộc trong
truyền tin. Do vậy cần đạt đƣợc sự cân bằng giữa hai yếu tố này để đảm bảo

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
14
Số hóa bởi Trung tâm Học liệu
trên một phạm vi hẹp. Điều này đã hạn chế về năng lực tính toán cũng nhƣ
không gian lƣu trữ trên mỗi nút cảm biến.
1.4.3. Ảnh hưởng của nhiễu từ môi trường
Do trong mạng cảm biến không dây sử dụng đƣờng truyền vô tuyến nên
bị ảnh hƣởng bởi những can nhiễu bên ngoài, có thể bị mất mát hoặc sai lệch
thông tin khi truyền từ nút về trạm gốc.
1.4.4. Định tuyến trong WSNs
Định tuyến trong mạng không dây đã là đề tài nghiên cứu nóng hổi
trong nhiều năm gần đây. Công nghệ định tuyến khởi điểm từ ngành truyền
thông dữ liệu máy tính đã đƣợc khai thác những tiềm năng ứng dụng trong
mạng không dây, mang lại rất nhiều mô hình tự tổ chức và tự phục vụ trong
những kế hoạch thƣơng mại.
Nguyên nhân của hoạt động này là quá trình vận hành ổn định mà chỉ
cần thay đổi những điều kiện truyền dƣới sự kết hợp băng thông và năng
lƣợng đã hạn chế việc sử dụng các giao thức dựa trên IP và tạo nên những
thách thức mới cho kỹ thuật định tuyến WSN. Nhiệm vụ tìm kiếm và duy trì
các tuyến là không hề đơn giản do những giới hạn về năng lƣợng và những sự
thay đổi trạng thái tại các điểm nút (ngừng, tắc và các trở ngại khác) thƣờng
tạo nên những thay đổi đột ngột. Xây dựng và tạo nên những tuyến tự động
qua mạng đòi hỏi phải có những bộ xử lý điểm nút hiệu quả, dung lƣợng bộ
nhớ lớn và các bộ định tuyến phụ trợ, cũng nhƣ thời gian chờ của mạng đến
khi hình thành tuyến thay thế.
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.