Mạng không dây địa hình xấu thuật toán định tuyến và ứng dụng

  • 68 trang
  • file .pdf
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGÔ HỒNG SƠN
MẠNG KHÔNG DÂY ĐỊA HÌNH XẤU: THUẬT TOÁN
ĐỊNH TUYẾN VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
---    ---
NGÔ HỒNG SƠN
MẠNG KHÔNG DÂY ĐỊA HÌNH XẤU: THUẬT TOÁN
ĐỊNH TUYẾN VÀ ỨNG DỤNG
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Trần Hồng Quân
HÀ NỘI - 2010
1
MỤC LỤC
DANH MỤC HÌNH .......................................................................................................3
BẢNG CÁC TỪ VIẾT TẮT .........................................................................................4
CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN VÔ TUYẾN (WSN) ............5
1.1. Giới thiệu chung ...............................................................................................5
1.2. Mạng Ad hoc [11] .............................................................................................6
1.3. Mạng cảm biến vô tuyến (Wireless Sensor Network) [1]-[2]-[9]-[11] .........8
1.3.1. Nút cảm biến trong mạng cảm biến vô tuyến [6] ...................................8
1.3.2. Đặc tính của mạng cảm biến vô tuyến [5]-[6] .......................................10
1.3.3. Một số chuẩn mạng cảm biến vô tuyến [1] ...........................................13
1.3.4. Ứng dụng của mạng cảm biến vô tuyến [2] ..........................................13
1.4. Tóm tắt chƣơng ..............................................................................................14
CHƢƠNG 2: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN VÔ TUYẾN ............15
2.1. Giao thức định tuyến [5]-[6]-[10]-[13]..........................................................15
2.1.1. Các giao thức định tuyến dựa trên cấu trúc mạng [5]-[6] ...................17
2.1.1.1. Định tuyến các mạng phẳng ............................................................17
2.1.1.2. Định tuyến các mạng phân cấp [6] .................................................29
2.1.1.3. Định tuyến dựa trên vị trí [6] ..........................................................33
2.1.2. Định tuyến dựa trên thao tác giao thức [6] ...........................................36
2.1.2.1. Các giao thức định tuyến đa đƣờng ................................................36
2.1.2.2. Định tuyến dựa vào truy vấn ...........................................................36
2.1.2.3. Các giao thức định tuyến dựa trên sự điều chỉnh .........................36
2.1.2.4. Định tuyến dựa trên chất lƣợng dịch vụ (QoS) .............................36
2.1.2.5. Định tuyến coherent và non-coherent ............................................37
2.2. Thuật toán định tuyến [8]-[9]........................................................................38
2.2.1. Cơ bản về mạng và đồ thị .......................................................................38
2
2.2.1.1. Cây lan tỏa tối thiểu (MST – Minimum Spanning Tree) .............38
2.2.1.2. Cây đƣờng đi ngắn nhất (SPT – Shortest Path Tree) ...................38
2.2.2. Một số thuật toán cây lan tỏa tối thiểu ..................................................39
2.2.2.1. Thuật toán Prim ...............................................................................39
2.2.2.2. Thuật toán Bor vka .........................................................................40
2.2.2.3. Thuật toán Kruskal ..........................................................................41
2.2.3. Một số thuật toán cây đƣờng đi ngắn nhất ...........................................43
2.2.3.1. Thuật toán Dijkstra ..........................................................................43
2.2.3.2. Thuật toán Ford-Bellman ................................................................44
2.2.4. Các thuật toán phân tán .........................................................................47
2.2.4.1. Thuật toán Ford-Bellman phân tán ................................................47
2.2.4.2. Thuật toán MST phân tán ...............................................................47
2.2.4.3. Thuật toán cây lan tỏa......................................................................48
2.2.4.4. Thuật toán cặp (Định vị hóa theo thuật toán Prim và Dijkstra) .48
2.3. Tóm tắt chƣơng ..............................................................................................51
CHƢƠNG 3: ĐỊNH TUYẾN ĐỊA HÌNH XẤU – MÔ PHỎNG VÀ ĐÁNH GIÁ .52
3.1. Sơ lƣợc về bộ mô phỏng mạng NS-2 [4] .......................................................52
3.2. Thực hiện mô phỏng [7]-[14]-[15] ................................................................55
3.3. Đánh giá [15] ..................................................................................................58
3.4. Tóm tắt chƣơng ..............................................................................................64
TÀI LIỆU THAM KHẢO...........................................................................................66
3
DANH MỤC HÌNH
Hình 1: Mô hình mạng không dây Ad hoc .......................................................................6
Hình 2: Mạng Ad hoc điển hình ......................................................................................6
Hình 3: Mạng cảm biến vô tuyến ....................................................................................8
Hình 4: Cấu trúc của một nút cảm biến ..........................................................................9
Hình 6: Các mô hình RandomWalk, Flooding, Gossiping ............................................17
Hình 7: Hoạt động của SPIN.........................................................................................21
Hình 8: Hoạt động của Directed Diffusion ...................................................................23
Hình 9: Một ví dụ về Directed Diffusion trong mạng cảm biến ....................................24
Hình 10: Hoạt động cơ bản của Directed Diffusion .....................................................25
Hình 13: Minh họa việc thiết lập liên kết ......................................................................49
Hình 15: Mô hình tổng quan bộ mô phỏng NS-2 ..........................................................52
Hình 16: C++ và OTcl, hai thành phần đối ngẫu.........................................................53
Hình 17: Kiến trúc của NS-2 .........................................................................................54
Hình 18: Các hố mạng là các nút mạng “chết” ............................................................56
Hình 20: Mô phỏng 500 nút mạng WSN .......................................................................58
4
BẢNG CÁC TỪ VIẾT TẮT
AODV Adhoc On-demand Distance Vector
DSDV Destination Sequenced Distance Vector
GAF Geographic Adaptive Fidelity
GEAR Geographic Energy Aware Routing
LAN Local Area Network
LEACH Low Energy Adaptive Clustering Hierarchy
MAC Medium Access Control
MCFA Minimum Cost Forwarding Algorithm
MST Minimum Spanning Tree
PEGASIS Power-Efficient Gathering in Sensor Information Systems
SAR Sequential Assignment Routing
SPIN Sensor Protocols for Information via Negotiation
SPT Shortest Path Tree
WSN Wireless Sensor Network
5
CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN VÔ TUYẾN (WSN)
Nội dung chương bao gồm những phần chính sau:
- Giới thiệu chung về mạng không dây
- Giới thiệu về mạng Adhoc
- Giới thiệu về mạng cảm biến vô tuyến, các đặc điểm cũng như ứng dụng của
mạng cảm biến vô tuyến
1.1. Giới thiệu chung
Cùng với sự phát triển của khoa học công nghệ, công nghệ thông tin đang ngày
càng được ứng dụng ở hầu hết các lĩnh vực trong cuộc sống xã hội như kinh tế, giáo
dục, xây dựng, y học,... việc ứng dụng công nghệ thông tin vào giải quyết các công
việc thì Internet ngày càng khẳng định được vị trí quan trọng của mình trong cuộc
sống xã hội thời hiện đại. Khi cuộc sống con người ngày càng phát triển thì nhu cầu
trao đổi thông tin của con người ngày càng cao. Con người muốn mình có thể được kết
nối với thế giới vào bất cứ lúc nào, từ bất cứ nơi đâu mà không cần phải có đường nối.
Đó chính là lý do mà mạng không dây ra đời. Ngày nay, chúng ta có thể thấy được sự
hiện diện của mạng vô tuyến ở nhiều nơi như trong các tòa nhà, các công ty, bệnh
viện, trường học hay thậm chí là các quán cà phê. Cùng với sự phát triển của mạng có
dây truyền thống, mạng vô tuyến cũng đang có những bước phát triển nhanh chóng
nhằm đáp ứng nhu cầu trao đổi thông tin và truyền thông của con người một cách tốt
nhất.
Khi mà mạng vô tuyến đang ngày càng được quan tâm, đầu tư nghiên cứu và
phát triển thì ngày càng có nhiều mô hình, kiến trúc mạng được đề xuất bởi các nhà
khoa học, các hội nghị.
Mạng Ad hoc (viết tắt là MANETs – Mobile Adhoc Networks) là một loại
mạng vô tuyến điển hình không phụ thuộc vào cơ sở hạ tầng. Trong đó mạng cảm biến
vô tuyến (WSNs – Wireless Sensor Networks) là một dạng của mạng Ad hoc đang rất
được quan tâm nghiên cứu hiện nay. Việc các mạng vô tuyến ít phụ thuộc vào cơ sở hạ
tầng là một điều rất thuận lợi nhưng lại có những vấn đề khác đặt ra như tốc độ truyền
thông không cao, mô hình mạng không ổn định như mạng có dây truyền thống do các
nút mạng hay di chuyển, năng lượng cung cấp cho các nút mạng thường chủ yếu là
pin... Do đó, cùng với vấn đề bảo mật của mạng không dây thì vấn đề định tuyến trong
mạng vô tuyến cũng là vấn đề vô cùng quan trọng. Nó quyết định rất lớn đến hiệu
năng hoạt động của toàn hệ thống mạng.
6
1.2. Mạng Ad hoc [11]
Mạng Ad hoc là một mạng vô tuyến phi tập trung hóa (phân tán). Một mạng là
Ad hoc bởi vì nó không dựa trên một cơ sở hạ tầng sẵn có, chẳng hạn như các router
trong mạng có dây hay các access point trong mạng không dây được quản trị (cơ sở hạ
tầng). Thay vào đó, mỗi nút tham gia vào việc định tuyến bằng cách chuyển tiếp dữ
liệu tới các nút khác, và vì vậy việc xác định các nút nào chuyển tiếp dữ liệu được thực
hiện một cách động dựa trên sự kết nối của mạng.
Mạng Ad hoc sớm nhất là các mạng radio gói (PRNETs) từ những năm 1970, được
bảo trợ bởi DARPA sau dự án ALOHAnet.
Hình 1: Mô hình mạng không dây Ad hoc
Hình 2: Mạng Ad hoc điển hình
Ứng dụng của mạng Ad hoc
Sự phi tập trung của các mạng Ad hoc làm cho chúng thích hợp với rất nhiều
ứng dụng mà các nút trung tâm không thể thỏa mãn, và có thể phát triển sự mở rộng
của mạng Ad hoc giống các mạng không dây được quản trị.
- Đáp ứng nhu cầu truyền thông mang tính chất tạm thời: Ở tại địa điểm trong
một khoảng thời gian nhất định, giống như trong một lớp học, một cuộc hội thảo hay
một cuộc họp, ... việc thiết lập một mạng mang tính chất tạm thời để truyền thông với
7
nhau chỉ diễn ra trong một khoảng thời gian ngắn. Nếu chúng ta thiết lập một mạng có
cơ sở hạ tầng, dù là mạng không dây vẫn rất tốn kém tiền bạc cũng như nhân lực, vật
lực, thời gian. Do đó, mạng Ad hoc được coi là giải pháp tốt nhất cho những tình
huống như thế này.
- Hỗ trợ khi xảy ra các thiên tai, hỏa hoạn và dịch họa: Khi xảy ra các thiên tai
như hỏa hoạn, động đất, cháy rừng ở một nơi nào đó, cơ sở hạ tầng ở đó như đường
dây, các máy trạm, máy chủ, ... có thể bị phá hủy dẫn đến hệ thống mạng bị tê liệt là
hoàn toàn khó tránh khỏi. Vì thế, việc thiết lập nhanh chóng một mạng cần thời gian
ngắn mà lại có độ tin cậy cao và không cần cơ sở hạ tầng để đáp ứng truyền thông,
nhằm giúp khắc phục, giảm tổn thất sau thiên tai, hỏa hoạn là cần thiết. Khi đó mạng
Ad hoc là một lựa chọn phù hợp nhất cho những tình huống như vậy.
- Đáp ứng truyền thông tại những nơi xa trung tâm, các vùng sâu, vùng xa: tại
những nơi xa trung tâm thành phố, nơi có dân cư thưa thớt như ở vùng sâu, vùng xa,
việc thiết lập các hệ thống mạng có cơ sở hạ tầng là rất khó khăn và tốn kém. Vậy ở
những nơi này, giải pháp được đưa ra là sử dụng các mạng vệ tinh hoặc mạng Ad Hoc.
- Tính hiệu quả: Trong một số ứng dụng nào đó, nếu sử dụng dịch vụ mạng có
cơ sở hạ tầng có thể không có hiệu quả cao bằng việc dùng mạng Ad hoc. Ví dụ như
với một mạng có cơ sở hạ tầng, do được điều khiển bởi một điểm truy cập mạng lên
các nút mạng muốn truyền thông với nhau đều phải thông qua nó. Ngay cả khi hai nút
mạng ở gần nhau, chúng cũng không thể trực tiếp truyền thông với nhau mà phải
chuyển tiếp qua một điểm truy cập trung tâm(Acess Point). Điều đó gây ra một sự lãng
phí thời gian và băng thông mạng. Trong khi đó, nếu sử dụng mạng Ad Hoc việc
truyền thông giữa hai nút mạng đó lại trở lên vô cùng dễ dàng và nhanh chóng. Hai nút
mạng gần nhau có thể truyền thông trực tiếp với nhau mà không cần phải thông qua
thiết bị trung gian nào khác.
Các mạng Ad hoc có thể được chia lớp cụ thể hơn theo ứng dụng của chúng:
 Mạng ad hoc di động (mobile ad hoc networks - MANETs)
 Mạng vô tuyến lưới (wireless mesh networks)
 Mạng cảm biến vô tuyến (wireless sensor networks)
Các yêu cầu kỹ thuật:
Một mạng Ad hoc được tạo nên từ nhiều “nút” được liên kết bởi “các liên kết”
Các liên kết bị ảnh hưởng bởi các tài nguyên của các nút (chẳng hạn như nguồn năng
lượng sẵn có, công suất phát, công suất tính toán và bộ nhớ) và bởi các thuộc tính hành
vi (tính đáng tin cậy và tính chất đáng tin cậy), hay bởi các thuộc tính liên kết (chẳng
hạn nhiễu/méo dọc theo khoảng cách, độ dài của liên kết và mất tín hiệu, nhiễu/méo và
ồn)…
8
1.3. Mạng cảm biến vô tuyến (Wireless Sensor Network) [1]-[2]-[9]-[11]
Mạng cảm biến vô tuyến (WSN) bao gồm các bộ cảm biến tự trị được phân tán
trong không gian để cùng theo dõi các điều kiện tự nhiên hay môi trường, chẳng hạn
như nhiệt độ, âm thanh, rung động, áp suất, chuyển động hay sự ô nhiễm. Sự phát triển
của các mạng cảm biến vô tuyến được thúc đẩy bởi các ứng dụng quân sự như là việc
theo dõi chiến trường. Mạng cảm biến vô tuyến có thể hiểu đơn giản là mạng liên kết
các nút với nhau bằng kết nối sóng vô tuyến (RF connection) trong đó 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ố một cách không có hệ thống (non-topology) trên một diện tích rộng (phạm vi
hoạt động rộng), sử dụng nguồn năng lượng hạn chế (pin), có thời gian hoạt động lâu
dài (vài tháng đến vài năm) và có thể hoạt động trong môi trường khắc nghiệt (chất
độc, ô nhiễm, nhiệt độ ...).Chúng được sử dụng trong rất nhiều vùng ứng dụng công
nghiệp cũng như dân cư, bao gồm quá trình điều khiển và giám sát công nghiệp, theo
dõi sức khỏe, theo dõi môi trường, các ứng dụng chăm sóc sức khỏe và điều khiển giao
thông.
Một mạng cảm biến thường tạo nên một mạng Ad hoc không dây, có nghĩa là
mỗi bộ cảm biến hỗ trợ một thuật toán định tuyến multi-hop (một vài nút có thể
chuyển tiếp các gói dữ liệu tới trung tâm (base station)).
Trong khoa học máy tính và viễn thông, các mạng cảm biến vô tuyến là một
lĩnh vực được quan tâm nghiên cứu với một số lượng các cuộc hội thảo và hội nghị
diễn ra hàng năm.
Hình 3: Mạng cảm biến vô tuyến
1.3.1. Nút cảm biến trong mạng cảm biến vô tuyến [6]
Cấu tạo của nút cảm biến như sau:
9
Hình 4: Cấu trúc của một nút cảm biến
Mỗi nút cảm biến được cấu thành bởi 4 thành phần cơ bản như ở hình 2:
- đơn vị cảm biến (a sensing unit)
- đơn vị xử lý (a processing unit)
- đơn vị truyền dẫn (a transceiver unit)
- bộ nguồn (a power unit).
Ngoài ra có thể có thêm những thành phần khác tùy thuộc vào từng ứng dụng
như là hệ thống định vị (location finding system), bộ phát nguồn (power generator) và
bộ phận di động (mobilizer).
Các đơn vị cảm biến (sensing units) bao gồm cảm biến và bộ chuyển đổi tương
tự-số. 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 bộ cảm
biến được chuyển sang tín hiệu số bằng bộ ADC, sau đó được đưa vào bộ xử lý.
Đơn vị xử lý thường được kết hợp với bộ lưu trữ nhỏ (storage unit), quyết định
các thủ tục làm 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.
Một trong số các phần quan trọng nhất của một nút mạng cảm biến là bộ nguồn.
Các bộ nguồn thường được hỗ trợ bởi các bộ phận lọc như là tế bào năng lượng mặt
trời. Ngoài ra cũng có những thành phần phụ khác phụ thuộc vào từng ứng dụng. 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ó độ
chính xác cao về vị trí. Các bộ phận di động đôi lúc cần phải 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. 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 module. Ngoài kích cỡ ra các nút cảm biến còn một
10
số ràng buộc nghiêm ngặt khác, như là phải tiêu thụ rất ít năng lượng, hoạt động ở mật
độ cao, có giá thành thấp, có thể tự hoạt động, và thích biến với sự biến đổi của môi
trường.
1.3.2. Đặc tính của mạng cảm biến vô tuyến [5]-[6]
Mỗi nút trong mạng WSN thông thường bao gồm 2 phần: phần cảm biến
(sensor) hoặc điều khiển và phần giao tiếp vô tuyến (RF transceiver). Do số lượng nút
trong WSN là lớn và không cần các hoạt động bảo trì, nên yêu cầu thông thường đối
với một nút mạng là giá thành thấp (10 - 50 USD) và kích thước nhỏ gọn ( diện tích bề
mặt vài đến vài chục cm2).
Mạng phải cho phép hai nút bất kỳ trao đổi với nhau thường là thông qua các
nút khác – các nút chuyển tiếp thông tin. Một “đường đi” là một chuỗi các liên kết mà
kết nối hai nút đó. Thông thường, có nhiều đường đi giữa hai nút bất kỳ. Các nút
thường bị giới hạn bởi công suất phát (phạm vi phát) và các nguồn năng lượng sẵn có.
Công suất phát thường tiêu hao phần lớn năng lượng ở mỗi nút. Phụ thuộc vào luật
bình phương nghịch đảo, nó đòi hỏi năng lượng hiệu quả nhiều hơn để chuyển tiếp
thông tin qua một mạng thông qua nhiều nút.
Các nút mạng thường có chức năng cảm biến (nút cảm biến): cảm ứng, quan sát
môi trường xung quanh như: nhiệt độ, độ ẩm, ánh sáng... theo dõi hay định vị các mục
tiêu cố định hoặc di động ... Các nút giao tiếp Ad hoc với nhau và truyền dữ liệu về
trung tâm một cách gián tiếp bằng kỹ thuật multi-hop.
Lưu lượng dữ liệu lưu thông trong WSN là thấp và không liên tục (không hẳn
với các ứng dụng dò vết và định vị). Do vậy để tiết kiệm năng lượng, các nút cảm biến
thường có nhiều trạng thái hoạt động (active mode) và trạng thái nghỉ (sleep mode)
khác nhau. Thông thường thời gian một nút ở trạng thái nghỉ lớn hơn ở trạng thái hoạt
động rất nhiều.
Như vậy, đặc trưng cơ bản nhất để phân biệt một mạng cảm biến và một mạng
vô tuyến khác chính là giá thành, mật độ nút mạng, phạm vi hoạt động, topo mạng, lưu
lượng dữ liệu, năng lượng tiêu thụ và thời gian ở trạng thái hoạt động.
Đặc điểm của mạng cảm biến
Như trên ta đã biết đặc điểm của mạng cảm biến là bao gồm một số lượng lớn
các nút cảm biến, các nút cảm biến có giới hạn và ràng buộc về tài nguyên đặc biệt là
năng lượng rất khắt khe. Do đó, cấu trúc mạng mới có đặc điểm rất khác với các mạng
truyền thống. Sau đây ta sẽ phân tích một số đặc điểm nổi bật trong mạng cảm biến
như sau:
- Khả năng chịu lỗi (fault tolerance): Một số các nút cảm biến có thể không
hoạt động nữa do thiếu năng lượng, do những hư hỏng vật lý hoặc do ảnh
hưởng của môi trường. Khả năng chịu lỗi thể hiện ở việc mạng vẫn hoạt động
11
bình thường, duy trì những chức năng của nó ngay cả khi một số nút mạng
không hoạt động.
- Khả năng mở rộng: Khi nghiên cứu một hiện tượng, số lượng các nút cảm
biến được triển khai có thể đến hàng trăm nghìn nút, phụ thuộc vào từng ứng
dụng con số này có thể vượt quá hàng triệu. Do đó cấu trúc mạng mới phải có
khả năng mở rộng để có thể làm việc với số lượng lớn các nút này.
- Giá thành sản xuất : Vì các mạng cảm biến bao gồm một số lượng lớn các nút
cảm biến nên chi phí của mỗi nút rất quan trọng trong việc điều chỉnh chi phí
của toàn mạng. Nếu chi phí của toàn mạng đắt hơn việc triển khai bộ cảm biến
theo kiểu truyền thống, như vậy mạng không có giá thành hợp lý. Do vậy, chi
phí của mỗi nút cảm biến phải giữ ở mức thấp.
- Ràng buộc về phần cứng : Ví số lượng các nút trong mạng rất nhiều nên các
nút cảm biến cần phải có các ràng buộc về phần cứng như sau : Kích thước phải
nhỏ, tiêu thụ năng lượng thấp, có khả nằng hoạt động ở những nơi có mật độ
cao, chi phí sản xuất thấp, có khả năng tự trị và hoạt động không cần có người
kiểm soát, thích nghi với môi trường.
- Môi trường hoạt động: Các nút cảm biến được thiết lập dày đặc, rất gần hoặc
trực tiếp bên trong các hiện tượng để quan sát. Vì thế, chúng thường làm việc
mà không cần giám sát ở những vùng xa xôi. Chúng có thể làm việc ở bên trong
các máy móc lớn, ở dưới đáy biển, hoặc trong những vùng ô nhiễm hóa học
hoặc sinh học, ở gia đình hoặc những tòa nhà lớn.
- Phương tiện truyền dẫn : Ở những mạng cảm biến multihop, các nút được kết
nối bằng những phương tiện không dây. Các đường kết nối này có thể tạo nên
bởi sóng vô tuyến, hồng ngoại hoặc những phương tiện quang học. Để thiết lập
sự hoạt động thống nhất của những mạng này, các phương tiện truyền dẫn phải
được chọn phải phù hợp trên toàn thế giới. Hiện tại nhiều phần cứng của các
nút cảm biến dựa vào thiết kế mạch RF. Những thiết bị cảm biến năng lượng
thấp dùng bộ thu phát vô tuyến 1 kênh RF hoạt động ở tần số 916MHz. Một
cách khác mà các nút trong mạng giao tiếp với nhau là bằng hồng ngoại. Thiết
kế máy thu phát vô tuyến dùng hồng ngoại thì giá thành rẻ và dễ dàng hơn. Cả
hai loại hồng ngoại và quang đều yêu cầu bộ phát và thu nằm trong phạm vi
nhìn thấy, tức là có thể truyền ánh sáng cho nhau được.
- Cấu hình mạng cảm biến (network topology): Trong mạng cảm biến, hàng
trăm đến hàng nghìn nút được triển khai trên trường cảm biến. Chúng được
triển khai trong vòng hàng chục feet của mỗi nút. Mật độ các nút có thể lên tới
20 nút/m3. Do số lượng các nút cảm biến rất lớn nên cần phải thiết lâp một cấu
hình ổn định. Chúng ta có thể kiểm tra các vấn đề liên quan đến việc duy trì và
thay đổi cấu hình ở 3 pha sau:
+ Pha tiền triển khai và triển khai: các nút cảm biến có thể đặt ngẫu
nhiên hoặc xếp theo trật tự trên trường cảm biến. Chúng có thể được triển
12
khai bằng cách thả từ máy bay xuống, tên lửa, hoặc có thể do con người hoặc
robot đặt từng cái một.
+ Pha hậu triển khai: sau khi triển khai, những sự thay đổi cấu hình
phụ thuộc vào việc thay đổi vị trí các nút cảm biến, khả năng đạt trạng thái
không kết nối (phụ thuộc vào nhiễu, việc di chuyển các vật cản...), năng lượng
thích hợp, những sự cố, và nhiệm vụ cụ thể.
+ Pha triển khai lại: Sau khi triển khai cấu hình, ta vẫn có thể thêm
vào các nút cảm biến khác để thay thế các nút gặp sự cố hoặc tùy thuộc vào
sự thay đổi chức năng.
- Sự tiêu thụ năng lượng : Các nút cảm biến không dây, có thể coi là một thiết
bị vi điện tử chỉ có thểđược trang bị nguồn năng lượng giới hạn (<0,5Ah, 1,2V).
Trong một số ứng dụng, việc bổ sung nguồn năng lượng không thể thực hiện
được. Vì thế khoảng thời gian sống của các nút cảm biến phụ thuộc mạnh vào
thời gian sống của pin. Ở mạng cảm biến multi-hop Ad hoc, mỗi một nút đóng
một vai trò kép: vừa khởi tạo vừa định tuyến dữ liệu. Sự trục trặc của một vài
nút cảm biến có thể gây ra những thay đổi đáng kể trong cấu hình và yêu cầu
định tuyến lại các gói và tổ chức lại mạng. Vì vậy, việc duy trì và quản lý
nguồn năng lượng đóng một vai trò quan trọng. Đó là lý do vì sao mà hiện nay
người ta đang tập trung nghiên cứu về các giải thuật và giao thức để thiết kế
nguồn cho mạng cảm biến. Nhiệm vụ chính của các nút cảm biến trong trường
cảm biến là phát hiện ra các sự kiện, thực hiện xử lý dữ liệu cục bộ nhanh
chóng, và sau đó truyền dữ liệu đi. Vì thế sự tiêu thụ năng lượng được chia ra
làm 3 vùng: cảm nhận (sensing), giao tiếp (communicating), và xử lý dữ liệu
(data processing).
Thiết kế trong mạng cảm biến
Do giới hạn về nguồn năng lượng cung cấp (pin...), giá thành và yêu cầu hoạt
động trong một thời gian dài, nên vấn đề tiêu thụ năng lượng là tiêu chí thiết kế quan
trọng nhất trong mạng cảm biến:
- Lớp vật lý: tương đối đơn giản, gọn nhẹ do ràng buộc về kích thước và khả
năng tính toán của nút. Kỹ thuật điều chế tín hiệu số: O-QPSK, FSK cải thiện hiệu suất
bộ khuếch đại công suất. Các kỹ thuật mã hóa sửa sai phức tạp như Turbo Codes,
LDPC không được sử dụng, kỹ thuật trải phổ được sử dụng để cải thiện SNR ở thiết bị
thu và giảm tác động của fading của kênh truyền...
- Lớp MAC: kỹ thuật đa truy cập TDMA hoặc CSMA-CA hiệu chỉnh với mục
đích giảm năng lượng tiêu thụ.
- Lớp định tuyến: Định tuyến "nhận biết năng lượng", định tuyến địa lý, ...
WSN thường được triển khai trên một phạm vi rộng, số lượng nút mạng lớn và
được phân bố một cách tương đối ngẫu nhiên, các nút mạng có thể di chuyển làm thay
13
đổi sơ đồ mạng... do vậy WSN đòi hỏi một hình trạng mạng linh động (ad-hoc, grid,
star...) và các nút mạng có khả năng tự điều chỉnh, tự cấu hình (auto-reconfigurable).
Trong một số WSN thông dụng (giám sát, cảm biến, môi trường ...) địa chỉ ID
các nút chính là vị trí địa lý và giao thức định tuyến dựa vào vị trí địa lý này gọi là
Geography Routing Protocol (GRT). Đối với mạng với số lượng lớn các nút, sơ đồ
mạng không ổn định ... GRT giúp đơn giản hóa giải thuật tìm đường, giảm dữ liệu
bảng định tuyến (routing table) lưu trữ tại các nút. GRT phù hợp với các WSN cố định,
tuy nhiên đối với các nút di động (địa chỉ ID nút thay đổi) giao thức định tuyến trở nên
phức tạp và không ổn định.
Việc cluster hoá: phân chia mạng diện rộng (hàng trăm, hàng nghìn nút) thành
các clusters để ổn định hình trạng của mạng, đơn giản hóa giải thuật định tuyến, giảm
đụng độ (collission) khi truy cập vào kênh truyền (medium access) nên giảm được
năng lượng tiêu thụ , đơn giản hóa việc quản lý mạng và cấp phát địa chỉ cho từng nút
mạng (theo cluster).
Do giới hạn khả năng tính toán của từng nút mạng cũng như để tiết kiệm năng
lượng, WSN thường sử dụng các phương pháp tính toán và xử lý tín hiệu phi tập trung
(giảm tải cho nút gần hết năng lượng) hoặc gửi dữ liệu cần tính toán cho các trạm cơ
sở (có khả năng xử lý tín hiệu mạnh và ít ràng buộc về tiêu thụ năng lượng).
1.3.3. Một số chuẩn mạng cảm biến vô tuyến [1]
Do phạm vi ứng dụng cua WSN rất rộng lớn, tính chất, đặc trưng của mạng phụ
thuộc vào ứng dụng triển khai 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, Routing, synchronisation ...) phù
hợp cho từng ứng dụng cụ thể dựa trên các 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. of Hawaii)
- PRNET system (U.S. Defense)
- WINS (U. of California)
- PicoRadio (U. of California)
- MicroAMPS (M.I.T)
- MANET (Mobile ad-hoc Network)
- Zigbee: dựa trên physical layer và MAC layer của chuẩn WPAN 802.15.4
1.3.4. Ứng dụng của mạng cảm biến vô tuyến [2]
WSN được ứng dụng đầu tiên trong các lĩnh vực quân sự. Cùng với sự phát
triển của ngành công nghiệp điều khiển tự động, robot, thiết bị thông minh, môi
trường, y tế ... WSN ngày càng được sử dụng nhiều trong hoạt động công nghiệp và
dân dụng. Một số ứng dụng cơ bản của WSN:
14
- Cảm biến môi trường (quân sự: phát hiện mìn, chất độc, dịch chuyển quân
địch...; công nghiệp: hệ thống chiếu sáng, độ ẩm, phòng cháy, chống rò rỉ...;
dân dụng: hệ thống điều hòa nhiệt độ, chiếu sáng...)
- Điều khiển (quân sự: kích hoạt thiết bị, vũ khí quân sự...; công nghiệp: điều
khiển tự động các thiết bị, robot... )
- Theo dõi, giám sát, định vị (quân sự: định vị, theo dõi sự dịch chuyển thiết bị,
quân đội...)
- Môi trường (giám sát lũ lụt, bão, gió, mưa..., phát hiện ô nhiễm, chất thải...)
- Y tế (định vị, theo dõi bệnh nhân, hệ thống báo động khẩn cấp...)
- Hệ thống giao thông thông minh: giao tiếp giữa biển báo và phương tiện giao
thông, hệ thống điều tiết lưu thông công cộng, hệ thống báo hiệu tai nạn, kẹt xe
... hệ thống định vị phương, trợ giúp điều khiển tự động phương tiện giao
thông...
- Gia đình (nhà thông minh: hệ thống cảm biến, giao tiếp và điều khiển các thiết
bị thông minh...)
WSN tạo ra môi trường giao tiếp giữa các thiết bị thông minh, giữa các thiết bị thông
minh và con người và giao tiếp giữa các thiết bị thông minh và các hệ thống viễn
thông khác (hệ thống thông tin di động, Internet...)
Hầu hết các mạng WSN đều hoạt động ở tầm tần số ISM 2.4 Ghz, trừ DASH7.
Lớp vật lý và liên kết dữ liệu theo chuẩn 802.15.4 của IEEE, trừ DASH7.
Một phần trên của lớp 2 trở lên sẽ thay đổi tùy theo chuẩn. Một chuẩn khá "tai
tiếng" là zigbee. Một chuẩn mới đang được nghiên cứu là WirelessHART, đây là một
chuẩn mở, có thêm tính năng đồng bộ thời gian ở lớp 2. Bên cạnh đó DASH7, chuẩn
của ISO, cũng là 1 vấn đề đáng quan tâm.
Một số thông số của 802.15.4: Tốc độ truyền dữ liệu tại 2.4Ghz là 250kbps.
Truy cập TDMA. Khi không cần truyền dữ liệu thì chuyển sang trạng thái rỗi nhờ đó
với 2 cục pin AA thời gian sử dụng có thể lên đến 2 năm.
Một số thông số của DASH7: Hoạt động tại tần số 433 Mhz, thời gian sử dụng
với 2 cục pin AA lên đến 10 năm, tầm phủ sóng 2km...
1.4. Tóm tắt chƣơng
Chương 1 của luận văn đã giới thiệu khái quát về mạng vô tuyến cũng như mạng
con của nó là mạng cảm biến vô tuyến (WSNs) và vấn đề định tuyến trong mạng WSN
là vấn đề đáng quan tâm để định hướng cho việc nghiên cứu trong các chương tiếp
theo.
15
CHƢƠNG 2: ĐỊNH TUYẾN TRONG MẠNG CẢM BIẾN VÔ TUYẾN
Nội dung chương bao gồm những phần chính sau:
- Trình bày về các giao thức định tuyến trong mạng WSN
- Trình bày về các thuật toán định tuyến trong mạng WSN
2.1. Giao thức định tuyến [5]-[6]-[10]-[13]
Thông thường, việc định tuyến trong WSN có thể được chia thành định tuyến phẳng
(flat-based), phân cấp (hierarchical-based), và dựa trên vị trí (location-based) phụ
thuộc vào cấu trúc của mạng. Trong định tuyến phẳng, mọi nút thường được gán các
vai trò hay chức năng như nhau. Trong định tuyến phân cấp, các nút sẽ thực hiện các
vai trò khác nhau trong mạng. Trong định tuyến dựa trên vị trí, các vị trí của các nút
cảm biến được khai thác để định tuyến dữ liệu trong mạng.
Hơn nữa, các giao thức định tuyến này có thể được chia lớp thành các loại như: đa
đường (multipath-based), theo yêu cầu (query-based), thỏa thuận (negotiation-based),
chất lượng dịch vụ (QoS-based), hay chặt chẽ (coherent-based routing techniques) phụ
thuộc vào hoạt động của giao thức. Thêm vào đó, các giao thức định tuyến có thể được
chia thành ba loại là proactive, reactive và hybrid phụ thuộc vào nút nguồn tìm ra
đường tới đích như thế nào. Trong các giao thức proactive, mọi đường đi được tính
toán trước khi chúng thực sự được cần đến, trong khi đối với giao thức reactive, các
đường đi được tính toán theo yêu cầu. Các giao thức hybrid sử dụng một tổ hợp ý
tưởng của hai giao thức trên. Khi mọi nút cảm biến là tĩnh, việc sử dụng các giao thức
định tuyến điều khiển bằng bảng sẽ dễ dàng hơn là sử dụng các giao thức phản ứng.
Một lượng lớn năng lượng được sử dụng trong việc phát hiện và thiết lập đường đi của
các giao thức phản ứng. Các lớp giao thức định tuyến khác được gọi là các giao thức
định tuyến cộng tác (cooperative). Trong việc định tuyến cộng tác, các nút gửi dữ liệu
tới một nút trung tâm nơi mà dữ liệu có thể được kết tập lại và có thể được đưa tới việc
xử lý cao hơn, do đó chi phí định tuyến sẽ giảm và việc sử dụng năng lượng cũng
giảm. Nhiều giao thức khác trông cậy vào thông tin thời gian và thông tin vị trí. Hình
dưới đây mô tả sự phân lớp các giao thức định tuyến trong mạng cảm biến vô tuyến.
16
Các giao thức định tuyến trong mạng WSN
Cấu trúc mạng Thao tác giao thức
Định Định Định Định Định Định Định Định
tuyến tuyến tuyến tuyến tuyến tuyến tuyến tuyến
các các dựa dựa dựa dựa dựa dựa trên
mạng mạng vào vị trên trên đa trên trên sự liên
phẳng phân cấp trí sự đường truy QoS kết chặt
điều vấn chẽ
chỉnh
Hình 5: Sự phân lớp các giao thức định tuyến trong mạng cảm biến vô tuyến
Kiến trúc phẳng có một vài lợi ích bao gồm số lượng mào đầu tối thiểu để duy trì cơ sở
hạ tầng, và có khả năng khám phá ra nhiều đường giữa các nút truyền dẫn để chống lại
lỗi.
Đối với kiến trúc thứ hai là kiến trúc phân cấp theo cụm, lợi dụng cấu trúc của mạng
để đạt được hiệu quả về năng lượng, sự ổn định, sự mở rộng. Trong loại giao thức này
các nút mạng tự tổ chức thành các cụm trong đó một nút có mức năng lượng cao hơn
các nút khác và đóng vai trò là nút chủ. Nút chủ thực hiện phối hợp hoạt động trong
cụm và chuyển tiếp thông tin giữa các cụm với nhau. Việc tạo thành các cụm có khả
năng làm giảm tiêu thụ năng lượng và tăng thời gian sống của mạng.
Còn loại kiến trúc thứ ba sử dụng phương pháp trung tâm dữ liệu nhằm phân bố yêu
cầu (interest) bên trong mạng. Phương pháp này sử dụng thuộc tính dựa trên tên do đó
một nút nguồn truy vấn một thuộc tính của sự kiện/hiện tượng hơn là một nút riêng lẻ.
Một giao thức khác có thể truyền sự quan tâm tới các nút bao gồm quảng bá, các thuộc
tính dựa trên mutilcasting, geo-casting.
Loại giao thức thứ tư là dựa vào vị trí để đánh địa chỉ cho các nút cảm biến. Loại giao
thức này rất có ích cho những ứng dụng nơi mà vị trí của các nút cảm biến trong vùng
địa lý được bao phủ bởi mạng liên quan đến truy vấn được đưa ra bởi nút nguồn.
17
2.1.1. Các giao thức định tuyến dựa trên cấu trúc mạng [5]-[6]
2.1.1.1. Định tuyến các mạng phẳng
Loại giao thức định tuyến đầu tiên là các giao thức định tuyến phẳng multihop.
Trong các mạng phẳng, thông thường mỗi nút đóng vai trò như nhau và các nút cảm
biến cộng tác cùng với nhau để thực thi các tác vụ cảm nhận. Vì có rất nhiều nút cho
nên không thể gán cho từng nút các định danh toàn cục, do vậy cần phải định tuyến
theo trung tâm dữ liệu (data centric). Việc định tuyến này sử dụng trạm cơ sở (BS –
base station) gửi yêu cầu tới các vùng xác định và chờ dữ liệu đến từ các cảm biến
nằm trong vùng đã chọn đó. Khi dữ liệu được yêu cầu thông qua các truy vấn, việc đặt
tên theo thuộc tính rất cần thiết để xác định các thuộc tính của dữ liệu. Chúng ta sẽ
xem xét một số giao thức và ưu điểm cũng như hiệu năng của chúng.
Giao thức trung tâm dữ liệu: Flooding và Gossiping
Flooding là kỹ thuật chung thường được sử dụng để tìm ra đường và truyền
thông tin trong mạng adhoc vô tuyến và hữu tuyến.
Chiến lược định tuyến này rất đơn giản và không phụ thuộc vào cấu hình mạng
và các giải thuật định tuyến phức tạp. Phát tràn sử dụng phương pháp reactive nhờ đó
mỗi nút nhận dữ liệu hoặc điều khiển dữ liệu để gửi các gói tới các nút lân cận. Sau
khi truyền, một gói sẽ được truyền trên tất cả các đường có thể. Trừ khi mạng bị ngắt
không thì các gói sẽ truyền đến đích
Hình 6: Các mô hình RandomWalk, Flooding, Gossiping
Hơn nữa khi cấu hình mạng thay đổi các gói sẽ truyền theo những tuyến mới
giải thuật này sẽ tạo ra vô hạn các bản sao của mỗi gói khi đi qua các nút. Giải thuật
này có 3 nhược điểm lớn như sau: thứ nhất là hiện tượng bản tin kép. Tức là các gói dữ
liệu giống nhau được gửi đến cùng nút. Thứ hai là hiện tượng chồng chéo, tức là các
18
nút cùng cảm nhận một vùng không gian và do đó tạo ra các gói tương tự nhau gửi đến
các nút lân cận. Và thứ ba đó là thuật toán này không hề quan tâm đến vấn đề năng
lượng của các nút, các nút sẽ nhanh chóng tiêu hao năng lượng và làm giảm thời gian
sống của mạng.
Một sự cải tiến của giao thức này là Gossiping, thuật toán này cải tiến ở chỗ
mỗi nút sẽ ngẫu nhiên gửi gói mà nó nhận được đến một trong các nút lân cận của nó.
Thuật toán này làm giảm số lượng các gói lan truyền trong mạng, tránh hiện tượng bản
tin kép tuy nhiên có nhược điểm là có thể gói sẽ không bao giờ đến được đích.
Hai giao thức SPIN (Sensor Protocols for Information via Negotiation – Các
giao thức cảm biến thông tin thông qua điều chỉnh) và DD (Directed Diffusion –
Giao thức lan tỏa trực tiếp) ban đầu được sử dụng nhằm mục đích tiết kiệm năng
lượng thông qua việc điều chỉnh dữ liệu và loại bỏ các dữ liệu dư thừa. Hai giao thức
này sau đó được dùng để thiết kế nên nhiều giao thức khác nhưng vẫn đi theo mục
đích đặt ra.
SPIN [5]-[6]
Các giao thức tương thích được Heinzelman đưa ra và gọi chúng là Các giao
thức cảm nhận thông tin thông qua sự điều chỉnh (Sensor Protocols for Information via
Negotiation – SPIN). Giao thức này giả định rằng tất cả các nút trong mạng cảm biến
đều có khả năng làm trạm cơ sở. Điều này cho phép việc sử dụng bất kỳ một nút nào
có thể nhận được thông tin ngay lập tức. Các giao thức này sử dụng tài nguyên của các
nút lân cận với dữ liệu tương tự, và do đó cần phải có chi phí để phân phối dữ liệu mà
các nút khác không có. Họ SPIN sử dụng việc điều chỉnh dữ liệu và các thuật toán
thích ứng tài nguyên.
Các nút chạy SPIN phân công một tên mức cao để mô tả một cách hoàn chỉnh
dữ liệu thu được của chúng (gọi là siêu dữ liệu (meta-data)) và thực hiện các việc điều
chỉnh siêu dữ liệu trước khi dữ liệu bất kỳ được truyền đi. Điều này đảm bảo rằng
không có dư thừa dữ liệu được gửi qua mạng. Ngữ nghĩa của các định dạng siêu dữ
liệu được các ứng dụng đặc tả và không được quy định tại SPIN. Ví dụ, các cảm biến
có thể sử dụng ID duy nhất của chúng để báo cáo siêu dữ liệu nếu chúng bao phủ một
khu vực nhất định đã biết. Ngoài ra, SPIN có thể truy cập vào các mức năng lượng
hiện hành của nút và thích nghi với các giao thức nó hoạt động dựa trên lượng năng
lượng còn lại.
Những giao thức này làm việc theo cả cách sử dụng bảng điều khiển và phân
phối thông tin trên mạng, ngay cả khi người sử dụng không yêu cầu bất kỳ dữ liệu nào.