ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN SỸ MINH ĐỀ XUẤT CÁC THUẬT TOÁN ĐỊNH TUYẾN
ĐEM LẠI HIỆU QUẢ NĂNG LƢỢNG TRONG
MẠNG CẢM BIẾN KHÔNG DÂY

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ố: LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thanh Tùng

Nguyễn Sỹ Minh

3

LỜI CAM ĐOAN

Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi
tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm
luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu
tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa
được trình bày hoàn chỉnh trong bất cứ tài liệu nào.

Hà Nội, ngày tháng năm 2014
Học viên
Nguyễn Sỹ Minh 4 MỤC LỤC

Trang
Lời cảm ơn ……………………………………………………………
02
Lời cam đoan …………………………………………………………
03

1.4. Ứng dụng của mạng cảm biến không dây …………………………
27
1.4.1. Các ứng dụng về môi trường
28
1.4.2. Các ứng dụng trong y học ……………………………………
29
1.4.3. Ứng dụng trong gia đình ……………………………………….
29
1.4.4. Trong công nghiệp ……………………………………………
29
1.4.5. Trong nông nghiệp………………………………………………
30
1.4.6. Trong quân sự ………………………………………………
30
1.4.7. Trong giao thông ……………………………………………
30
1.5. Kết luận chương 1 …………………………………………………
30
Chƣơng 2. Định tuyến trong mạng cảm biến không dây …………….
31
5

2.1. Giới thiệu ………………………………………………………
31
2.2 Các giao thức định tuyến trong WSN
33
2.2.1 Giao thức định tuyến phẳng (Flat Routing)
35
2.2.1.1 Flooding và Gossiping
35

3.1.1. Giới thiệu về vấn đề quy hoạch tuyến tính (LP)
58
3.1.2. Giới thiệu ngôn ngữ AMPL (MathProg)
60
3.1.3. Mô hình toán học cho vấn đề định tuyến tối ưu trong mạng
cảm biến không dây.
62
3.2. Thuật toán Heuristic
65
3.2.1. Giới thiệu thuật toán Heuristic
65
3.2.2. Phương pháp Heuristic SP_RE cho vấn đề định tuyến trong
WSNs. …………………………………………………………………
65
3.3 Mô phỏng
67
6

3.3.1. Đặc điểm kênh vô tuyến
67
3.3.2. Thiết lập mô hình mạng và kết quả mô phỏng
71
3.4 Kết luận chương 3
73
Chƣơng 4. Mô phỏng mạng cảm biến không dây với NS2
74
4.1 Giới thiệu giao thức định tuyến AODV và ERS, EERS
74
4.2. Đề xuất phương pháp cải tiến
78

Chữ
viết tắt
Chữ đầy đủ
Nghĩa tiếng Việt
ACK
Acknowledgement
Bản tin phúc đáp
ADC
Analog-to-Digital Converter
Bộ chuyển đổi tương tự - Số
ADV
Advertise
Bản tin quảng bá
AMPL
A Mathematical
Programming Language
Ngôn ngữ lập trình toán học
AoA
Angle of Arrival
Góc đến
AODV
Ad-hoc On-Demand Distance
Vector
Giao thức định tuyến theo yêu cầu
BS
Base Station (Sink)
Trạm gốc
C4ISRT
Military Command, Control,
Communications,

dụng hiệu quả năng lượng
8

GLPK
GNU Linear Programming
Kit
Là phần mềm tối ưu hóa mã nguồn
mở dùng để giải các bài toán quy
hoạch tuyến tính.
GPS
Global Positioning System
Hệ thống định vị toàn cầu
Gusek
GLPK Under Scite Extended
Kit
là phần mềm mã nguồn mở hỗ trợ
cho GLPK
LEACH
Low-energy adaptive
clustering hierarchy
Giao thức phân cấp theo cụm thích
ứng năng lượng thấp
LP
Linear Programming
Quy hoạch tuyến tính
LDPC
Low-Density Parity Check
Kiểm tra bit chẵn lẻ mật độ thấp
MAC
Media Access Control

Định tuyến phân phối tuần tự
SMP
Sensor Management Protocol
Giao thức quản lí mạng cảm biến
SPIN
Sensor protocols for
information via negotiation
Giao thức cho thông tin dữ liệu
thông qua đàm phán
SQDDP
Sensor Query and Data
Dissemination Protocol
Giao thức phân phối dữ liệu và truy
vấn cảm biến
SP_RE
Shortest Path of the
Con đường ngắn nhất với năng
9

Remaining Energy
lượng còn lại
TADAP
Task Assignment and Data
Advertisement Protocol
Giao thức quảng bá dữ liệu và chỉ
định nhiệm vụ cho từng cảm biến
TCP
Transmission Control
Protocol
Giao thức điều khiển truyền dẫn


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1.1. Cấu trúc mạng cảm biến không dây
Hình 1.2. Cấu tạo nút cảm biến
Hình 1.3. Kiến trúc giao thức mạng cảm biến không dây.
Hình 1.4. Cấu trúc phẳng của mạng cảm biến không dây
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 phân cấp chức năng theo lớp
Hình 2.1. Các ứng dụng trong mạng WSN
Hình 2.2. Mô hình truyền dữ liệu đa chặng
Hình 2.3. Phân loại giao thức định tuyến
Hình 2.4. Flooding các gói dữ liệu trong mạng thông tin
Hình 2.5. Bùng nổ lưu lượng do Flooding
Hình 2.6. Vấn đề overlap lưu lượng do Flooding
Hình 2.7. Hoạt động cơ bản của giao thứ SPIN
Hình 2.8. Thủ tục bắt tay trong giao thức SPIN – PP
Hình 2.9. Giao thức SPIN – BC
Hình 2.10. Truyền interest
Hình 2.11. Hoạt động cơ bản của giao thức định tuyến Directed Disffusion.
Hình 2.12. Pha cài đặt gradient.
Hình 2.13. Phân phối dữ liệu theo đường được chọn nâng cao chất lượng.
Hình 2.14. Mô hình mạng LEACH
Hình 2.15. Các pha trong LEACH.
Hình 2.16. Cấu trúc mạng hình chuỗi
Hình 2.17. Nhóm phân cấp trong TEEN và APTEEN
Hình 2.18. Ví dụ về lưới ảo trong GAF
Hình 2.19. Sự chuyển trạng thái trong GAF
Hình 2.20. Chuyển tiếp địa lý đệ quy trong GEAR
Hình 3.1. Phương pháp SP_RE

di động không có. Thách thức khó khăn nhất của các thiết kế của các mạng cảm
biến không dây là năng lượng hạn chế của pin của các thiết bị cảm biến. Điều
này giới hạn thời gian hoạt động mà các mạng cảm biến không dây có thể hoạt
động trong các ứng dụng.
Đã có nhiều giao thức định tuyến tiết kiệm năng lượng đã được thiết kế
cho các mạng cảm biến không dây, trong đó năng lượng là một mối quan tâm
cần thiết. Có rất nhiều khía cạnh của một kiến trúc mạng có thể được thiết kế để
có năng lượng hiệu quả, bao gồm cả việc thiết kế các giao thức định tuyến. Giao
thức định tuyến đóng một phần quan trọng trong hiệu quả năng lượng của các
mạng cảm biến không dây (WSNs), vì dữ liệu truyền thông chiếm phần lớn các
nguồn tài nguyên năng lượng của mạng .
Do đó, mục đích của luận văn này là tập trung vào phát triển các thuật
toán định tuyến hỗ trợ hiệu quả năng lượng. Các thuật toán này được thiết kế để
thực hiện truyền thông dữ liệu trong khi đảm bảo kéo dài thời gian hoạt động
của WSNs.
2. Cấu trúc của luận văn
Ngoài phần mở đầu và kết luận, nội dung của luận văn được bố cục làm 4
chương cụ thể như sau:
13

Chƣơng 1. Tổng quan về mạng cảm biến không dây: Trình bày định
nghĩa, cấu trúc mạng WSNs, các yếu tố ảnh hưởng đến cấu trúc và các ứng dụng
của WSNs.
Chƣơng 2. Định tuyến trong mạng cảm biến không dây: Trình bày các
vấn đề phải đối mặt khi định tuyến đường đi trong WSNs và các giao thức định
tuyến đang được dùng phổ biến trong mạng cảm biến, cuối cùng là đánh giá ưu
điểm, nhược điểm của các giao thức định tuyến hiện tại.
Chƣơng 3. Mô hình toán cho vấn đề định tuyến tối ƣu trong mạng
cảm biến không dây và giải pháp
: Xây dựng mô hình toán cho vấn đề định

dây có thể được triển khai cho các mục đích chuyên dụng như giám sát và an
ninh; kiểm tra môi trường; tạo ra không gian thông minh; khảo sát, chính xác
hóa trong nông nghiệp; y tế; Lợi thế chủ yếu của chúng là khả năng triển
khai hầu như trong bất kì loại hình địa lý nào kể cả các môi trường nguy hiểm
không thể sử dụng mạng Sensor có dây truyền thống được.
Việc kết hợp các bộ cảm biến thành mạng lưới ngày nay đã tạo ra nhiều
khả năng mới cho con người. Các bộ vi cảm biến với bộ xử lý gắn trong và
các thiết bị vô tuyến hoàn toàn có thể gắn trong một kích thước rất nhỏ.
Chúng có thể hoạt động trong một môi trường dày đặc với khả năng xử lý tốc
độ cao. Do đó, với mạng cảm biến không dây ngày nay, người ta đã có thể
khám phá nhiều hiện tượng rất khó thấy trước đây.
Ngày nay, các mạng cảm biến không dây được ứng dụng trong nhiều
lĩnh vực như các cấu trúc chống lại địa chấn, nghiên cứu vi sinh vật biển,
giám sát việc chuyên chở các chất gây ô nhiễm, kiểm tra hệ sinh thái và môi
trường sinh vật phức tạp,
1.2. Nền tảng phát triển mạng
Việc phát triển mạng Wireless Sensor dựa trên công nghệ mạng Ad hoc
15

không dây và được thúc đẩy bởi hai yếu tố là nhu cầu ứng dụng và các tiến bộ
công nghệ.
1.2.1. Mạng Ad hoc không dây
Mạng Ad-hoc không dây là kiểu mạng không có cơ sở hạ tầng nền tảng,
được triển khai cho các mục đích sử dụng tạm thời cần thiết lập nhanh chóng,
thuận tiện như để tìm kiếm và cứu hộ, phục vụ liên lạc cho các thành
viên trong một cuộc họp, Mạng Ad hoc không cần các thành phần cơ sở
hạ tầng như tổng đài, trạm thu phát gốc hay bất kì một trung tâm điều khiển
nào. Tất cả các nút di động trong mạng Ad hoc được liên kết động với nhau
một cách tuỳ ý, không có bất kì sự điều khiển nào từ bên ngoài. Tất cả các nút
này đều có thể hoạt động như một bộ định tuyến nhờ khả năng tìm và duy trì

dày đặc bên trong đối tượng cần thăm dò hoặc ở rất gần nó. Vị trí của các
Sensor phải không cần định trước. Điều này cho phép triển khai ngẫu nhiên
trong các vùng không thể tiếp cận hoặc trong các hoạt động tránh sự nguy
hiểm. Điều này cũng có nghĩa là các thuật toán và giao thức phải có khả năng
tự tổ chức. Một đặc trưng nữa của mạng Sensor là khả năng cộng tác của
các Sensor. Các Nút Sensor phải có bộ xử lý gắn trong. Thay vì chuyển các
dữ liệu thô đến các nút có nhiệm vụ xử lý, các nút Sensor sẽ sử dụng khả năng
tính toán của nó để thực hiện các xử lý đơn giản và chỉ chuyển đi các dữ liệu
được yêu cầu và đã qua xử lý sơ bộ.
Các đặc điểm trên đưa đến một phạm vi ứng dụng lớn của mạng Sensor.
Một số lĩnh vực được ứng dụng là y tế, quân sự và an ninh. Ví dụ như các bác
sĩ sẽ kiểm tra từ xa các dữ liệu về sinh lý bệnh nhân. Điều này vừa thuận tiện
cho bệnh nhân vừa giúp các bác sĩ hiểu rõ hơn về tình trạng bệnh nhân.
Mạng Sensor còn được sử dụng để phát hiện các tác nhân hóa học trong
không khí và nước. Chúng giúp chỉ ra kiểu, sự cô lại và vị trí của các chất. Về
cơ bản, các mạng Sensor cung cấp cho người sử dụng sự hiểu tốt hơn, thông
minh hơn về môi trường. Chúng ta có thể thấy rằng trong tường lai, các mạng
wireless Sensor sẽ là một phần không thể thiếu trong cuộc sống, giống như
máy tính cá nhân hiện nay.
Các ứng dụng thực tế của mạng Sensor yêu cầu phải sử dụng công
nghệ mạng Wireless Ad hoc. Mặc dù vậy, có nhiều thuật toán và giao thức đã
17

được sử dụng cho các mạng Wireless Ad hoc truyền thống nhưng chúng không
phù hợp lắm với các đặc tính và yêu cầu ứng dụng của mạng Sensor, để minh
hoạ điểm này, sự khác nhau giữa mạng Sensor và mạng Wireless Ad hoc được
phác hoạ dưới đây: [8]
- Số lượng các nút cảm biến trong mạng cảm biến có thể lớn gấp nhiều lần
số lượng nút trong mạng ad hoc.
- Các nút cảm biến dễ bị lỗi.


Hình 1.1. Cấu trúc mạng cảm biến không dây
Dữ liệu được định tuyến lại đến các Sink bởi một cấu trúc đa điểm như
hình vẽ trên. Các Sink có thể giao tiếp với các nút quản lý nhiệm vụ (task
manager) qua mạng Internet hoặc vệ tinh.
Sink là một thực thể, tại đó thông tin được yêu cầu. Sink có thể là thực thể
bên trong mạng (là một nút cảm biến ) hoặc ngoài mạng. Thực thể ngoài mạng
có thể là một thiết bị thực sự ví dụ như máy tính xách tay mà tương tác với
mạng cảm biến, hoặc cũng đơn thuần chỉ là một gateway mà nối với mạng
khác lớn hơn như Internet nơi mà các yêu cầu thực sự đối với các thông tin lấy
từ một vài nút cảm biến trong mạng.
Giới thiệu về nút cảm biến: [34]
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
(1.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) và 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).
19 Hình 1.2 Cấu tạo nút cảm biến [34]
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 sensor đượ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

- 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 multi-hop, 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
21

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 lộn xộn

phẳng quản lý này làm cho các nút có thể làm việc cùng nhau theo cách có
hiệu quả nhất, định tuyến dữ liệu trong mạng cảm biến di động và chia sẻ tài
nguyên giữa các nút cảm biến. [8].

Hình 1.3 Kiến trúc giao thức mạng cảm biến không dây. [8]
Mặt phẳng quản lý năng lượng (Power Management Plane): Điều khiển
việc sử dụng năng lượng của nút cảm biến. Ví dụ, nút cảm biến có thể tắt khối
thu của nó sau khi thu được bản tin từ một nút lân cận. Điều này giúp tránh tạo
ra các bản tin giống nhau. Cũng vậy, khi mức năng lượng của nút cảm biến
thấp, nút cảm biến phát tín hiệu quảng bá tới các nút lân cận để thông báo nó
23

có mức năng lượng thấp và không thể tham gia vào quá trình chuyển tiếp các
bản tin chọn đường. Năng lượng còn lại sẽ được dành riêng cho nhiệm vụ cảm
biến.
Mặt phẳng quản lý di động (Mobility Management Plane): Phát hiện và
ghi lại sự di chuyển của các nút cảm biến để duy trì tuyến tới người sử dụng,
các nút cảm biến có thể lưu vết của các nút cảm biến lân cận. Nhờ xác định
được các nút cảm biến lân cận, các nút cảm biến có thể cân bằng giữa năng
lượng của nó và nhiệm vụ thực hiện.
Mặt phẳng quản lý nhiệm vụ (Task Management Plane): Dùng để làm cân
bằng và xác định các nhiệm vụ cảm biến trong một phạm vi quan sát thực
tế. Không phải tất cả các nút cảm biến trong vùng đó đều phải thực
hiện nhiệm vụ cảm biến tại cùng một thời điểm. Kết quả là một số nút
cảm biến thực hiện nhiệm vụ nhiều hơn các nút khác tuỳ theo mức năng
lượng của nó. Chức năng quản lý này là cần thiết để các nút cảm biến có thể
làm việc cùng nhau theo một cách thức sử dụng hiệu quả năng lượng, chọn
đường số liệu trong mạng cảm biến di động và phân chia tài nguyên giữa các
nút cảm biến.
Lớp vật lý: Có nhiệm vụ lựa chọn tần số, tạo ra tần số sóng mang, phát

Vì vậy, lớp mạng của mạng cảm biến được thiết kế tuân theo nguyên tắc sau:
[17]
- Hiệu quả năng lượng luôn luôn được coi là vấn đề quan trọng
- Mạng cảm biến chủ yếu là tập trung dữ liệu
- Tích hợp dữ liệu chỉ được sử dụng khi nó không cản trở sự cộng tác có
hiệu quả của các nút cảm biến.
1.3.3. Các cấu trúc đặc trƣng của mạng cảm biến không dây
1.3.3.1. Cấu trúc phẳng
Trong cấu trúc phẳng (flat architecture) (hình 1.4), tất cả các nút đều
ngang hàng và đồng nhất trong hình dạng và chức năng. Các nút giao tiếp với
Sink qua Multi-hop 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
25

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ố… [16]

Hình 1.4 Cấu trúc phẳng của mạng cảm biến không dây
1.3.3.2. Cấu trúc tầng
Trong cấu trúc tầng (tiered architecture) (hình 1.5)[16], 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-hop hay multi-
hop ( 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 ở một mức 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
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 giữa các nút. Những chức năng này có thể phân theo cấp,