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

http://lrc.tnu.edu.vn/


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

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01

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


http://lrc.tnu.edu.vn/


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

http://lrc.tnu.edu.vn/


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

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
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
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn/


WSN

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

DHT

Distributed Hash Table

Bảng băm phân tán

GHT

Goegrapphic Hash Table

Bảng băm phân tán theo vị trí địa lý

CSN

Chord for Sensor

Kỹ thuật Chord cho mạng cảm biến

Network
CHR

Cell Hash Routting

Kỹ thuật định tuyến băm ô



Low-energy adaptive

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

clustering hierarchy

ứng năng lƣợng thấp

Analog to Digital

Chuyển đổi tín hiệu tƣơng tự sang tín

Converter

hiệu số

Greedy Perimetter

Định tuyến theo phƣơng pháp tham

Statelees Routting

lam và chu vi

ADC

GPSR

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

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
http://lrc.tnu.edu.vn/


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

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

http://lrc.tnu.edu.vn/


1

Ở
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

phân tán vào việc định tuyến trong mạng cảm biến không dây nhằm giải quyết
những vấn đề về năng lượng, khả năng mở rộng, tra cứu, tìm kiếm dữ liệu…
Trong đó đáng quan tâm nhất là việc sử dụng năng lượng hiệu quả trong việc
định tuyến.
1.1. Tổng quan về mạng cảm biến không dây -WSN
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
Số hóa bởi Trung tâm Học liệu

http://lrc.tnu.edu.vn/


3

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ị
đơ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

cảm biến là việc làm đòi hỏi nhiều kỹ năng về chuyên ngành điện tử. Nhƣng
có một giải pháp mà gần đây đƣợc nhiều nhà phát triển quan tâm đó là sử
dụng những platform đã đƣợc xây dựng những nền tảng cơ bản sẵn có. Về mặt
phát triển, nó giúp cho nhà phát triển tiết kiệm khá nhiều về thời gian. Về mặt
kỹ thuật, đó là những thiết bị lập trình logic. Ngoài ra nó còn là nền tảng mã
nguồn mở (open-source electronics prototyping platform). Giống nhƣ một
chiếc máy tính để có thể giúp các nhà phát triển lập trình làm bất cứ việc gì
với định hƣớng mà họ quan tâm. Thêm vào đó là khả năng tƣơng tác với môi
trƣờng thông qua cảm biến điện tử nhƣ: nhiệt độ, ánh sáng, độ ẩm,
chuyển động,…
Zolertia là một trong số đó, chuyên về việc phát triển các thiết bị cảm
biến không dây. Trong đó Z1 là một trong những sản phẩm đáng đƣợc quan
tâm. Với mô đun không dây công suất thấp Z1 Platform đƣợc coi nhƣ một sản
phẩm chủ lực của công ty.

Hình 1.2 Nút cảm biến không dây của Zolertia Z1

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

http://lrc.tnu.edu.vn/


5

th

-

–


độ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
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
động (Mobilizer).

Hình 1.3 Các thành phần của một nút cảm ứng
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.
Số hóa bởi Trung tâm Học liệu

http://lrc.tnu.edu.vn/


7

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

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.

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

http://lrc.tnu.edu.vn/


9

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)
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,

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

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

http://lrc.tnu.edu.vn/


11

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.

chính cần đƣợc quan tâm. Để có thể đạt đƣợc mục tiêu này thì khi thiết kế cấu
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.
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
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
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn/


13


http://lrc.tnu.edu.vn/


14

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

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á
trị khóa trong các mảng giá trị tìm kiếm. Trong các hàm băm có kích thƣớc đủ
lớn thời gian trung bình cho mỗi lần tra cứu độc lập với số phần tử trong
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn/