Cải tiến thuật toán định tuyến cho trạm thu phát di động trong mạng cảm biến không dây

"IMPROVING ROUTING ALGORITHM FOR MOBILE SINK IN WSN"

ABSTRACT

In WSN, to collect and process data, the network uses sensors. Sensors work based

on battery power. However, it is not easy to reload. Therefore, energy is always a matter

of concern for scientists and researchers . Besides, WSN is applied a lot in life . To

extend the life of the network and less energy consumed , in this paper, propose a routing

algorithm between Leach _C and ACO (Ant Colony Optimize). Using a mobile sink to

collect data from the base station (BS) to the cluster headers (CHS), the direction of the

sink is determined by the ACO algorithm. Results, compared to LEACH, LEACH-C,

LEACH-CD. From there, save energy and improve network life time.

“CẢI TIẾN THUẬT TOÁN ĐỊNH TUYẾN CHO MOBILE SINK TRONG WSN”

TÓM TẮT

Trong WSN, để thu thập và xử lý dữ liệu, mạng sử dụng các sensors. Các sensors hoạt

động được là nhờ năng lượng pin. Tuy nhiên, nó không dễ dàng để nạp lại. Vì vậy, năng

lượng luôn là vấn đề quan tâm của các nhà khoa học và nghiên cứu. Bên cạnh đó, WSN

được ứng dụng rất nhiều trong cuộc sống. Để kéo dài tuổi thọ của mạng và năng lượng ít

bị tiêu hao, trong bài báo này, đề xuất một thuật toán định tuyến kết hợp giữa LEACH_C

và ACO. Sử dụng một sink di động đi thu thập dữ liệu từ trạm gốc đến các trưởng cụm,

hướng đi của sink được quyết định bởi thuật toán ACO. Kết quả, được so sánh với

LEACH, LEACH-C, LEACH-CD. Từ đó, tiết kiệm được năng lượng và cải thiện thời

gian sống của mạng.

i

LỜI CAM ĐOAN

Tôi cam đoan rằng luận văn “Cải tiến thuật toán định tuyến cho trạm thu phát

di động trong mạng cảm biến không dây” là bài nghiên cứu của chính tôi.

Ngoại trừ những tài liệu tham khảo đƣợc trích dẫn trong luận văn này, tôi cam

đoan rằng toàn phần hay những phần nhỏ của luận văn này chƣa từng đƣợc công bố

hoặc đƣợc sử dụng để nhận bằng cấp ở những nơi khác.

Luận văn này chƣa bao giờ đƣợc nộp để nhận bất kỳ bằng cấp nào tại các

trƣờng đại học hoặc cơ sở đào tạo khác.

TP.HCM, ngày … tháng … năm 2019

Học viên thực hiện luận văn

Tạ Chí Qui Nhơn

ii

LỜI CẢM ƠN

Trong suốt quá trình học tập, nghiên cứu và hoàn thành luận văn thạc sĩ, ngoài

những cố gắng nỗ lực của bản thân, tôi đã nhận đƣợc sự hƣớng dẫn, giúp đỡ rất

nhiệt tình của quý thầy cô, cùng với sự động viên khích lệ và ủng hộ của gia đình,

bạn bè và đồng nghiệp; với lòng kính trọng và biết ơn sâu sắc tôi xin đƣợc gửi lời

cảm ơn chân thành đến:

Ban lãnh đạo và tất cả cán bộ, công chức, viên chức đang công tác tại Trƣờng

Cao đẳng Công nghệ thông tin Thành phố Hồ Chí Minh đã tạo điều kiện để tôi hoàn

thành việc học cao học tại trƣờng Đại học Mở Tp. HCM.

Xin gửi lời cảm ơn trân trọng nhất đến PGS.TS Trần Công Hùng, ngƣời đã

trực tiếp hƣớng dẫn, chỉ bảo, chia sẻ kiến thức, tài liệu, tạo mọi điều kiện thuận lợi

và định hƣớng cho em trong suốt quá trình thực hiện luận văn.

Bên cạnh đó, tôi cũng đã nhận đƣợc rất nhiều sự hỗ trợ, góp ý từ NCS. Phan

Thị Thể, Ths. Nguyễn Ngọc Thắng và các bạn bè; xin gửi lời tri ân đến tất cả quý

thầy, cô và các anh chị.

Do thời gian có hạn, bản thân đã cố gắng và nỗ lực hết sức mình nhƣng chắc

rằng luận văn khó tránh khỏi thiếu sót; tôi rất mong nhận đƣợc sự thông cảm và chỉ

bảo tận tình của quý thầy cô và các anh chị.

Xin chân thành cảm ơn!

TP.HCM, ngày … tháng … năm 2019

Học viên thực hiện luận văn

Tạ Chí Qui Nhơn

iii

MỤC LỤC

Trang

LỜI CAM ĐOAN ........................................................................................................i

LỜI CẢM ƠN .............................................................................................................ii

MỤC LỤC................................................................................................................. iii

DANH MỤC HÌNH VẼ.............................................................................................vi

DANH MỤC BẢNG.................................................................................................vii

DANH MỤC TỪ VIẾT TẮT ................................................................................. viii

MỞ ĐẦU.....................................................................................................................1

CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY .....................5

1.1.Giới thiệu..............................................................................................................5

1.2.Cấu trúc mạng cảm biến không dây..................................................................6

1.2.1. Cấu trúc một nút mạng WSN..............................................................6

1.2.2. Cấu trúc mạng cảm biến không dây ...................................................7

1.2.3. Kiến trúc giao thức mạng WSN ..........................................................9

1.3.Một số vấn đề thiết kế mạng cảm biến không dây .........................................12

1.3.1. Khả năng chịu lỗi (fault tolerance) ...................................................12

1.3.2. Khả năng mở rộng (scalability).........................................................12

1.3.3. Chi phí sản xuất (production costs) ..................................................12

1.3.4. Hạn chế của phần cứng (hardware constraints)..............................13

1.3.5. Cấu hình mạng cảm biến (network topology)..................................13

1.3.6. Sink di động.........................................................................................13

1.3.7. Tiêu thụ năng lượng ...........................................................................13

1.3.8. Độ tin cậy .............................................................................................14

1.3.9. Độ trễ....................................................................................................14

1.4.Ứng dụng của mạng cảm biến không dây.......................................................14

1.4.1. Quân sự................................................................................................14

1.4.2. Công nghiệp.........................................................................................15

1.4.3. Nông nghiệp.........................................................................................16

iv

1.4.4. Giám sát môi trường ..........................................................................18

1.4.5. Gia đình ...............................................................................................19

1.4.6. Sức khỏe...............................................................................................20

1.4.7. Giao thông:..........................................................................................20

1.5.Kết luận..............................................................................................................21

CHƢƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN....................................................22

2.1.Định tuyến trong WSN .....................................................................................22

2.2.Một số giao thức định tuyến trong WSN ........................................................23

2.2.1. LEACH ................................................................................................23

2.2.2. LEACH_C ...........................................................................................27

2.2.3. Logic mờ ..............................................................................................28

2.2.4. Giao thức CHEF Fuzzy (Cluster Head Election mechanism using

Fuzzy logic) .......................................................................................................30

2.3.Mô hình trạm thu phát di động: gồm 03 dạng ...............................................32

2.4.Một số giải thuật định tuyến có trạm thu phát di động.................................33

2.4.1. Thuật toán MSA (Mobile Sink Assisted Energy Efficient Routing

Algorithm).........................................................................................................33

2.4.2. Thuật toán MECA (Mobile sink based Energy-efficient Clustering

Algorithm).........................................................................................................34

2.4.3. LEACH kết hợp mobile sink theo quỹ đạo cố định.........................38

2.4.4. LEACH_C có mobile sink..................................................................39

2.4.5. Định tuyến động trên lưới ảo (Virtual Grid based Dynamic Route

Adjustment - VGDRA) ....................................................................................41

2.4.6. Đề xuất giảm sự tiêu hao năng lượng trong WSN bằng phương

pháp tìm đường đi ngắn nhất..........................................................................43

2.4.7. Đề xuất hướng di chuyển để tiết kiệm năng lượng cho sink mobility

trong mạng cảm biến không dây.....................................................................46

2.4.8. Thuật toán tìm đường đi ngắn nhất ACO........................................48

2.5.Kết luận..............................................................................................................51

CHƢƠNG 3: GIẢI PHÁP ĐỀ XUẤT......................................................................52

3.1.Giới thiệu: ..........................................................................................................52

v

3.2.Đề xuất: ..............................................................................................................52

3.2.1. Mô hình tiêu thụ năng lượng .............................................................53

3.2.2. Hướng di chuyển của mobile sink:....................................................54

3.2.3. Lưu đồ hoạt động của thuật toán đề xuất ........................................54

3.3.Kết luận..............................................................................................................56

CHƢƠNG 4: MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU SUẤT CỦA GIẢI PHÁP ĐỀ

XUẤT........................................................................................................................57

4.1.Cài đặt mô phỏng:.............................................................................................57

4.2.Các tiêu chí đánh giá hiệu suất ........................................................................57

4.3.Kết quả mô phỏng .............................................................................................58

4.4.Kết luận..............................................................................................................61

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN................................................................62

TÀI LIỆU THAM KHẢO ........................................................................................63