LỜI NÓI ĐẦU

Ngày nay nhờ có những tiến bộ nhanh chóng trong khoa học và công nghệ sự phát triển của những mạng bao gồm các cảm biến giá thành rẻ, tiêu thụ ít năng lượng và đa chức năng đã nhận được những sự chú ý đáng kể. Hiện nay người ta đang tập trung triển khai các mạng cảm biến để áp dụng vào trong cuộc sống hàng ngày. Đó là các lĩnh vực về y tế, quân sự, môi trường, giao thông... Trong một tương lai không xa, các ứng dụng của mạng cảm biến sẽ trở thành một phần không thể thiếu trong cuộc sống con người nếu chúng ta phát huy được hết các điểm mạnh mà không phải mạng nào cũng có được như mạng cảm biến.

Tuy nhiên mạng cảm ứng đang phải đối mặt với rất nhiều thách thức, một trong những thách thức lớn nhất đó là nguồn năng lượng bị giới hạn và không thể nạp lại. Hiện nay rất nhiều nhà nghiên cứu đang tập trung vào việc cải thiện khả năng sử dụng hiệu quả năng lượng của mạng cảm biến trong từng lĩnh vực khác nhau.

Trong quá trình tìm hiểu và nghiên cứu về mạng cảm biến, em đã lựa chọn và tìm hiểu giao thức định tuyến PEGASIS. Giao thức này cải thiện đáng kể thời gian sống của mạng cảm biến, và em quyết định chọn đề tài này làm đồ án tốt nghiệp.

Để có thể hoàn thành được đồ án tốt nghiệp này, em đã được học hỏi những kiến thức quí báu từ các thầy, cô giáo của Trường Đại học Bách Khoa Hà Nội trong suốt năm năm đại học. Em vô cùng biết ơn sự dạy dỗ, chỉ bảo tận tình của các thầy, các cô trong thời gian học tập này.

Em xin bày tỏ lòng biết ơn tới TS. Trần Ngọc Lan-bộ môn kỹ thuật thông tin - Khoa điện tử viễn thông- Đại học Bách Khoa Hà Nội, đã tận tình chỉ bảo và định hướng cho em nghiên cứu đề tài này. Cô đã cho em những lời khuyên quan trọng trong suốt quá trình hoàn thành đồ án.

Cuối cùng, em xin cảm ơn gia đình và bạn bè luôn tạo điều kiện thuận lợi, động viên và giúp đỡ em trong suốt thời gian học tập, cũng như quá trình nghiên cứu, hoàn thành đồ án này.

TÓM TẮT ĐỒ ÁN

Ngày nay nhờ tiến bộ vượt bậc trong khoa học và công nghệ, mạng cảm biến đã trở thành đề tài nghiên cứu nóng bỏng và nhận được sự tiến bộđáng kể trong vài năm qua. Mạng cảm biến là mạng vô tuyến bao gồm các thiết bị cảm biến được phân bố một cách ngẫu nhiên trong không gian, nhằm quan sát các hiện tượng vật lý , hay điều kiện môi trường như nhiệt độ, âm thanh, sự chấn động, áp suất, sự chuyển động, ô nhiễm ở các vị trí khác nhau.

Sự phát triển của mạng cảm biến mởđầu là các ứng dụng trong quân đội ví dụ như giám sát chiến trường. Tuy nhiên bây giờ mạng cảm biến còn được sử dụng trong nhiều lĩnh vực dân dụng bao gồm: quan sát môi trường sống, chăm sóc sức khỏe, nhà tựđộng hay điều khiển giao thông.

Các con cảm biến là các thiết bịđiện tử nhỏ, thông thường được trang bị bộ thu phát vô tuyến hoặc các thiết bị không dây khác, một bộ vi xử lý nhỏ và một nguồn năng lượng. Các con cảm biến này có khả năng thu thập, xử lý và truyền thông thông tin đến các nút khác và ra thế giới bên ngoài.

Mạng cảm biến là một lĩnh vực rất sâu rộng, đồ án này sẽ giới thiệu một cách khái quát nhất về các đặc điểm của mạng cảm biến. Sau đó phần cuối sẽ nghiên cứu và đưa ra giải thuật định tuyến PEGASIS nhằm cải thiện đáng kể thời gian sống của mạng.

Đồ án này gồm có 4 chương:

Chương 1: Tổng quan về mạng cảm biến. Chương này trình bày những khái niệm chung nhất về WSNs và đưa ra cấu trúc của mạng cảm biến. Đồng thời cũng nêu ra các ứng dụng cụ thể trong nhiều lĩnh vực cuộc sống.

Chương 2: Các giao thức đặc trưng của mạng cảm biến. Chương này đưa ra hai giao thức đặc trưng đó là : đồng bộ thời gian và giao thức vị trí. Hai giao thức này rất quan trọng và có ý nghĩa đối với mạng cảm biến. http://www.ebook.edu.vn

Chương 3: Định tuyến trong mạng cảm biến. Chương này phân loại các giao thức định tuyến ra làm ba loại : trung tâm dữ liệu, phân cấp và định tuyến dựa vào vị trí địa lý.

Chương 4: Giới thiệu về Mobility framework của OMNeT++ và mô phỏng giao thức định tuyến PEGASIS. Chương này nêu ra những ưu điểm của PEGASIS so với giải thuật LEACH và đưa ra kết quả mô phỏng . http://www.ebook.edu.vn

Abstract

Nowadays thanks to rapid advances in science and technology, Wireless Sensor Networks have become a hot issue in research, and significant progress has been achieved in the past few years.

Wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control.

Sensor nodes are small electronic components, typically equipped with a radio transceiver or other wireless communications device, a small microcontroller, and an energy source, usually a battery. It's capable of gathering, processing, and communicating information to other nodes and to the outside world.

The field of WSN is wide and deep. This thesis will introduce overview about WSN and give out a protocol which extends lifetime of WSN.

This thesis has a total of 4 chapters:

Chapter 1: Overview of wireless sensor networks: giving out the definition, the architecture (includes factors that influence the architecture of the networks and the two typical architectures of sensor networks), the applications and also pointing out many challenges that WSN are facing.

Chapter 2: Protocols in WSN: giving out an overview of protocols used in WSN and the most two important ones, those are localization and time synchronization protocols. http://www.ebook.edu.vn

Chapter 3: Routing in WSN: summarizing recent routing protocols for sensor networks and presenting a classification for the various approaches pursued. The three main categories explored in this chapter are data - centric, hierarchical and location - based. Each routing protocol is described and discussed under the appropriate category.

Chapter 4: Simulating PEGASIS using Mobility framework of OMNeT++: giving out an overview of OMNeT++ and Mobility framework, a basic algorithm of PEGASIS. After that, the presented simulation results show that PEGASIS extends significantly the life time of sensor networks. http://www.ebook.edu.vn

Mục lục

DANH SÁCH HÌNH VẼ.............................................................................................. iiiDANH SÁCH BẢNG BIỂU ..........................................................................................vDANH SÁCH CÁC TỪ VIẾT TẮT............................................................................viChương 1. Tổng quan về mạng cảm biến ....................................................................1

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

1.2. Cấu trúc mạng cảm biến........................................................................................2

1.2.1. Các yếu tốảnh hưởng đến cấu trúc mạng cảm biến ......................................2

1.2.2. Kiến trúc giao thức mạng...............................................................................8

1.2.3. Hai cấu trúc đặc trưng của mạng cảm biến.................................................10

1.2.3.1. Cấu trúc phẳng.......................................................................................10

1.2.3.2. Cấu trúc tầng .........................................................................................10

1.3. Ứng dụng.............................................................................................................13

1.3.1. Ứng dụng trong quân đội..............................................................................14

1.3.2. Ứng dụng trong môi trường..........................................................................16

1.3.3. Ứng dụng trong chăm sóc sức khỏe..............................................................17

1.3.4. Ứng dụng trong gia đình ..............................................................................18

1.4. Kết luận ...............................................................................................................18

Chương 2. Các giao thức đặc trưng của mạng cảm biến .........................................19

2.1. Giới thiệu về giao thức đặc trưng trong mạng cảm biến.....................................19

2.2. Giao thức đồng bộ thời gian................................................................................19

2.2.1. Đồng hồ các nút cảm biến và sự chính xác ..................................................21

2.2.2. Đồng bộ thời gian trong mạng cảm biến......................................................22

2.2.2.1. Giao thức đồng bộ giữa bên nhận và bên phát......................................24

2.2.2.2. Giao thức đồng bộ giữa bên nhận và bên nhận.....................................30

2.3. Giao thức vị trí.....................................................................................................34

2.3.1. Định vị dựa vào mốc có sẵn .........................................................................35

2.3.2. Định vị dựa vào vị trí tương đối...................................................................36

2.4 Kết luận ................................................................................................................37

Chương 3. Định tuyến trong mạng cảm biến ............................................................38

3.1. Giới thiệu.............................................................................................................38

3.2. Thách thức trong vấn đềđịnh tuyến....................................................................38

3.3. Các vấn đề về thiết kế giao thức định tuyến........................................................39http://www.ebook.edu.vn

3.3.1. Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng.............................39

3.3.2. Ràng buộc về tài nguyên...............................................................................39

3.3.3. Mô hình dữ liệu trong mạng cảm biến..........................................................40

3.3.4. Cách truyền dữ liệu ......................................................................................40

3.4. Phân loại và so sánh các giao thức định tuyến....................................................42

3.5. Giao thức trung tâm dữ liệu.................................................................................44

3.5.1. Flooding và Gossiping..................................................................................44

3.5.2. SPIN..............................................................................................................45

3.5.3. Directed Diffusion ........................................................................................47

3.6. Giao thức phân cấp..............................................................................................50

3.6.1. LEACH..........................................................................................................50

3.6.2. PEGASIS.......................................................................................................53

3.7. Giao thức dựa trên vị trí ......................................................................................54

3.7.1. GAF...............................................................................................................55

3.7.2. GEAR ............................................................................................................57

3.8. Kết luận ...............................................................................................................59

Chương 4. Mô phỏng PEGASIS bằng Mobility Framework của OMNeT++........60

4.1. Giới thiệu về OMNeT++ và Mobility Framework..............................................60

4.1.1. Giới thiệu về OMNeT++..............................................................................60

4.1.2. Giới thiệu về Mobility...................................................................................64

4.2. Giới thiệu về PEGASIS.......................................................................................71

4.2.1. PEGASIS cơ bản...........................................................................................72

4.2.2. PEGASIS cải tiến..........................................................................................73

4.3. Mô phỏng.............................................................................................................76

4.3.1. Mô hình năng lượng .....................................................................................76

4.3.2. Giả thiết và thiết lập thông số ban đầu cho quá trình mô phỏng.................82

4.3.3. Kết quả mô phỏng.........................................................................................89

4.4. Kết luận và hướng nghiên cứu tiếp theo..............................................................91

KẾT LUẬN...................................................................................................................92

Tài liệu tham khảo .......................................................................................................93http://www.ebook.edu.vn

DANH SÁCH HÌNH VẼ

Hình 1.1 Cấu trúc mạng cảm biến....................................................................................3Hình 1.2 Cấu tạo nút cảm biến........................................................................................4Hình 1.3 Kiến trúc giao thức mạng cảm biến .................................................................8Hình 1.4 Cấu trúc phẳng của mạng cảm biến...............................................................10Hình 1.5 Cấu trúc tầng của mạng cảm biến...................................................................11Hình 1.6 Cấu trúc mạng phân cấp chức năng theo lớp..................................................11Hình 1.7 Ứng dụng trong quân đội...............................................................................15Hình 1.8 Ứng dụng trong môi trường...........................................................................17Hình 1.9 Ứng dụng trong chăm sóc sức khỏe...............................................................18Hình 2.1 Xác định góc đến của âm thanh ở xa bởi một dãy sensor.............................20Hình 2.2 Đồng bộ bên phát/bên nhận và bên nhận/bên nhận. ......................................23Hình 2.3 Hoạt động của việc đồng bộ bên phát/bên nhận .............................................25Hình 2.4 LTS multihop phân bố...................................................................................29Hình 2.5 Ví dụ về RBS ..................................................................................................31Hình 2.6 Chuyển tiếp gói dữ liệu và chuyển đổi nhãn thời gian ..................................33Hình 3.1 Mô hình truyền dữ liệu giữa sink và các nút...................................................41Hình 3.2 Truyền gói trong Flooding ..............................................................................44Hình 3.3 Ba tín hiệu bắt tay của SPIN ..........................................................................46Hình 3.4 Hoạt động của SPIN........................................................................................46Hình 3.5 Hoạt động cơ bản của Directed Diffusion......................................................49Hình 3.6 Mô hình mạng LEACH.................................................................................51Hình 3.7 Ví dụ về lưới ảo trong GAF ...........................................................................56Hình 3.8 Sự chuyển trạng thái trong GAF ....................................................................56Hình 3.9 Chuyển tiếp địa lý đệ quy trong GEAR .........................................................59Hình 4.1 Cấu trúc phân cấp module trong OMNeT++ .................................................61Hình 4.2 Các kết nối trong OMNeT++.........................................................................62http://www.ebook.edu.vn

Hình 4.3 Cấu trúc của host di động...............................................................................65Hình 4.4 Cấu trúc kế thừa module trong MF................................................................67Hình 4.5 Xây dựng chuỗi sử dụng thuật toán Greedy..................................................72Hình 4.6 Xử lý lỗi khi một nút trong chuỗi chết............................................................73Hình 4.7 Khắc phục của PEGASIS................................................................................76Hình 4.8 Mô hình năng lượng đơn giản.........................................................................79Hình 4.9 Trạm BS gửi broadcast đến cho các nút trong mạng.....................................84Hình 4.10 Trạm BS gửi bản tin Max Distance đến nút xa nhất.....................................85Hình 4.11 Nút xa nhất chuỗi gửi bản tin Invite mời nút gần nhất vào chuỗi.................86Hình 4.12 Các nút kết nối vào nhau tạo thành chuỗi.....................................................86Hình 4.13 Chuỗi sau khi thiết lập xong. ........................................................................87Hình 4.14 Kết quả khi mô phỏng mạng có kích thước.................................................90(50m,50m) với năng lượng ban đầu của nút là 0.25 J....................................................90Hình 4.15 Kết quả mô phỏng khi kích thước mạng......................................................90là (100m.100m) với năng lượng của nút ban đầu là 0.5J...............................................90http://www.ebook.edu.vn

iv

DANH SÁCH BẢNG BIỂU

Bảng 3.1 Phân loại và so sánh các giao thức chọn đường trong WSN.........................43 Bảng 3.2 Miêu tả interert sử dụng cặp giá trị thuộc tính ..............................................48 Bảng 4.1 Các loại bản tin tương ứng của các lớp .........................................................68 Bảng 4.2 Số vòng khi 1%, 20%, 50%, và 100% nút chết..............................................89 http://www.ebook.edu.vn

v

DANH SÁCH CÁC TỪ VIẾT TẮT

ID Identification ADC Analog to Digital Converter RF Radio frequency MAC Media Access Control UTC Coordinated Universal Time GPS Global Positioning System LTS Lightweight time synchronization protocol RBS Reference broadcast synchronization). RSS Received signal strength TDOA Time of arrival AOA Angle of arrival TDOA Time difference of arrival RSSI Receiver Signal Strength Indicator PLF Perceptive localization framework TDMA Time Division Multiple Access CDMA Code Division Multiple Access ARP Address Resolution Protocol BS BaseStation WSN Wireless Sensor Network http://www.ebook.edu.vn

vi Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Chương 1. Tổng quan về mạng cảm biến

1.1. Giới thiệu

Trong những năm gần đây, rất nhiều mạng cảm biến không dây đã và đang được phát triển và triển khai cho nhiều các ứng dụng khác nhau như: theo dõi sự thay đổi của môi trường, khí hậu, giám sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học, chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng như quản lý thuốc trong các bệnh viên, theo dõi và điều khiển giao thông, các phương tiện xe cộ...

Hơn nữa với sự tiến bộ công nghệ gần đây và hội tụ của hệ thống các công nghệ như kỹ thuật vi điện tử, công nghệ nano, giao tiếp không dây, công nghệ mạch tích hợp, vi mạch phần cảm biến, xử lý và tính toán tín hiệu...đã tạo ra những con cảm biến có kích thước nhỏ, đa chức năng, giá thành thấp, công suất tiêu thụ thấp, làm tăng khả năng ứng dụng rộng rãi của mạng cảm biến không dây.

Một mạng cảm biến không dây là một mạng bao gồm nhiều nút cảm biến nhỏ có giá thành thấp, và tiêu thụ năng lượng ít, giao tiếp thông qua các kết nối không dây, có nhiệm vụ cảm nhận, đo đạc, tính toán nhằm mục đích thu thập, tập trung dữ liệu để đưa ra các quyết định toàn cục về môi trường tự nhiên .

Những nút cảm biến nhỏ bé này bao gồm các thành phần :

Các bộ vi xử lý rất nhỏ, bộ nhớ giới hạn,bộ phận cảm biến, bộ thu phát không dây, nguồn nuôi. Kích thước của các con cảm biến này thay đổi từ to như hộp giấy cho đến nhỏ như hạt bụi, tùy thuộc vào từng ứng dụng.

Khi nghiên cứu về mạng cảm biến không dây, một trong những đặc điểm quan trọng và then chốt đó là thời gian sống của các con cảm biến hay chính là sự giới hạn về năng lượng của chúng. Các nút cảm biến này yêu cầu tiêu thụ công suất thấp. Các nút cảm biến hoạt động có giới hạn và nói chung là không thể thay thếđược nguồn cung cấp. Do đó, trong khi mạng truyền thông tập trung vào đạt được các dịch vụ chất

Đỗ Thị Tuyết ĐT6-K48 1 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

lượng cao, thì các giao thức mạng cảm biến phải tập trung đầu tiên vào bảo toàn công suất.

Mạng cảm biến có một sốđặc điểm sau: Có khả năng tự tổ chức, yêu cầu ít hoặc không có sự can thiệp của con người

Truyền thông không tin cậy, quảng bá trong phạm vi hẹp và định tuyến multihop

Triển khai dày đặc và khả năng kết hợp giữa các nút cảm biến Cấu hình mạng thay đổi thường xuyên phụ thuộc vào fading và hư hỏng ở các nút

Các giới hạn về mặt năng lượng, công suất phát, bộ nhớ và công suất tính toán Chính những đặc tính này đã đưa ra những chiến lược mới và những yêu cầu thay đổi trong thiết kế mạng cảm biến.

1.2. Cấu trúc mạng cảm biến

1.2.1. Các yếu tốảnh hưởng đến cấu trúc mạng cảm biến

Các cấu trúc hiện nay cho mạng Internet và mạng ad hoc không dây không dùng được cho mạng cảm biến không dây, do một số lý do sau: 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. Cấu trúc mạng cảm biến thay đổi khá thường xuyên. Các nút cảm biến chủ yếu sử dụng truyền thông kiểu quảng bá, trong khi hầu hết các mạng ad hoc đều dựa trên việc truyền điểm-điểm.

Đỗ Thị Tuyết ĐT6-K48 2 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Các nút cảm biến bị giới hạn về năng lượng, khả năng tính toán và bộ nhớ.

Các nút cảm biến có thể không có số nhận dạng toàn cầu (global identification) (ID) vì chúng có một số lượng lớn mào đầu và một số lượng lớn các nút cảm biến.

Do vậy, cấu trúc mạng mới sẽ: Kết hợp vấn đề năng lượng và khả năng định tuyến. Tích hợp dữ liệu và giao thức mạng. Truyền năng lượng hiệu quả qua các phương tiện không dây. Chia sẻ nhiệm vụ giữa các nút lân cận.

Các nút cảm biến được phân bố trong một sensor field như hình (1.1). Mỗi một nút cảm biến có khả năng thu thập dữ liệu và định tuyến lại đến các sink.

Hình 1.1 Cấu trúc mạng cảm biến

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 node) 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à ¾

Đỗ Thị Tuyết ĐT6-K48 3 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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:

Cấu tạo của nút cảm biến như sau:

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

Hình 1.2 Cấu tạo nút cảm biến.

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.

Đỗ Thị Tuyết ĐT6-K48 4 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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

Đặc điểm của cấu trúc 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 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 ¾ ể

Đỗ Thị Tuyết ĐT6-K48 5 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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 sensor 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ể ẻ

Đỗ Thị Tuyết ĐT6-K48 6 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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 hoặc xếp theo trật tự trên trường cảm biến. Chúng có thểđược triển 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 (power consumption) :

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 multihop 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ữ ổ ữ ữ

Đỗ Thị Tuyết ĐT6-K48 7 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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

1.2.2. Kiến trúc giao thức mạng

Kiến trúc giao thức áp dụng cho mạng cảm biến được trình bày trong hình (1.3). Kiến trúc này bao gồm các lớp và các mặt phẳng quản lý . Các mặt 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.

Hình 1.3 Kiến trúc giao thức mạng cảm biến

Mặt phẳng quản lý công suất : Quản lý cách cảm biến sử dụng nguồn năng lượng của nó. Ví dụ : nút cảm biến có thể tắt bộ thu sau khi nhận được một bản tin. Khi mức công suất của con cảm biến thấp, nó sẽ broadcast sang nút cảm biến bên cạnh thông báo rằng mức năng lượng của nó thấp và nó không thể tham gia vào quá trình định tuyến .

Mặt phẳng quản lý di động : có nhiệm vụ phát hiện và đăng ký sự chuyển động của các nút. Các nút giữ việc theo dõi xem ai là nút hàng xóm của chúng.

Đỗ Thị Tuyết ĐT6-K48 8 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Mặt phẳng quản lý : Cân bằng và sắp xếp nhiệm vụ cảm biến giữa các nút trong một vùng quan tâm. Không phải tất cả các nút cảm biến đều thực hiện nhiệm vụ cảm nhận ở cùng một thời điểm.

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 hiện tín hiệu, điều chế và mã hóa tín hiệu. Băng tần ISM 915 MHZ được sử dụng rộng rãi trong mạng cảm biến. Vấn đề hiệu quả năng lượng cũng cần phải được xem xét ở lớp vật lý, ví dụ : điều biến M hoặc điều biến nhị phân.

Lớp liên kết dữ liệu : lớp này có nhiệm vụ ghép các luồng dữ liệu, phát hiện các khung (frame) dữ liệu, cách truy nhập đường truyền và điều khiển lỗi. Vì môi trường có tạp âm và các nút cảm biến có thể di động, giao thức điều khiển truy nhập môi trường (MAC) phải xét đến vấn đề công suất và phải có khả năng tối thiểu hoá việc va chạm với thông tin quảng bá của các nút lân cận.

Lớp mạng : Lớp mạng của mạng cảm biến được thiết kế tuân theo nguyên tắc sau :

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.

Lớp truyền tải : chỉ cần thiết khi hệ thống có kế hoạch được truy cập thông qua mạng Internet hoặc các mạng bên ngoài khác.

Lớp ứng dụng : Tuỳ theo nhiệm vụ cảm biến, các loại phần mềm ứng dụng khác nhau có thểđược xây dựng và sử dụng ở lớp ứng dụng.

Đỗ Thị Tuyết ĐT6-K48 9 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

1.2.3. Hai cấu trúc đặc trưng của mạng cảm biến

1.2.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 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ạng cảm biến

1.2.3.2. Cấu trúc tầng

Trong cấu trúc tầng (tiered architecture) (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 hop 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 ở một mức xác định thực hiện các nhiệm vụđã định sẵn.

Đỗ Thị Tuyết ĐT6-K48 10 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Hình 1.5 Cấu trúc tầng của mạng cảm biến

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, 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, và cấp trên cùng thực hiện phân phối dữ liệu (hình 1.6). Cấp 0: Cảm nhận Cấp 1 : Tính toán Cấp 2: Phân phối

Hình 1.6 Cấu trúc mạng phân cấp chức năng theo lớp 11

11 Đỗ Thị Tuyết ĐT6-K48 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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í chi 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 tất cả 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 làm nhiệm vụ cảm nhận, một số lượng nhỏ hơn các nút có chi phí cao hơn được chỉđịnh để phân tích dữ liệu, định vị và đồng bộ thời gian, chi phí cho toàn mạng sẽ giảm đi.

-Mạng cấu trúc tầng sẽ có tuổi thọ cao hơn cấu trúc mạng phẳng. Khi cần phải tính toán nhiều thì một bộ xử lý nhanh sẽ hiệu quả hơn, phụ thuộc vào thời gian yêu cầu thực hiện tính toán. Tuy nhiên, với các nhiệm vụ cảm nhận cần hoạt động trong khoảng thời gian dài, các nút tiêu thụ ít năng lượng phù hợp với yêu cầu xử lý tối thiểu sẽ hoạt động hiệu quả hơn. Do vậy với cấu trúc tầng mà các chức năng mạng phân chia giữa các phần cứng đã được thiết kế riêng cho từng chức năng sẽ làm tăng tuổi thọ của mạng.

-Vềđộ tin cậy: mỗi mạng cảm biến phải phù hợp với với số lượng các nút yêu cầu thỏa mãn điều kiện về băng thông và thời gian sống. Với mạng cấu trúc phẳng, qua phân tích người ta đã xác định thông lượng tối ưu của mỗi nút trong mạng có n nút là

⎛

W n

⎞

⎟⎠

, trong đó W là độ rộng băng tần của kênh chia sẻ. Do đó khi kích cỡ mạng tăng

⎜⎝

lên thì thông lượng của mỗi nút sẽ giảm về 0.

-Việc nghiên cứu các mạng cấu trúc tầng đem lại nhiều triển vọng để khắc phục vấn đề này. Một cách tiếp cận là dùng một kênh đơn lẻ trong cấu trúc phân cấp, trong đó các nút ở cấp thấp hơn tạo thành một 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 ⎜

Đỗ Thị Tuyết ĐT6-K48 12 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

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 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 với nhau.

Tóm lại, việc tương thích giữa 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 người ta đang tập trung nghiên cứu về các tiện ích về 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 chức năng cập nhật và tìm kiếm. Hiện nay cũng đang có rất nhiều mô hình tìm kiếm địa chỉ trong mạng cấu trúc tầng.

1.3. Ứng dụng

Như trên ta đã đề cập đến các lĩnh vực ứng dụng mạng cẳm biến không dây.Cụ thể ta sẽ xem xét kỹ một sốứng dụng như sau để hiểu rõ sự cần thiết của mạng cảm biến không dây.

Các mạng cảm biến có thể bao gồm nhiều loại cảm biến khác nhau như cảm biến động đất, cảm biến từ trường tốc độ lấy mẫu thấp, cảm biến thị giác, cảm biến hồng ngoại, cảm biến âm thanh, radar... mà có thể quan sát vùng rộng các điều kiện xung quanh đa dạng bao gồm:

Nhiệt độ.

Độẩm.

Sự chuyển động của xe cộ.

Điều kiện ánh sáng.

Áp suất.

Sự hình thành đất.

Mức nhiễu. ¾

Đỗ Thị Tuyết ĐT6-K48 13 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Sự có mặt hay vắng mặt một đối tượng nào đó.

Mức ứng suất trên các đối tượng bị gắn.

Đặc tính hiện tại như tốc độ, chiều và kích thước của đối tượng.

Các nút cảm biến có thểđược sử dụng để cảm biến liên tục hoặc là phát hiện sự kiện, số nhận dạng sự kiện, cảm biến vị trí và điều khiển cục bộ bộ phận phát động. Khái niệm vi cảm biến và kết nối không dây của những nút này hứa hẹn nhiều vùng ứng dụng mới. Chúng ta phân loại các ứng dụng này trong quân đội, môi trường, sức khỏe, gia đình và các lĩnh vực thương mại khác.

1.3.1. Ứng dụng trong quân đội

Mạng cảm biến không dây có thể tích là một phần tích hợp trong hệ thống điều khiển quân đội, giám sát, giao tiếp, tính toán thông minh, trinh sát, theo dõi mục tiêu. Đặc tính triển khai nhanh, tự tổ chức và có thể bị lỗi của mạng cảm biến làm cho chúng hứa hẹn kỹ thuật cảm biến cho hệ thống trong quân đội. Vì mạng cảm biến dựa trên sự triển khai dày đặc của các nút cảm biến có sẵn, chi phí thấp và sự phá hủy của một vài nút bởi quân địch không ảnh hưởng đến hoạt động của quân đội cũng như sự phá hủy các cảm biến truyền thống làm cho khái niệm mạng cảm biến là ứng dụng tốt đối với chiến trường. Một vài ứng dụng quân đội của mạng cảm biến là quan sát lực lượng, trang thiết bị, đạn dược, theo dõi chiến trường do thám địa hình và lực lượng quân địch, mục tiêu, việc đánh giá mức độ nguy hiểm của chiến trường, phát hiện và do thám việc tấn công bằng hóa học, sinh học, hạt nhân.

Giám sát lực lượng , trang thiết bị và đạn dược:

Các người lãnh đạo, sĩ quan sẽ theo dõi liên tục trạng thái lực lượng quân đội, điều kiện và sự có sẵn của các thiết bị và đạn dược trong chiến trường bằng việc sử dụng mạng cảm biến. Quân đội, xe cộ, trang thiết bị và đạn dược có thể gắn liền với các thiết bị cảm biến nhỏđể có thể thông báo về trạng thái. Những bản báo cáo này

Đỗ Thị Tuyết ĐT6-K48 14 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

được tập hợp lại tại các nút sink để gửi tới lãnh đạo trong quân đội. Dữ liệu cũng có thể được chuyển tiếp đến các cấp cao hơn.

Giám sát chiến trường: địa hình hiểm trở, các tuyến đường , đường mòn và các chỗ eo hẹp có thể nhanh chóng được bao phủ bởi mạng cảm biến và gần như có thể theo dõi các hoạt động của quân địch. Khi các hoạt động này được mở rộng và kế hoạch hoạt động mới được chuẩn bị một mạng mới có thểđược triển khai bất cứ thời gian nào khi theo dõi chiến trường.

Giám sát địa hình và lực lượng quân địch: mạng cảm biến có thể được triển khai ở những địa hình then chốt và một vài nơi quan trọng, các nút cảm biến cần nhanh chóng cảm nhận các dữ liệu và tập trung dữ liệu gửi về trong vài phút trước khi quân địch phát hiện và có thể chặn lại chúng. Hình (1.7) cho ta hình dung được vềứng dụng của mạng cảm biến trong hoạt động quân đội.

Hình 1.7 Ứng dụng trong quân đội p h

Đỗ Thị Tuyết ĐT6-K48 15 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Đánh giá sự nguy hiểm của chiến trường: trước và sau khi tấn công mạng cảm biến có thểđược triển khai ở những vùng mục tiêu để nắm được mức độ nguy hiểm của chiến trường.

Phát hiện và thăm dò các vụ tấn công bằng hóa học, sinh học và hạt nhân. Trong các cuộc chiến tranh hóa học và sinh học đang gần kề, một điều rất quan trọng là sự phát hiện đúng lúc và chính xác các tác nhân đó. Mạng cảm biến triển khai ở những vùng mà được sử dụng như là hệ thống cảnh báo sinh học và hóa học có thể cung cấp các thông tin mang ý nghĩa quan trọng đúng lúc nhằm tránh thương vong nghiêm trọng.

1.3.2. Ứng dụng trong môi trường

Một vài ứng dụng môi trường của mạng cảm biến bao gồm theo dõi sự di cư của các loài chim, các động vật nhỏ, các loại côn trùng, theo dõi điều kiện môi trường mà ảnh hưởng đến mùa màng và vật nuôi; việc tưới tiêu, các thiết bịđo đạc lớn đối với việc quan sát diện tích lớn trên trái đất, sự thăm dò các hành tinh, phát hiện sinh-hóa, nông nghiệp chính xác, quan sát môi trường, trái đất, môi trường vùng biển và bầu khí quyển, phát hiện cháy rừng, nghiên cứu khí tượng học và địa lý, phát hiện lũ lụt, sắp đặt sự phức tạp về sinh học của môi trường và nghiên cứu sự ô nhiễm.

Phát hiện cháy rừng: vì các nút cảm biến có thểđược triển khai một cách ngẫu nhiên, có chiến lược với mật độ cao trong rừng, các nút cảm biến sẽ dò tìm nguồn gốc của lửa để thông báo cho người sử dụng biết trước khi lửa lan rộng không kiểm soát được. Hàng triệu các nút cảm biến có thểđược triển khai và tích hợp sử dụng hệ thống tần số không dây hoặc quang học. Cũng vậy, chúng có thểđược trang bị cách thức sử dụng công suất có hiểu quả như là pin mặt trời bởi vì các nút cảm biến bị bỏ lại không có chủ hàng tháng và hàng năm. Các nút cảm biến sẽ cộng tác với nhau để thực hiện cảm biến phân bố và khắc phục khó khăn, như các cây và đá mà ngăn trở tầm nhìn thẳng của cảm biến có dây. nguy hi

Đỗ Thị Tuyết ĐT6-K48 16 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Hình 1.8 Ứng dụng trong môi trường

Phát hiện lũ lụt: một ví dụđó là hệ thống báo động được triển khai tại Mỹ. Một vài loại cảm biến được triển khai trong hệ thống cảm biến lượng mưa, mức nước, thời tiết. Những con cảm biến này cung cấp thông tin để tập trung hệ thống cơ sở dữ liệu đã được định nghĩa trước.

1.3.3. Ứng dụng trong chăm sóc sức khỏe

Một vài ứng dụng về sức khỏe đối với mạng cảm biến là giám sát bệnh nhân, các triệu chứng, quản lý thuốc trong bệnh viện, giám sát sự chuyển động và xử lý bên trong của côn trùng hoặc các động vật nhỏ khác, theo dõi và kiểm tra bác sĩ và bệnh nhân trong bệnh viện.

Theo dõi bác sĩ và bệnh nhân trong bệnh viện : mỗi bệnh nhân được gắn một nút cảm biến nhỏ và nhẹ, mỗi một nút cảm biến này có nhiệm vụ riêng, ví dụ có nút cảm biến xác định nhịp tim trong khi con cảm biến khác phát hiện áp suất máu, bác sĩ cũng có thể mang nút cảm biến để cho các bác sĩ khác xác định được vị trí của họ trong bệnh viện. ụ

Đỗ Thị Tuyết ĐT6-K48 17 Đồ án tốt nghiệp Chương 1 Tổng quan về mạng cảm biến

Hình 1.9 Ứng dụng trong chăm sóc sức khỏe

1.3.4. Ứng dụng trong gia đình

Trong lĩnh vực tựđộng hóa gia đình, các nút cảm biến được đặt ở các phòng để đo nhiệt độ. Không những thế, chúng còn được dùng để phát hiện những sự dịch chuyển trong phòng và thông báo lại thông tin này đến thiết bị báo động trong trường hợp không có ai ở nhà.

1.4. Kết luận

Chương này đã giới thiệu tổng quan về kiến trúc mạng cảm biến và các ứng dụng trong nhiều lĩnh vực dân sự cũng như quân sự, y tế, môi trường... Qua đó ta thấy rõ được tầm quan trọng của mạng cảm biến với cuộc sống của chúng ta. Với sự phát triển nhanh chóng của công nghệ ngày nay sẽ hứa hẹn thêm nhiều ứng dụng mới của mạng cảm biến. ụ

Đỗ Thị Tuyết ĐT6-K48 18 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Chương 2. Các giao thức đặc trưng của mạng cảm biến

2.1. Giới thiệu về giao thức đặc trưng trong mạng cảm biến

Trong chương trước chúng ta đã xem xét về các khái niệm tổng quan nhất về mạng cảm biến. Chương này chúng ta sẽđi sâu vào tìm hiểu các giao thức đặc trưng của mạng cảm biến. Đó là hai giao thức đồng bộ thời gian và giao thức vị trí. Hai giao thức này có ý nghĩa rất quan trọng trong mạng cảm biến.

2.2. Giao thức đồng bộ thời gian

Vấn đề thời gian rất quan trọng trong nhiều ứng dụng và giao thức trong mạng cảm biến. Các nút có thểđo thời gian bằng cách dùng các xung đồng hồ cục bộ lấy từ các bộ dao động. Bởi vì các pha ngẫu nhiên làm dịch chuyển và làm trôi tốc độ của bộ dao động, do vậy thời gian cục bộ của các nút sẽ bắt đầu sai khác đi làm cho mạng mất đi sựđồng bộ. Do vậy việc đồng bộ thời gian có vai trò rất quan trọng trong hoạt động của mạng cảm biến.

Đồng bộ thời gian là phương thức cho phép các thực thể riêng biệt trong một nhóm đồng bộ xung đồng hồ của chúng hoặc đồng bộ với thời gian toàn cầu phối hợp (UTC). Phần này sẽ giải thích tại sao cần đồng bộ thời gian và đưa ra một số giao thức đồng bộ khác nhau.

Tại sao cần đồng bộ thời gian trong mạng cảm biến:

Mạng cảm biến cần liên kết với thế giới thực để biết khi nào một hiện tượng xảy ra.

Dịch vụ cơ bản chính của mạng cảm biến là tích hợp dữ liệu. Do đó cần đồng bộ giữa các nút để có thể tích hợp dữ liệu truyền đến Sink

Một vài giao thức yêu cầu đồng bộ thời gian: quản lý cấu hình mạng. Ch

Đỗ Thị Tuyết ĐT6-K48 19 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Các nút cảm biến thường nhỏ, giá thành thấp nên bộ dao động thường không chính xác, hơn nữa chúng bị giới hạn về năng lượng nên thường có chếđộ sleep để tiết kiệm năng lượng.

Sau đây, ta xét ví dụđơn giản minh hoạ sự cần thiết của độ chính xác về thời gian như sau (hình 2.1)

Hình 2.1 Xác định góc đến của âm thanh ở xa bởi một dãy sensor

Một sóng âm phát ra từ một nguồn âm ở khoảng cách xa tác động đến một dãy các sensor và ta có thểước đoán góc tới trong trường hợp này. Mỗi một sensor đều biết vị trí của chúng và lưu lại thời gian đến của âm thanh. Trong trường hợp cụ thể như hình vẽ, góc θ có thểđược xác định khi d và x đã biết, dùng công thức lượng giác

x= d × sinθ do đó θ= arcsin x . Khoảng cách giữa các sensor có thể xác định từ các vị

d

trí đã biết của các sensor và x có thể thu được từđộ lệch thời gian Δt giữa các lần cảm nhận của sensor và vận tốc của âm thanh c ≈ 330m / s , sử dụng công thức x = c ×Δt . Cho d = 1m và Δt = 0.001s thì θ≈ 0.336 (radians). Nếu đồng hồ của các sensor chính xác đến 500 μs , sự sai lệch về thời gian thực có thểở khoảng giữa 500 và 1500 μs , và vì thế giá trị của góc θ có thể thay đổi trong khoảng θ≈ 0.166 và θ≈ 0.518 . Vì thế,

một sai số nhỏ trong khi đồng bộ thời gian có thể dẫn tới độ lệch đáng kể khi ước đoán. http://www.ebook.edu.vn

Đỗ Thị Tuyết ĐT6-K48 20 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Cần phải chú ý rằng thời gian dùng trong mạng cảm biến phải là thời gian tự nhiên (physical time), đó là hai nút cảm biến phải có sự cảm nhận như nhau về 1s và 1s của một nút cảm biến càng gần với 1s trong thời gian thực (real time) hoặc thời gian toàn cầu phối hợp (coordinated universal time - UTC) càng tốt. Thời gian tự nhiên phải được phân biệt với khái niệm về thời gian logic (logical time) là thời gian mà cho phép quyết định việc sắp xếp các sự kiện trong hệ thống phân bố nhưng không cần thiết phải chỉ ra bất kì sự liên quan nào đến thời gian thực.

2.2.1. Đồng hồ các nút cảm biến và sự chính xác

Hầu hết các thiết bịđồng hồ của các nút cảm biến và máy tính đều có cấu tạo giống nhau. Mỗi nút có một bộ dao động ở một tần số xác định và một máy đếm xung dao động. Phần mềm của các nút chỉ truy nhập tới giá trị của bộđếm này và thời gian giữa hai lần tăng này quyết định cách giải quyết vấn đề thời gian: các sự kiện xảy ra giữa hai lần tăng này không thểđược phận biệt từ các nhãn thời gian của chúng.

Bộ dao động thường có độ trôi, đó là sự dịch ngẫu nhiên so với tần số trên danh nghĩa, hay còn gọi là độ lệch đồng hồ. Điều này phụ thuộc vào sự không trong suốt của tinh thể, hay các điều kiện môi trường như áp suất, nhiệt độ... do vậy việc triển khai mạng cảm biến trên thực tế khác nhiều so với trong phòng thí nghiệm. Độ lệch đồng hồ được đo bằng ppm (parts per million), nó đưa ra con số về số dao động thêm vào hoặc số dao động bị mất mà đồng hồ tạo ra trong lượng thời gian cần cho 1 triệu dao động ở tốc độ danh nghĩa.

Tần số dao động thay đổi theo thời gian. Có 2 kiểu thay đổi:

Thay đổi ngắn hạn: do thay đổi nhiệt độ, do thay đổi trong điện áp nguồn cung cấp, áp suất không khí...

Thay đổi dài hạn: do sự lão hóa của các bộ dao động

Người ta thường giả định tần số các bộ dao động là ổn định vừa phải trong phạm vi từ vài phút đến vài chục phút. Điều này cũng nói lên rằng các thuật toán đồng ằ

Đỗ Thị Tuyết ĐT6-K48 21 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

bộ thời gian phải đồng bộ lại vài phút một lần để theo kịp sự thay đổi của tần số. Vì thế giao thức đồng bộ thời gian là rất cần thiết.

Một điều cần quan tâm nữa là bao lâu thì giao thức đồng bộ thời gian chạy một lần? Giả sử một nút chỉđiều chỉnh độ dịch pha Φi và tốc độ trôi của dao động là x ppm

cốđịnh, độ chính xác yêu cầu là δ s, thì sau khoảng thời gian khoảng 8 s cần

x ×10−6 thiết phải đồng bộ lại. Với x = 20ppm, độ chính xác là 1s thì sau 50s phải đồng bộ lại. Các mô hình hiện đại ngày nay đều cố gắng ước lượng chính xác không chỉ Φi mà còn

θi để kéo dài chu kì trước khi phải đồng bộ lại. Một lần nữa phải nhấn mạnh rằng quá trình đồng bộ một lần không có hiệu quả vì tốc độ trôi thay đổi, và thường thì ta giới hạn được tốc độ trôi lớn nhất ρi > 0 mà thỏa mãn

1d

1+ρ ≤ dt Hi (t) ≤ 1+ρi (2.1)

Công thức này còn dùng để xác định tần sốđồng bộ lại.

2.2.2. Đồng bộ thời gian trong mạng cảm biến

Trong mạng cảm biến có một sốđặc điểm mà ảnh hưởng đến yêu cầu thiết kế của các thuật toán đồng bộ thời gian:

Thuật toán phải phù hợp với phạm vi mạng mutilhop rộng lớn, các nút bị ràng buộc về mặt năng lượng. Yêu cầu về phạm vi bao hàm cả số lượng các nút trong mạng và mật độ các nút.

Yêu cầu vềđộ chính xác có thể thay đổi khác nhau từ mili giây cho đến hàng giây.

Không sử dụng thêm phần cứng chỉ giành cho mục đích đồng bộ vì tốn chi phí và năng lượng thêm vào cho phần phụđó.

Mức độ di động là rất thấp. dt

Đỗ Thị Tuyết ĐT6-K48 22 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Hầu như không có giới hạn trên cốđịnh về trễ truyền gói vì phụ thuộc lớp MAC, lỗi các gói, và truyền lại.

Trễ truyền giữa hai nút hàng xóm là không đáng kể. Một khoảng cách 30m cần 10-7s vì vận tốc ánh sang là c =3.108m/s.

Có rất nhiều giao thức đồng bộ thời gian truyền thống cố gắng giữ việc đồng bộ giữa các nút ở mọi thời điểm nhưng lại không quan tâm đến năng lượng và cấu hình mạng cho nên không thể áp dụng vào mạng cảm biến. Vì đặc điểm của mạng cảm biến cho nên giao thức đồng bộ thời gian cần chú ý về các vấn đề vềđộ chính xác, chi phí năng lượng và các yêu cầu về bộ nhớ.

Phương pháp cơ bản đểđồng bộ thời gian trong mạng cảm biến là cộng tác giữa các nút trong toàn mạng. Thiết lập mối liên hệ cặp dây (pair-wise) giữa các nút trong mạng sau đó mở rộng ra toàn mạng.

Có hai cách thiết lập sự cộng tác giữa hai nút trong mạng đó là đồng bộ giữa bên gửi và bên nhận (Sender-Receiver) và giữa bên nhận và bên nhận (Receiver-Receiver). Đồng bộ giữa bên gửi và bên nhận yêu cầu liên kết hai chiều giữa hai nút lân cận. Trong phương pháp đồng bộ giữa bên nhận và bên nhận, nhiều nút nhận của các gói có nhãn thời gian như nhau đồng bộ với nhau mà không yêu cầu đồng bộ với bên gửi ( mốc gửi gói tin broadcast đến hai nút A và B, sau đó A và B tự đồng bộ với nhau không cần đến mốc). Hai phương pháp này được miêu tả như hình (2.2).

Hình 2.2 Đồng bộ bên phát/bên nhận và bên nhận/bên nhận. không có gi

Đỗ Thị Tuyết ĐT6-K48 23 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

2.2.2.1. Giao thức đồng bộ giữa bên nhận và bên phát

Trong giao thức này, một nút gọi là bên nhận, trao đổi gói dữ liệu với nút khác gọi là bên phát, làm cho bên nhận đồng bộ với đồng hồ của bên phát. Giao thức đồng bộ giữa bên nhận và bên phát nói chung là đòi hỏi đường nối 2 chiều giữa các nút lân cận.

Điển hình của giao thức đồng bộ giữa bên phát và bên nhận là Lightweight time synchronization protocol (LTS). Giao thức này đưa ra bởi VAN GREUNEN và RABAEY đểđồng bộđồng hồ của mạng với đồng hồ của các nút tham chiếu, ví dụ như có thể có bộ nhận GPS. Trong khi hoạt động nó điều khiển các nút để sử dụng năng lượng hiệu quả và đạt được độ chính xác cao, và đưa ra những giới hạn tương đối chính xác về các phần cứng cơ sở và các hệ thống. LTS không yêu cầu phải update đồng hồ cục bộ và nó cũng không ước lượng tốc độ trôi thực sự.

LTS chia quá trình đồng bộ làm 2 giai đoạn:

-Giao thức đồng bộ 2 chiều đểđồng bộ 2 nút lân cận.

-Để giữ các nút hoặc một tập hợp các nút cần quan tâm đồng bộ theo một tham chiếu chung, LTS xây dựng một cây phân tán từ các nút tham chiếu đến tất cả các nút. Nếu các lỗi khi đồng bộ single-hop là độc lập, phân phối y hệt nhau và có trung bình là O thì các nút lá của cây cũng được đồng bộ với lỗi bằng O nhưng sự thay đổi là tổng các thay đổi dọc theo đường truyền từ nút tham chiếu đến nút lá. Vì vậy sự thay đổi này có thể tối thiểu hoá bằng việc tìm ra cây phân tán có chiều cao nhỏ nhất.

Đồng bộ 2 chiều

Đầu tiên chúng ta sẽ nghiên cứu vềđồng bộ hai chiều (hình 2.4)

Sau khi quá trình đồng bộ lại được khởi động ở nút i, gói dữ liệu yêu cầu đồng bộđược định dạng tại thời điểm t1 với thời gian Li(t1). Nút i điều khiển các gói qua hệ thống hoạt động và các ngăn xếp. Trễđường truyền có thể biến thiên rất nhiều. Khi nút i gửi bit đầu tiên tại thời điểm t2, nút j nhận bit cuối cùng của gói tại t3 = t2 +τ + tP ,

Đỗ Thị Tuyết ĐT6-K48 24 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

trong đó τ là trễđường truyền và tP là thời gian truyền gói (chiều dài của gói tính theo bit).

Hình 2.3 Hoạt động của việc đồng bộ bên phát/bên nhận

Sau đó một thời gian, tại thời điểm t4, gói dữ liệu đến được báo hiệu đến ứng dụng hoặc hệ thống hoạt động của nút j qua một quá trình ngắt, sau đó được đánh dấu ờ

Đỗ Thị Tuyết ĐT6-K48 25 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

tại thời điểm t5 với thời gian Lj(t5). Tại t6, nút j định dạng gói phúc đáp với thời gian Lj(t6), và điều khiển gói đó đến hệ thống hoạt động của nó và ngăn xếp mạng. Gói này bao gồm cả thời gian trước đó là Lj(t5) và Li(t1). Nút i ngừng nhận gói vào thời điểm t7 (t6 cộng với mào đầu của mạng hoặc hệ thống hoạt động) và đánh dấu tại thời điểm t8 với thời gian Li(t8). Bây giờ ta sẽ phân tích vì sao nút i lại nhận ra sự hiệu chỉnh của nó. Để có O =Δ(t1):= Li (t ) − Lj (t1) , chúng ta giả sử không có bất kì sự trôi nào giữa các

1 *

đồng hồ trong khoảng thời gian từ t1 đến t8, do đó O =Δ(t*) với các nút t ∈[t1,t8 ], và trên thực tế nút i ước đoán O bằng việc ước đoán Δ(t5).

Từ hình vẽ ta thấy nhãn thời gian Lj(t5) đánh dấu sự quay lại của nút i, có thể xảy ra bất kì lúc nào trong khoảng từ t1 đến t8. Tuy nhiên chúng ta có thể làm giảm sự không xác định này bằng các nhận xét sau:

Chỉ có một độ trễđường truyền τ cộng với thời gian truyền gói tP giữa t1 và t5

Chỉ có thêm một khoảng τ+ tP giữa t5 và t8 đối với gói phúc đáp. Với các nút tĩnh chúng ta có thể giả thiết rằng trễđường truyền là như nhau theo cả hai hướng.

Thời gian giữa t5 và t6 cũng được tính bởi hiệu Lj (t6) − Lj (t5).

Do vậy, có thể giảm sự không chính xác của t5 đến khoảng

I =[Li (t1) +τ + tP , Li (t8) −τ− tP −(Lj (t6) − Lj (t5))] . Nếu chúng ta giả sử thời gian sử dụng trong hệ thống hoạt động và ngăn xếp mạng, khoảng ngắt cũng như là trễđường truyền là như nhau theo hai hướng, thì từ nút i sẽ suy ra nút j sẽ có Lj(t5) tại thời điểm (xét so với nút i)

Li (t5) = Li (t1) +τ+ tP + Li (t8) −τ − tp −(Lj (t6) − Lj (t5 )) (2.2)2

Vì thế, 5

Đỗ Thị Tuyết ĐT6-K48 26 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

O =Δ(t5) = Li (t5) − Lj (t5) = Li (t8) + Li (t1) − Lj (t6) − Lj (t5 ) (2.3)

2

Bây giờ nút i có thểđiều chỉnh đồng hồ cục bộ bằng việc gắn thêm độ lệch O vào. Bằng cách này nút i sẽđồng bộ với thời gian cục bộ của nút j. Khi mục đích của việc gắn thêm này là để cho nút j về O thì phải cần thêm gói thứ 3, gửi từ i đến j và bao gồm cả O. Trong trường hợp này thì toàn bộ quá trình đồng bộ cần 3 gói.

I

Sai sốđồng bộ cao nhất của mô hình này là nếu τ và tP có độ chính xác cao.

2 Sai sốđồng bộ thực sự có thể do các khoảng ngắt khác nhau ở i và j, đến các thời điểm khác nhau giữa giữa việc ngắt để nhận một gói và dánh dấu thời gian gói đó, và các thời gian truy nhập kênh khác nhau. Những sự không chính xác này có thể giảm đáng kể nếu nút yêu cầu có thểđánh dấu thời gian các gói của nó càng chậm càng tốt, tốt nhất là ngay trước khi truyền hoặc ngay sau khi chiếm được đường truyền.

Đồng bộ trong toàn mạng

Nhờ có khả năng đồng bộ theo hai chiều, LTS giải quyết được nhiệm vụđồng bộ tất cả các nút trong toàn mạng với nút tham chiếu. Nếu một nút i nào đó cách nút tham chiếu một khoảng là hi hop và nếu lỗi đồng bộ thông thường phụ thuộc vào các thông số μ= 0 và σ '= 2σ ở mỗi hop, và nếu các nút là độc lập với nhau, lỗi đồng bộ

của của i phụ thuộc vào phương sai σi 2 =4hiσ 2. Với các nhận xét cơ bản này mục đích của LTS là xây dựng một cây phân tán có chiều cao nhỏ nhất và chỉ cần đồng bộ các cặp nút dọc theo cạnh của cây. Nếu quá trình đồng bộ dọc theo cây phân tán mất nhiều thời gian, độ trôi giữa các đồng hồ sẽ gây ra thêm sai số.

LTS multihop tập trung

Nút chuẩn (ví dụ như một nút với bộ nhận GPS) tạo nên cây phân tán T và bắt đầu đồng bộ: đầu tiên đồng bộ nút chuẩn với các nút con của T, sau đó các nút con với các nút con, và cứ tiếp tục như thế. Vì vậy mỗi một nút cần phải biết các nút con của nó. (

Đỗ Thị Tuyết ĐT6-K48 27 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Các nút tham chiếu cũng cần phải đồng bộ lại tần sốđể bù cho độ trôi. Người ta cho rằng các nút tham chiếu cần phải có 4 tham số: chiều cao lớn nhất h của cây phân tán, tốc độ trôi lớn nhất ρ phải thoả mãn cho tất cả các nút trong mạng, độ lệch chuẩn

của mỗi hop là 2σ (đã nói ở trên), và độ chính xác mong muốn là δ . Mục đích là để luôn luôn có sai sốđồng bộở các nút lá luôn nhỏ hơn δvới độ chính xác là 99%. Ngay sau khi đồng bộ lại, độ chính xác của nút lá nhỏ hơn h × 2.3× 2 ×σ và nó có thể tăng đến mức δ. Với độ trôi lớn nhất ρ , quá trình này mất một khoảng thời gian là δ− 2 ×2.3× h ×σ

. Chu kỳđồng bộ phải được chọn sao cho nhỏ hơn độ trôi xảy ra trong

ρquá trình đồng bộ lại đơn, có thể phá hỏng độ chính xác ban đầu 2.3× 2 ×h ×σ .

Vấn đề chủ yếu ởđây là chi phí. Quá trình đồng bộđơn theo hai chiều cần 3 gói và như vậy việc đồng bộ cả mạng bao gồm n nút sẽ cần 3n nút, khi không tính đến lỗi kênh hoặc xung đột. Thêm vào đó là nguồn năng lượng đáng kểđể tạo nên cây phân tán, và nó cần phải lặp lại quá trình này sau mỗi lần đồng bộđể chịu đựng được các sai số.

Do những lý do trên ta thấy được việc cần thiết có các nút tham chiếu multiple, nếu một nút bị hỏng hoặc nếu mạng bị phân chia, thì các nút khác có thể thay thế. Một giao thức chủ rất hữu dụng để hỗ trợ các nút tham chiếu động.

LTS multihop phân bố

LTS multihop phân bố không xây dựng cây phân tán, nhưng mỗi nút đều nhận dạng được số lượng các nút tham chiếu dọc theo đường đi thích hợp của chúng. Đó là nhiệm vụ của các nút để thiết lập đồng bộ lại theo chu kỳ.

Ta hãy xem xét trường hợp ở hình 2.4 và cho rằng nút 1 muốn đồng bộ với nút tham chiếu R. Nút 1 phát yêu cầu đồng bộđến R theo 1 chuỗi đồng bộ theo 2 hướng: nút 4 đồng bộ với nút R, nút 3 đồng bộ với nút 4, và cứ thếđến nút 1. l

Đỗ Thị Tuyết ĐT6-K48 28 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Hình 2.4 LTS multihop phân bố

Có 2 điều cần chú ý ởđây là:

-Kết quả là nút 2, 3 và 4 cũng được đồng bộ với nút R

-Do có độ chính xác yêu cầu δ và cùng tốc độ trôi ρ cho tất cả các nút, tần số

đồng bộ lại đối với nút i cách nút tham chiếu hi hop là δ− 4 × 2.3× hi ×σ . Vì thế trên

ρ

hình ta thấy nút 1 và nút 6 có chu kỳđồng bộ lại ngắn nhất. Nếu 2 nút này luôn yêu cầu đồng bộ với nút R thì các nút 2, 3, 4 và 5 không bao giờ tự yêu cầu đồng bộ lại.

Một nút phải chọn nút tham chiếu gần nhất để giảm tối đa sai số. Trong cách này không cần phải xây dựng cây có trọng số nhỏ nhất mà nhiệm vụ của giải thuật này là tìm đường đi tốt nhất. Đối với các mạng và giao thức định tuyến xác định ta gặp phải vấn đề về chu trình đồng bộ/định tuyến. Từ những ví dụ trước ta thấy các nút có thể tận dụng những thuận lợi khi quá trình đồng bộđang diễn ra. Như trong ví dụ nút 5 ở hình

(2.4) . Thay vì đồng bộ nút 5 độc lập với nút tham chiếu R (có thể làm cho nút 3 và nút 4 tựđông yêu cầu đồng bộ), nút 5 có thể gửi yêu cầu đến tất cả các nút ở lân cận tiếp tục đồng bộ. Nếu có bất kỳ phản hồi nào, nút 5 có thểđợi một khoảng thời gian và sau đó sẽđồng bộ với nút phản hồi.

Các đặc điểm của LTS được kiểm tra bằng việc mô phỏng 500 nút phân bố ngẫu nhiên trong vòng 120m (hình chữ nhật 120m, mỗi nút có khả năng truyền trong hoặc tham gia vào quá trình đang đồng bộ (giảm số lượng mào đầu khoảng 15 đến 60%). Tuy nhiên, nếu chỉ có một số lượng nút được đồng bộ, các giải thuật phân bố có thể đ

Đỗ Thị Tuyết ĐT6-K48 29 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

giới hạn mào đầu của nó đến các vùng quan tâm và lưu trữ năng lượng của tất cả các nút trong khi các giải thuật tập trung bao gồm tất cả các nút và vì thế nó có chi phí cố định bất kể khi giao thức đồng bộ thời gian có được dùng hay không.

2.2.2.2. Giao thức đồng bộ giữa bên nhận và bên nhận

Trong giao thức này nhiều bên nhận của các gói có nhãn thời gian như nhau đồng bộ với nhau nhưng không đồng bộ với bên gửi. Chúng ta xem xét một giao thức cơ bản đó là đồng bộ quảng bá tham chiếu RBS (Reference broadcast synchronization).

Giao thức này bao gồm hai thành phần: thành phần đầu tiên là một tập hợp các nút nằm trong vùng broadcast đơn (ví dụ như một tập hợp các nút có thể nghe thấy nhau) đánh giá xung đồng hồ của các nút ngang hàng với chúng. Thành phần thứ hai cho phép liên kết các nhãn thời gian giữa các nút ở xa với một vài khu vực broadcast giữa chúng. Chúng ta sẽ giải thích lần lượt mỗi thành phần này.

Đồng bộ trong một khu vực broadcast:

Ý tưởng cơ bản như sau: Bên gửi sẽ gửi theo chu kỳ một gói (không cần thiết đánh dấu nhãn thời gian) vào kênh broadcast và tất cả các bên nhận sẽđánh dấu nhãn thời gian cho gói này. Các bên nhận trao đổi nhãn thời gian của chúng và có thể sử dụng dữ liệu này để biết được đồng hồ của nút hàng xóm. Bằng việc lặp lại quá trình này các nút không chỉ biết vềđộ lệch pha của nhau mà còn cả tốc độ trôi nữa. Các nút không điều chỉnh đồng hồ cục bộ của nó nhưng đối với mỗi nút hàng xóm nó xây dựng một bảng lưu trữ các tham số cần thiết để chuyển đổi giá trị xung đồng hồ.Ví dụ: xem hình (2.5 ).

Hai nút i và j muốn đồng bộ. Tại thời điểm t0, nút R broadcast một gói xung, bao gồm số nhận dạng R và một chuỗi số s. Nút i và j có một khoảng cách khác nhau tới R, do đó trễ truyền cũng khác nhau. Bit cuối đến nút i ở thời điểm t1,i đến nút j ở thời điểm t1,j và trễ truyền tương biến là τi và τj .Ở cả hai nút một ngắt nhận gói được tạo ra, ở thời điểm t2,j và t2,i đối với nút j và i. u tr

Đỗ Thị Tuyết ĐT6-K48 30 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Hình 2.5 Ví dụ về RBS

Sau một khoảng thời gian ngắn nữa, ở thời điểm t3,i nút i đánh dấu gói với nhãn thời gian cục bộ Li(t3,i); nút j cũng tương tự tạo ra nhãn Lj(t3,j). Sau đó nút i và nút j cùng trao đổi nhãn thời gian và nhận dạng của các gói xung (địa chỉ bên gửi, chuỗi số) tương ứng. Cả hai nút dễ dàng tính toán độ lệch pha tương đối của đồng hồ bằng việc giả sử t3,i = t3,j. Đặc biệt, nút i lưu trữ giá trị O(t3,i)=Li(t3,i)-Lj(t3,j) như là độ lệch pha trong bảng cục bộ mà không có sựđiều chỉnh đồng hồ của nó. Rõ ràng, sự sắp xếp này có thể thuận lợi từ việc có các bên nhận đánh dấu các nhãn thời gian của các gói đến nhanh đến mức có thể trong chu trình ngắt.

Thời gian giữa việc nhận bit cuối và đánh dấu nhãn thời gian của gói được gọi là độ thay đổi bên nhận (receiver uncertainty), được ký hiệu là δr,i và δr,j đối với nút i và j tương ứng.

Độ chính xác đạt được đối với mỗi xung đơn:

Rõ ràng, toàn bộ việc tính toán là chính xác tuyệt đối khi việc giả sử t3,i=t3,j thực sựđúng. Chúng ta sẽ phân tích ngắn gọn nguồn lỗi đồng bộ có thể như sau:

Trễđường truyền: Trong mạng cảm biến, khu vực broardcast thông thường nhỏ và trễ truyền của một gói có thể bỏ qua. Hơn nữa, đó chỉ là sự khác nhau giữa trễ ắ

Đỗ Thị Tuyết ĐT6-K48 31 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

truyền giữa nút i và nút j mà có ý nghĩa và sự khác nhau này có xu hướng thậm chí nhỏ hơn.

Trễ giữa việc nhận bit cuối cùng và tạo ra một ngắt nhận gói: điều này có thể tùy thuộc vào trễ xử lý phần cứng (giống như tính toán checksum) cũng như là khoảng thời gian ngắn tạo khối ngắt trong các trường hợp phân đoạn chủ yếu hoặc ngắt phục vụ có độưu tiên cao hơn. Hơn nữa, đó là sự khác nhau giữa nút i và j mà coi như là lỗi đồng bộ.

Trễ giữa ngắt nhận gói và đánh dấu nhãn thời gian gói: nếu nhãn thời gian được tạo ra ngay trong chu trình ngắt thì trễ này rất nhỏ. Độ dịch chuyển giữa việc đánh dấu nhãn thời gian và trao đổi nhãn thời gian quan sát được cũng góp phần tạo ra lỗi đồng bộ. Thời gian càng trôi qua, lỗi này càng lớn.

So sánh với phương pháp đồng bộ thời gian giữa bên gửi/bên nhận thì thời gian yêu cầu của R đểđịnh dạng gói tin, chuyển qua hệđiều hành, phần mềm mạng, cũng như là trễ truy cập đường truyền là hoàn toàn không liên quan đến nhau vì điểm chung của việc tham chiếu của nút i và j là thời gian t0 mà gói xuất hiện trong kênh truyền.

Cách tạo ra khu vực broadcast:

Một trong những điểm không hạn chế của RBS là cách khu vực broadcast được tạo thành và cách nó có thểđảm bảo chắc chắn rằng một đường dẫn biến đổi thời gian thực tế tồn tại giữa hai nút mong muốn, nút cảm biến và sink.

Chúng ta hãy xem xét hai tình huống khác nhau sau: Trong tình huống một số lượng nút tĩnh hoạt động như là bên gửi xung chuyên dụng và cũng là bộ chuyển tiếp các gói. Những điều này được biểu diễn bằng vòng tròn trên hình. Các nút cảm biến thông thường là các nút hàng xóm trung gian được đồng bộ. Nút cảm biến đánh dấu nhãn thời gian của các gói xung và truyền sự quan sát của nó đến bên gửi xung mà tính toán mỗi cặp nút cảm biến độ lệch pha tương đối và tốc độ trôi, và rải rác các kết quả. Một khu vực broardcast là được rạo ra bởi phạm vi của xung bên gửi. Một nút cảm biến i chuyển tiếp một gói có hai tùy chọn: Nó có thể xác định các nút j khác trong ễ

Đỗ Thị Tuyết ĐT6-K48 32 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

cùng khu vực để chuyển tiếp gói đến. Nếu cả hai đều là nút hang xóm đơn bước nhảy thì nút i có thể chuyển đổi nhãn thời gian và gửi gói trực tiếp đến j. Điều này biểu thị bằng cung đặc trong hình (2.6). Trong trường hợp khác, nút i có thể yêu cầu bên gửi xung để chuyển tiếp gói đến nút j mà không thay đổi nó. Trong cả hai trường hợp, bên gửi xung không yêu cầu giữ bảng thông tin về hội thoại.

Hình 2.6 Chuyển tiếp gói dữ liệu và chuyển đổi nhãn thời gian

Nó có thể chuyển tiếp gói tới bên gửi xung. Đây là trách nhiệm bên gửi xung tìm kiếm một phần tử tiếp theo j và để chuyển đổi nhãn thời gian. Theo đó, bên gửi xung được yêu cầu giữ bảng với các tham số hội thoại.

Trong trường hợp khác, bên gửi xung không sử dụng đồng hồ cục bộ và do đó không cần thiết đồng bộ với các nút cảm biến của nó. Trong cả hai trường hợp khu vực broadcast được chọn lựa như sau:

Mỗi nút cảm biến là một thành viên của ít nhất một khu vực broadcast.

Khi một gói được truyền từ một nguồn đến nút sink trong khu vực broadcast khác, phải có một chuỗi các khu vực broadcast trên đường dẫn giữa nguồn và sink và hai khu vực broadcast phải chồng lấp lên một nút. Những nút gateway này (nút hình vuông có hai màu trên hình 2.6) biết các thông số hội thoại đối với tất cả các nút trong hai khu vực và theo đó có thể chuyển đổi nhãn thời gian. Ởđó phải có đủđộ chồng lấn đểđảm bảo chắc chắn có sự hiện diện của các nút gateway. Lý tưởng, giữa hai khu vực broadcast có nhiều hơn một nút gateway để cho phép một vài sự cân bằng khi chuyển tiếp tải.

Số các hội thoại cần thiết giữa một nguồn và một sink sẽ nhỏđể tránh sự mất mát độ chính xác, cái này được gọi là khu vực broadcast rộng lớn. Nói cách khác trong khu vực rộng lớn, có nhiều gói phải được trao đổi với công suất truyền lớn hơn phải n b

Đỗ Thị Tuyết ĐT6-K48 33 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

được sử dụng đểđạt được đến nút hàng xóm, làm tiêu hao năng lượng nhanh chóng hơn.

Điều này có thểđược xem xét như vấn đề phân cụm, với mục đích để tìm các cụm bị chồng lấp. Giao thức phân cấp cụm chuyên dụng cho mục được sử dụng ở [2]. Giao thức này cho phép điều chỉnh kích thước cụm để tìm được sự cân bằng tải giữa tối thiểu hóa các bước truyền và tối thiểu hóa lượng gói/công suất truyền.

Nếu không có các nút chuyên dụng hoặc khi tất cả các nút đều bào hồm bên gửi xung cần thiết được đồng bộ, khu vực broadcast phải nhỏ hơn và tất cả các thành viên trong khi vực broadcast phải là các nút hàng xóm một bước nhảy để có thể trao đổi xung quan sát cũng như chuyển tiếp gói dữ liệu. Khu vực broadcast là một tập hợp các nút. Trong tình huống này mỗi nút sẽ hoạt động như là một nút gửi xung, và việc quyết định chuyển tiếp bị giới hạn đến những nút hàng xóm này để chia sẻ ít nhất một khu vực broadcast với nút chuyển tiếp.

2.3. Giao thức vị trí

Trong nhiều trường hợp việc xác định vị trí trong thế giới tự nhiên của các nút trong mạng cảm biến là rất cần thiết, nó có ý nghĩa hoặc là mục đích của mạng cảm biến. Ví dụ như trong ứng dụng quan sát môi trường và khí tượng học, dữ liệu sẽ không còn có ý nghĩa nếu như không được đánh dấu thời gian và vị trí. Hay như trong các ứng dụng: theo dõi việc đóng gói hang, lưu trữ sách trong thư viện, theo dõi vị trí, tất cả các ứng dụng này đều cần xác định vị trí của các nút cả biến. Ngoài ra thông tin về vị trí cũng rất quan trọng trong một vài giao thức định tuyến, đặc biệt là định tuyến dựa vào vị trí.

Trong mạng cảm biến, có một số lượng rất lớn các nút, được triển khai một cách ngẫu nhiên trong khu vực quan sát. Việc xác định vị trí tuyệt đối của một nút thường rất khó. Chúng ta có thể trang bị thiết bị GPS cho các nút. Tuy nhiên cách này không khả thi đối với mạng cảm biến vì GPS tương đối đắt và không thể hoạt động trong môi trường đặc biệt như trong nhà, dưới lòng đất. ề

Đỗ Thị Tuyết ĐT6-K48 34 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

Hiện nay có hai kỹ thuật định vịđược xem xét chủ yếu trong mạng cảm biến là:

Định vị dựa vào mốc có sẵn.

Định vị dựa vào vị trí tương đối.

Cả hai kỹ thuật này đều sử dụng sựước lượng phạm vi và góc đối với việc định vị các nút cảm ứng thông qua cường độ tín hiệu thu được (received signal strength - RSS), thời gian đến (time of arrival - TOA), sự chênh lệch thời gian đến (time difference of arrival - TDOA), và góc tới (angle of arrival - AOA).

2.3.1. Định vị dựa vào mốc có sẵn

Phương pháp này giả sử như sau:

Có một vài con cảm biến đã biết vị trí.

Những nút này sẽ gửi tín hiệu mốc(dẫn đường) theo chu kỳ.

Các nút khác sẽđo tín hiệu này, sử dụng phép đo tam giác , đa trễ đểđánh giá vị trí.

RSSI (Receiver Signal Strength Indicator ) được dung để xác định sự tương quan tín hiệu với khoảng cách.

Hệ thống định vị ad hoc (AHLoS) đòi hỏi một vài nút phải có vị trí xác định qua GPS hoặc qua cấu hình điều khiển. Điều này cho phép các nút xác định được vị trí của chúng qua một quá trình hai pha: xếp loại và ước đoán. Trong pha xếp loại, mỗi một nút ước đoán phạm vi của các nút lân cận. Pha ước đoán sau đó cho phép các nút lân cận mà chưa xác định được vị trí dùng phạm vi được ước đoán trong pha xếp loại và vị trí của vật mốc để xác định vị trí của chúng.

Tuy nhiên phương pháp này chỉ phù hợp với tín hiệu RF, và rất nhạy cảm với vật cản, nhiễu đa đường, ảnh hưởng của môi trường (mưa,...). Hơn nữa tín hiệu RF phải có phạm vi tốt: khoảng vài chục mét. Ngoài ra ngưởi ta còn sử dụng RF và sóng siêu âm: nút mốc truyền tín hiệu RF và một sóng siêu âm tới bộ thu. Thời gian ạ

Đỗ Thị Tuyết ĐT6-K48 35 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

đến khác nhau giữa hai tín hiệu được sử dụng đểđo khoảng cách. Phạm vi lên tới 3 m, độ chính xác 2cm.

Tuy nhiên phương pháp giả sử rằng dấu hiệu của cột mốc ở những vị trí đã biết nhiều khi không thể áp dụng khi các nút cảm ứng triển khai ở những vùng mà khó có thể xác định được vị trí. Trên thế giới hiện này các nhà khoa học đang nghiên cứu về việc tựđịnh vị trong đó dùng các nguồn ở những vị trí chưa biết. Mặc dù họ coi nhẹ giả thuyết là các vật mốc phải ở vị trí cốđịnh nhưng chúng vẫn cần phải có nguồn tín hiệu. Các nguồn này được triển khai trong cùng một vùng với các nút cảm ứng và được dùng làm chuẩn cho các nút lân cận đểước đoán các vị trí và hướng chưa biết từ nguồn tín hiệu. Công trình nghiên cứu của Moses và Savvides dựa trên các nguồn tín hiệu. Các công trình khác ước đoán vị trí của các nút bằng việc xem xét các vấn đề vềước đoán vị trí như là các vấn đề về sự tối ưu lồi vì có những ràng buộc về vị trí giữa hai nút, ví dụ như phạm vi phủ sóng. Hơn nữa trong phương pháp định vị này, Patwari và các đồng nghiệp xác định được chính xác ranh giới của vị trí sensor dựa trên các trạm gốc cốđịnh cần thiết cho thời gian đến hoặc nhận của tín hiệu.

2.3.2. Định vị dựa vào vị trí tương đối

Mặc dù các giao thức định vị dựa trên vật mốc rất hiệu quảđối với một sốứng dụng nào đó, một số mạng cảm ứng khác có thểđược triển khai ở vùng mà không thể bịảnh hưởng bởi vật mốc hoặc GPS, lúc đó chúng có thể bịảnh hưởng bởi nhiễu môi trường hay là do sai số khi điều khiển. Hơn nữa, các nút cảm ứng loại bình thường có thể hoạt động ở chếđộ không tuyến tính hoặc nhiễu không tuân theo phân bố Gaussian. Để khắc phục những khó khăn này, các thông tin vùng được đặt theo từng bước truyền từ nguồn cho đến sink. Để thu được các thông tin vùng chính xác, các nút cảm ứng phải kết hợp để hỗ trợ cho nhau. Hơn nữa, năng lượng có thểđược dự trữ thêm bằng việc cho phép các nút cảm ứng dò theo vị trí của các nút lân cận.

Kỹ thuật xác định vị trí tương đối này được nghiên cứu kĩ hơn bởi cơ cấu vị trí thụ cảm (perceptive localization framework -PLF). Trong cơ cấu này, một nút có thể ươ

Đỗ Thị Tuyết ĐT6-K48 36 Đồ án tốt nghiệp Chương 2 Các giao thức đặc trưng của mạng cảm biến

phát hiện và dò theo vị trí của của nút lân cận bằng cách dùng kỹ thuật ước đoán kết hợp với một bộ lọc từng phần được ghép vào một dãy các sensor. Để tăng độ chính xác của việc ước lượng vị trí, sink có thể yêu cầu tất cả các nút dọc theo đường từ nguồn phải lọc từng phần để tăng số lượng vật mẫu. Quá trình tác động cục bộ này không yêu cầu bất kì một vật mốc nào. Hơn nữa, phần xử lý trung tâm không cần phải quyết định vị trí của các nguồn.

Cho dù dùng giao thức định vị dựa trên vật mốc hay là dựa trên vị trí tương đối thì thông tin vùng đều cần thiết trong các giao thức lớp vận chuyển, lớp mạng và lớp liên kết dữ liệu. Mỗi một loại giao thức định vị có những yêu cầu khác nhau. Các ứng dụng mạng cảm ứng sau này sẽ sử dụng kết hợp các kỹ thuật định vị này.

2.4 Kết luận

Chương này chỉ tập trung vào trình bày hai giao thức tiêu biểu nhất và đáp ứng được các yêu cầu riêng biệt của mạng cảm ứng là xác định vị trí và đồng bộ thời gian. Ngoài hai giao thức này còn có rất nhiều các giao thức khác như giao thức lớp ứng dụng, lớp Mac...Vì thời gian có hạn nên em chỉđưa ra hai giao thức quan trọng mà mọi người cần tìm hiểu khi tiếp cận về lĩnh vực mạng cảm biến. Ngày nay các nhà nghiên cứu cũng đã đưa rất nhiều cải tiến của hai giao thức này, phù hợp với thực tiễn hơn. ớ

Đỗ Thị Tuyết ĐT6-K48 37 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Chương 3. Định tuyến trong mạng cảm biến

3.1. Giới thiệu

Mặc dù mạng cảm biến có khá nhiều điểm tương đồng so với các mạng adhoc có dây và không dây nhưng chúng cũng biểu lộ một số các đặc tính duy nhất mà tạo cho chúng tồn tại thành mạng riêng. Chính những đặc tính này làm cho tập trung mũi nhọn vào yêu cầu thiết kế các giao thức định tuyến mới mà khác xa so với các giao thức định tuyến trong các mạng adhoc có dây và không dây. Việc nhằm vào đặc tính này đã đưa ra một tập các thách thức lớn và riêng đối với WSN.Chương này sẽ trình bày ba loại giao thức định tuyến chính hay được dùng trong mạng cảm biến, đó là định tuyến trung tâm dữ liệu (data - centric protocol), định tuyến phân cấp (hierarchical protocol) và định tuyến dựa vào vị trí (location - based protocol).

3.2. Thách thức trong vấn đềđịnh tuyến

Chính vì những đặc điểm riêng biệt của mạng cảm biến mà việc định tuyến trong mạng cảm biến phải đối mặt với rất nhiều thách thức sau:

Mạng cảm biến có một số lượng lớn các nút, cho nên ta không thể xây dựng được sơđồđịa chỉ toàn cầu cho việc triển khai số lượng lớn các nút đó vì lượng mào đầu để duy trì ID quá cao.

Dữ liệu trong mạng cảm biến yêu cầu cảm nhận từ nhiều nguồn khác nhau và truyền đến sink.

Các nút cảm biến bị rang buộc khá chặt chẽ về mặt năng lượng, tốc độ xử lý, lưu trữ.

Hầu hết trong các ứng dụng mạng cảm biến các nút nói chung là tĩnh sau khi được triển khai ngoại trừ một vài nút có thể di động.

Mạng cảm biến là những ứng dụng riêng biệt. ặ

Đỗ Thị Tuyết ĐT6-K48 38 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Việc nhận biết vị trí là vấn đề rất quan trọng vì việc tập hợp dữ liệu thông thường dựa trên vị trí.

Khả năng dư thừa dữ liệu rất cao vì các nút cảm biến thu lượm dữ liệu dựa trên hiện tượng chung.

3.3. Các vấn đề về thiết kế giao thức định tuyến

Mục đích chính của mạng cảm biến là truyền thông dữ liệu trong mạng trong khi cố gắng kéo dài thời gian sống của mạng và ngăn chặn việc giảm các kết nối bằng cách đưa ra những kỹ thuật quản lý năng lượng linh hoạt. Trong khi thiết kế các giao thức định tuyến, chúng ta thường gặp phải các vấn đề sau.

3.3.1. Đặc tính thay đổi thời gian và trật tự sắp xếp của mạng

Các nút cảm biến hoạt động với sự giới hạn về khả năng tính toán, lưu trữ và truyền dẫn, dưới ràng buộc về năng lượng khắt khe. Tùy thuộc vào ứng dụng mật độ các nút cảm biến trong mạng có thể từ thưa thớt đến rất dày. Hơn nữa trong nhiều ứng dụng số lượng các nút cảm biến có thể lên đến hang trăm, thậm chí hang ngàn nút được triển khai tùy ý và thông thường không bị giám sát bao phủ một vùng rộng lớn. Trong mạng này, đặc tính của các con cảm biến là có tính thích nghi động và cao, như là nhu cầu tự tổ chức và bảo toàn năng lượng buộc các nút cảm biến phải điều chỉnh liên tục để thích ứng hoạt động hiện tại.

3.3.2. Ràng buộc về tài nguyên

Các nút cảm biến được thiết kế với độ phức tạp nhỏ nhất cho triển khai trong phạm vi lớn để giảm chi phí toàn mạng. Năng lượng là mối quan tâm chính trong mạng cảm biến không dây, làm thế nào đểđạt được thời gian sống kéo dài trong khi các nút hoạt động với sự giới hạn về năng lượng dự trữ. Việc truyền gói mutilhop chính là nguồn tiêu thụ năng lượng chính trong mạng. Để giảm việc tiêu thụ năng lượng có thể đạt được bằng cách điều khiển tự động chu kỳ công suất của mạng cảm biến. Tuy p h

Đỗ Thị Tuyết ĐT6-K48 39 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

nhiên vấn đề quản lý năng lượng đã trở thành một thách thức chiến lược trong nhiều ứng dụng quan trọng.

3.3.3. Mô hình dữ liệu trong mạng cảm biến

Mô hình dữ liệu mô tả luồng thông tin giữa các nút cảm biến và các sink. Mô hình này phụ thuộc nhiều vào bản chất của ứng dụng trong đó cái cách dữ liệu được yêu cầu và sử dụng. Một vài mô hình dữ liệu được đề xuất nhằm tập trung vào yêu cầu tương tác và nhu cầu tập hợp dữ liệu của đa dạng các ứng dụng.

Một loại các ứng dụng của mạng cảm biến yêu cầu mô hình thu thập dữ liệu mà dựa trên việc lấy mẫu theo chu kỳ hay sự xảy ra của sự kiện trong môi trường quan sát. Trong các ứng dụng khác dữ liệu có thểđược chụp và lưu trữ hoặc có thểđược xử lý, tập hợp tại một nút trước khi chuyển tiếp dữ liệu đến sink. Một loại thứ 3 đó là mô hình dữ liệu tương tác hai chiều giữa các nút cảm biến và sink.

Nhu cầu hỗ trợđa dạng các mô hình dữ liệu làm tăng tính phức tạp của vấn đề thiết kế giao thức định tuyến.

3.3.4. Cách truyền dữ liệu

Cái cách mà các truy vấn và dữ liệu được truyền giữa các trạm cơ sở và các vị trí quan sát hiện tượng là một khía cạnh quan trọng trong mạng cảm biến không dây. Một phương pháp cơ bản để thực hiện việc này là mỗi nút cảm biến có thể truyền dữ liệu trực tiếp đến trạm cơ sở. Tuy nhiên phương pháp dựa trên bước nhảy đơn (singlehop) có chi phí rất đắt và các nút mà xa trạm cơ sở thì sẽ nhanh chóng bị tiêu hao năng lượng và do đó làm giảm thời gian sống của mạng.

Nhằm giảm thiểu lỗi của phương pháp này thì dữ liệu trao đổi giữa các nút cảm biến và trạm cơ sở có thểđược thực hiện bằng việc sử dụng truyền gói đa bước nhảy (mutilhop) qua phạm vi truyền ngắn. Phương pháp này tiết kiệm năng lượng đáng kể và cũng giảm đáng kể sự giao thoa truyền dẫn giữa các nút khi cạnh tranh nhau để truy ề

Đỗ Thị Tuyết ĐT6-K48 40 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

cập kênh, đặc biệt là trong mạng cảm biến không dây mật độ cao. Dữ liệu được truyền giữa các nút cảm biến và các sink được minh họa như hình vẽ (3.1).

Đểđáp ứng các truy vấn từ các sink hoặc các sự kiện đặc biệt xảy ra tại môi trường thì dữ liệu thu thập được sẽđược truyền đến các trạm cơ sở thông qua nhiều đường dẫn mutilhop.

Trong định tuyến mutilhop của mạng cảm biến không dây, các nút trung gian đóng vai trò chuyển tiếp dữ liệu giữa nguồn và đích. Việc xác định xem tập hợp các nút nào tạo thành đường dẫn chuyển tiếp dữ liệu giữa nguồn và đích là một nhiệm vụ quan trọng trong thuật toán định tuyến. Nói chung việc định tuyến trong mạng kích thước lớn vốn đã là một vấn đề khó khăn, các thuật toán phải nhằm vào nhiều yêu cầu thiết kế thách thức bao gồm sự chính xác, ổn định, tối ưu hóa và chú ý đến sự thay đổi của các thông số.

Hình 3.1 Mô hình truyền dữ liệu giữa sink và các nút

Với đặc tính bên trong của mạng cảm biến bao gồm sự ràng buộc về dải thông và năng lượng đã tạo thêm thách thức cho các giao thức định tuyến là phải nhằm vào việc thỏa mãn yêu cầu về lưu lượng trong khi vẫn mở rộng được thời gian sống của mạng. m bi

Đỗ Thị Tuyết ĐT6-K48 41 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

3.4. Phân loại và so sánh các giao thức định tuyến

Vấn đềđịnh tuyến trong mạng cảm biến là một thách thức khó khăn đòi hỏi phải cân bằng giữa sựđáp ứng nhanh của mạng và hiệu quả. Sự cân bằng này yêu cầu sự cần thiết thích hợp khả năng tính toán và truyền dẫn của các nút cảm biến ngược với mào đầu yêu cầu thích ứng với điều kiện này. Trong mạng cảm biến không dây, mào đầu được đo chính là lượng băng thông được sử dụng, tiêu thụ công suất và yêu cầu xử lý của các nút di động. Việc tìm ra chiến lược cân bằng giữa sự cạnh tranh này cần thiết tạo ra một nền tảng chiến lược định tuyến .

Việc thiết kế các giao thức định tuyến trong mạng cảm biến không dây phải xem xét giới hạn về công suất và tài nguyên của mỗi nút mạng, chất lượng thay đổi theo thời gian của các kênh vô tuyến và khả năng mất gói và trễ. Nhằm vào các yêu cầu thiết kế này một số các chiến lược định tuyến trong mạng cảm biến được đưa ra. Bảng

(3.1) đưa ra sự phân loại một số giao thức dựa trên nhiều tiêu chí khác nhau. Một loại giao thức định tuyến thông qua kiến trúc phẳng trong đó các nút có vai trò như nhau. 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.

Loại thứ 2 là 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à mở rộng thời gian sống của mạng.

Loại giao thức định tuyến thứ 3 là sử dụng phương pháp trung tâm dữ liệu để phan bố sự quan tâm (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 hiện tượng hơn là một nút riêng lẻ. n

Đỗ Thị Tuyết ĐT6-K48 42 Đồ án tốt nghiệ p Chương 3 Định tuyến trong mạng cảm biến

Bảng 3.1 Phân loại và so sánh các giao thức chọn đường trong WSN

Giao Giao Giao Phân Di Dựa Kết Xác QoS Độ KhảĐa Dựa Giao thức thức thức thức loại chuyển vào hợp số định phức năng đường vào chọn trung phân dựa hỏi/đáp liệu vị trí tạp định yêu đường tâmcấp trên của cỡ cầu

dữ vị trí trạng liệu thái SPIN x Ngang Có thể Có Có Không Không Thấp Hạn Có Có

hàng chế Directed x Ngang Hạn Có Có Có Không Thấp Hạn Có Có Diffusion hàng chế chế Rumor x Ngang Rất Không Có Không Không Thấp Tốt Không Có

hàng hạn chế GBR x Ngang Hạn Không Có Không Không Thấp Tốt Không Có hàng chế CADR x Ngang Không Không Có Không Không Thấp Hạn Không Không hàng chế COUGAR x Ngang Không Không Có Không Không Thấp Hạn Không Có hàng chế ACQUIRE x Ngang Hạn Không Có Không Không Thấp Hạn Không Có hàng chế chế LEACH X Phân Nút Không Có Có Không Nút Tốt Không Không cấp gốc cố chủ

định nhóm TEEN& x X Phân Nút Không Có Có Không Nút Tốt Không Không APTEEN cấp gốc cố chủ

định nhóm PEGASIS X Phân Nút Không Không Có Không Nút Tốt Không Không cấp gốc cố chủ

định nhóm MECN& X Phân Không Không Không Không Không Thấp Thấp Không Không SMECN cấp GAF X x Dựa Không Không Không Không Không Thấp Tốt Không Không

theo vị trí

GEAR x Dựa Không Không Không Không Không Thấp Hạn Không Không theo chế vị trí

SAR x Dựa Không Có Có Không Có Trung Hạn Không Có theo bình chế vị trí

SPEED x Dựa Không Không Không Không Có Trung Hạn Không Có theo bình chế QoS

Phân phối quan tâm trong toàn mạng đạt được bằng việc gắn nhiệm vụ cho các

con cảm biến và nhấn mạnh vào các câu hỏi mà liên quan đến các thuộc tính riêng.

Một giao thức khác có thể truyền 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. a D

Đỗ Thị Tuyết ĐT6-K48 43 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Loại giao thức thứ 4 là dựa vào vị trí đểđánh địa chỉ cho các nút cảm biến. lạ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.

3.5. Giao thức trung tâm dữ liệu

3.5.1. 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. Flood 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 3.2)

Hình 3.2 Truyền gói trong Flooding

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

Đỗ Thị Tuyết ĐT6-K48 44 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

đến các nút lân cận. Và thứ 3 đó 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 nut 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.

3.5.2. SPIN

SPIN (Sensor Protocol for Information via Negotiation) là giao thức định tuyến thông tin dựa trên sự dàn xếp dữ liệu. Mục tiêu chính của giao thức này đó là tập trung việc quan sát môi trường có hiệu quả bằng một số các nút cảm biến riêng biệt trong toàn bộ mạng. Nguyên lý của giao thức này đó là sự thích ứng về tài nguyên và sắp xếp dữ liệu. Ý nghĩa của việc dàn xếp dữ liệu (data negotiation) này là các nút trong SPIN sẽ biết về nội dung của dữ liệu trước khi bất kỳ dữ liệu nào được truyền trong mạng . SPIN khai thác tên dữ liệu nhờđó mà các nút sẽ kết hợp miêu tả dữ liệu (metadata) với dữ liệu mà chúng tạo ra và sử dụng sự miêu tả này để thực hiện việc giàn xếp dữ liệu trước khi truyền dữ liệu thực tế. Nơi nhận dữ liệu có thể bày tỏ mối quan tâm đến nội dung dữ liệu bằng cách gửi yêu cầu để lấy được dữ liệu quảng bá. Điều này tạo ra sự sắp xếp dữ liệu đểđảm bảo rằng dữ liệu chỉđược truyền đến nút quan tâm đến loại dữ liệu này. Do đó mà loại trừ khả năng bản tin kép và giảm thiểu đáng kể việc truyền dữ liệu dư thừa qua mạng. Hơn nữa việc sử dụng bộ miêu tả dữ liệu cũng loại trừ khả năng chồng lấn vì các nút có thể chỉ giới hạn về tên lọai dữ liệu mà chúng quan tâm đến.

Việc thích ứng tài nguyên cho phép các nút cảm biến chạy SPIN có thể thích ứng với trạng thái hiện tại của tài nguyên năng lượng. Mỗi nút có thể dò tìm tới bộ quản lý để theo dõi mức tiêu thụ năng lượng của mình trước khi truyền hoặc xử lý dữ liệu. Khi mức năng lượng còn lại thấp các nút này có thể giảm hoặc loại bỏ một số hoạt ờ

Đỗ Thị Tuyết ĐT6-K48 45 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

động như là truyền miêu tả dữ liệu hoặc các gói. Chính việc thích nghi với tài nguyên làm tăng thời gian sống của mạng.

Để thực hiện truyền và sắp xếp dữ liệu các nút sử dụng giao thức này sử dụng ba loại bản tin (hình 3.3).

Hình 3.3 Ba tín hiệu bắt tay của SPIN

Hình 3.4 Hoạt động của SPIN

Hoạt động của SPIN gồm 6 bước như hình (3.4). Bước 1: ADV để thông báo dữ liệu mới tới các nút. Bước 2: REQ để yêu cầu dữ liệu cần quan tâm. Sau khi nhận được ADV các nút quan tâm đến dữ liệu này sẽ gửi REQ để yêu cầu lấy dữ liệu. Bước 3: bản tin DATA bản tin này thực sự chứa dữ liệu được cảm biến và kèm theo mào đầu miêu tả dữ liệu. Bước 4, sau khi nút này nh ận dữ liệu nó sẽ chia sẻ dữ liệu của nó cho các nút còn lại trong mạng bằng việc phát bản tin ADV chứa miêu tả dữ liệu (metadata). ệ

Đỗ Thị Tuyết ĐT6-K48 46 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Bước 5: sau đó các nút xung quanh lại gửi bản tin REQ yêu cầu dữ liệu, và bước 6 là DATA lại được truyền đến các nút mà yêu cầu dữ liệu này.

Tuy nhiên giao thức SPIN cũng có hạn chế khi mà nút trung gian không quan tâm đến dữ liệu nào đó, khi đó dữ liệu không thểđến được đích.

3.5.3. Directed Diffusion

Đây là giao thức trung tâm dữ liệu đối với việc truyền và phân bổ thông tin trong mạng cảm biến không dây. Mục tiêu chính của phương pháp này là tiết kiệm năng lượng để tăng thời gian sống của mạng đểđạt được mục tiêu này, giao thức này giữ tương tác giữa các nút cảm biến, dựa vào việc trao đổi các bản tin, định vị trong vùng lân cận mạng. Sử dụng sự tương tác về vị trí nhận thấy có tập hợp tối thiểu các đường truyền dẫn. Đặc điểm duy nhất của giao thức này là sự kết hợp với khả năng của nút để có thể tập trung dữ liệu đáp ứng truy vấn của sink để tiết kiệm năng lượng.

Thành phần chính của giao thức này bao gồm 4 thành phần: interest (các mối quan tâm của mạng), data message (các bản tin dữ liệu), gradient, reinforcements. Directed disffusion sử dụng mô hình publish- and subcribe trong đó một người kiểm tra (tại sink) sẽ miêu tả mối quan tâm (interest) bằng một cặp thuộc tính-giá trị.

Bảng (3.2) miêu tả cặp thuộc tính-giá trị, các nút cảm biến có khả năng đáp ứng interest này sẽ trả lời kèm theo dữ liệu tương ứng.

Hoạt động của Directed Dissfusion như hình (3.5). Với mỗi nhiệm vụ cảm biến tích cực, sink sẽ gởi quảng bá bản tin interest theo chu kỳ cho các nút lân cận.

Bản tin này sẽ truyền qua tất cả các nút trong mạng như là một sự quan tâm đến một dữ liệu nào đó. Mục đích chính của việc thăm dò này là để xem xét xem có nút cảm biến nào đó có thể tìm kiếm dữ liệu tương ứng với interest. Tất cả các nút đều duy trì một interest cache để lưu trữ các interest entry khác nhau. ệ

Đỗ Thị Tuyết ĐT6-K48 47 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Bảng 3.2 Miêu tả interert sử dụng cặp thuộc tính-giá trị

Cặp thuộc tính-giá trị Miêu tả

Type = chim ruồi Phát hiện vị trí của chim ruồi

Interval=20ms Báo cáo sự kiện chu kỳ 20ms

Duration=10s Thời gian sống của Interest

Field=[(x1,x2),(y1,y2)] Báo cáo từ các con cảm biến trong vùng

Mỗi một mục (entry) trong interest cache sẽ lưu trữ một interest khác nhau. Các entry cache này sẽ lưu trữ một số trường sau: một nhãn thời gian (timestamp), nhiều trường gradient cho mỗi nút lân cận và và trường duration. Nhãn thời gian sẽ lưu trữ nhãn thời gian của interest nhận được sau cùng. Mỗi gradient sẽ lưu trữ cả tốc độ dữ liệu và chiều mà dữ liệu được gửi đi. Giá trị của tốc độ dữ liệu nhận được từ thuộc tính khoảng thời gian trong bản tin interest. Trường duration sẽ xác định khoảng thời gian tồn tại của interest.

Một gradient có thể coi như là một liên kết phản hồi của nút lân cận khi mà nhận được bản tin interest. Việc truyền bản tin interest trong toàn mạng cùng với việc thiết lập các gradient tại mỗi nút cho phép việc tìm ra và thiết lập các đường dẫn giữa sink mà đưa ra yêu cầu về dữ liệu quan tâm và các nút mà đáp ứng mối quan tâm đó.

Khi một nút phát hiện một sự kiện nó sẽ tìm kiếm trong cache xem có interest nào phù hợp không, nếu có nó sẽ tính toán tốc độ sự kiện cao nhất cho tất cả các gradient lối ra. Sau đó nó thiết lập một phân hệ cảm biến để lấy mẫu các sự kiện ở mức tốc độ cao này. Các nút sẽ gửi ra ngoài miêu tả về sự kiện cho các nút lân cận có gradient. Các nút lân cận này nhận dữ liệu và sẽ kiểm tra trong cache xem có entry nào phù hợp không, nếu không nó sẽ loại bỏ dữ liệu còn nếu phù hợp nó sẽ nhận dữ ồ

Đỗ Thị Tuyết ĐT6-K48 48 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

liệu các nút này sẽ thêm bản tin vào cache dữ liệu và sau đó gửi bản tin dữ liệu cho các nút lân cận.

Hình 3.5 Hoạt động cơ bản của Directed Diffusion

Khi nhận được một interest các nút tìm kiếm trong interest cache của nó xem có entry nào phù hợp không, nếu không nút sẽ tạo một cache entry mới. Các nút sẽ sử dụng các thông tin chứa trong interest để tạo ra các thông số interest trong entry. Các entry này là một tập hợp chứa các trường gradient với tốc độ và chiều tương ứng với nút lân cận mà interest được nhận. Nếu như interest nhận được có trong cache thì nút sẽ cập nhật nhãn thời gian và trường duration cho phù hợp với entry. Một trường gradient sẽđược remove khỏi entry nếu quá hạn.

Trong pha thiết lập gradient thì các sink sẽ thiết lập một tập hợp các đường dẫn. Sink có thể sử dụng đường dẫn này với sự kiện chất lượng cao để làm tăng tốc độ dữ liệu. Điều này đạt được thông qua một đường dẫn được hỗ trợ xử lý (path reinforcement process). Các sink này có thể sử dụng sự hỗ trợ của một số các nút lân cận. Để làm được điều này sink có thể gửi lại bản tin interest nguồn ở tốc độ cao thông qua các đường dẫn được chọn, nhờ việc tăng cường các nút nguồn trên đường dẫn để đượ

Đỗ Thị Tuyết ĐT6-K48 49 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

gửi dữ liệu thường xuyên hơn. Directed disffusion có ưu điểm nếu một đường dẫn nào đó giữa sink và một nút bị lỗi, một đường dẫn có tốc độ dữ liệu thấp hơn được thay thế. Kỹ thuật định tuyến này ổn định dưới phạm vi mạng động. Loại giao thức định tuyến này tiết kiệm năng lượng đáng kể.

3.6. Giao thức phân cấp

3.6.1. LEACH

LEACH (Low Energy Adaptive Clustering Hierarchy) là giao thức phân cấp theo cụm thích ứng năng lượng thấp. Đây là giao thức thu lượm và phân phát dữ liệu tới các sink đặc biệt là các trạm cơ sở. Mục tiêu chính của LEACH là:

Mở rộng thời gian sống của mạng

Giảm sự tiêu thụ năng lượng bởi mỗi nút mạng

Sử dụng tập trung dữ liệu để giảm bản tin truyền dẫn trong mạng

Đểđạt được những mục tiêu này LEACH đã thông qua mô hình phân cấp để tổ chức mạng thành các cụm, mỗi cụm được quản lý bởi nút chủ. Nút chủ gánh lấy trọng trách thực hiện nhiều tác vụ. Đầu tiên là thu lượm dữ liệu theo chu kỳ từ các nút thành viên, trong quá trình tập trung dữ liệu nút chủ sẽ cố gắng tập hợp dữ liệu để giảm dư thừa về những dữ liệu tương quan nhau. Nhiệm vụ thứ hai đó là nút chủ sẽ trược tiếp truyền dữ liệu đã được tạp hợp lại đến các trạm cơ sở. Việc truyền này có thể thực hiện theo kiểu single hop. Nhiệm vụ thứ ba là LEACH sẽ tạo ra một mô hình ghép kênh theo thời gian TDMA, mỗi nút trong cụm sẽ được gán một khe thời gian mà có thể sử dụng để truyền tin.

Mô hình LEACH như hình vẽ (3.6). Các nút chủ sẽ quảng bá mô hình TDMA cho các nút thành viên trong cụm của nó. Để giảm thiểu khả năng xung đột giữa các nút cảm biến trong và ngoài cụm, LEACH sử dụng mô hình truy cập đa phân chia theo mã CDMA.Quá trình hoạt động của LEACH được chia thành hai pha là pha thiết lập và pha ổn định. Pha thiết lập bao gồm hai bước là lựa chọn nút chủ và thông tin về l

Đỗ Thị Tuyết ĐT6-K48 50 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

cụm. Pha ổn định trạng thái gồm thu lượm dữ liệu, tập trung dữ liệu và truyền dữ liệu đến các trạm cơ sở. Thời gian của bước ổn định kéo dài hơn so với thời gian của bước thiết lập để giảm thiểu mào đầu.

Hình 3.6 Mô hình mạng LEACH

Trong bước thiết lập, một nút cảm biến lựa chọn một số ngẫu nhiên giữa 0 và 1. Nếu số này nhỏ hơn ngưỡng T(n) thì nút cảm biến là nút chủ. T(n) được tính như sau:

T (n) =1− p *(rp mod1/ p) nếu n ∈G (3.1)

T (n) = 0 còn lại Trong đó p: tỉ lệ phần trăm nút chủ

r: chu kì hiện tại

G: tập hợp các nút không được lựa chọn làm nút chủ trong 1/p chu kì cuối.

Sau khi được chọn làm nút chủ, các nút chủ sẽ quảng bá vai trò mới của chúng cho các nút còn lại trong mạng. Các nút còn lại trong mạng dựa vào bản tin đó và đế

Đỗ Thị Tuyết ĐT6-K48 51 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

cường độ tín hiệu nhận được hoặc một số tiêu chuẩn nào đó để quyết định xem có tham gia vào cụm đó hay không. Và sau đó các nút này sẽ thông báo cho nút chủ biết là mình có mong muốn trở thành thành viên của cụm do nút chủđó đảm nhận.

Trong quá trình tạo cụm các nút chủ sẽ tạo và phân phát mô hình TDMA cho các nút thành viên trong cụm. Mỗi nút chủ cũng chọn lựa một mã CDMA mà sau đó sẽ thông báo tới tất cả các thành viên trong cụm biết. Sau khi pha thiết lập hoàn thành báo hiệu sự bắt đầu của pha ổn định trạng thái và các nút trong cụm sẽ thu lượm dữ liệu và sử dụng các khe thời gian để truyền dữ liệu đến nút chủ. Dữ liệu được thu lượm theo chu kỳ.

Việc mô phỏng cho thấy LEACH tiết kiệm đáng kể năng lượng. Và sự tiết kiệm này phụ thuộc chủ yếu vào hệ số tập trung dữ liệu các nút chủ của cụm.

Tuy nhiên LEACH cũng có một số khuyết điểm sau:

Việc giả sử rằng tất cả các nút chủ trong mạng đều truyền đến trạm cơ sở thông qua một bước nhảy là không thực tế, và vì dự trữ năng lượng và khả năng của các nút thay đổi theo thời gian từ nút này đến nút khác. Hơn nữa khoảng chu kỳổn định trạng thái là vấn đề then chốt đểđạt được giảm năng lượng cần thiết để bù đắp lượng mào đầu gay ra bởi xử lý lựa chọn cụm. Chu kỳ ngắn sẽ làm tăng lượng mào đầu, chu kỳ dài sẽ nhanh chóng làm tiêu hao năng lượng của nút chủ.

LEACH có đặc tính giúp tiết kiệm năng lượng, yêu cầu về năng lượng trong LEACH được phân bổ cho tất cả các nút trong mạng vì chúng ta giả sử rằng vai trò nút chủđược luân chuyển vòng tròn dựa trên năng lượng còn lại trên mỗi nút. LEACH là thuật toán phân tán hoàn toàn và không yêu cầu sựđiều khiển bởi trạm cơ sở. Việc quản lý cụm là cục bộ và không cần sự hiểu biết về mạng toàn cục. Hơn nữa việc tập trung dữ liệu theo cụm cũng tiết kiệm năng lượng đáng kể vì các nút không yêu cầu gửi trực tiếp dữ liệu đến sink. ố

Đỗ Thị Tuyết ĐT6-K48 52 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

3.6.2. PEGASIS

PEGASIS (Power-Efficient Gathering in Sensor Information Systems), PEGASIS phân cấp là một họ các giao thức định tuyến và tập trung thông tin trong mạng cảm biến.

Giao thức này đầu tiên hỗ trợ việc kéo dài thời gian sống của mạng nhờ đạt được việc tiêu thụ năng lượng đồng nhất và hiệu suất năng lượng cao qua tất cả các nút trong mạng, thứ hai làm giảm trễ truyền dữ liệu đến sink.

Giao thức này xem xét mô hình mạng bao gồm tập hợp các nút đồng nhất được triển khai qua một vùng địa lý. Các nút này có sự hiểu biết về vị trí các nút khác trong toàn mạng và chúng còn có khả năng điều khiển công suất và bao phủ một vùng tùy ý. Các nút này cũng được trang bị bộ thu phát sóng hỗ trợ CDMA. Trách nhiệm của các nút này là thu lượm và truyền dữ liệu đến các sink, thông thường là các trạm cơ sở. Mục đích để phát triển một cấu trúc định tuyến và một sơđồ tập trung dữ liệu để giảm thiểu sự tiêu thụ công suất và truyền dữ liệu được tập trung đến trạm cơ sở với trễ truyền dẫn nhỏ nhất trong khi vẫn cân bằng sự tiêu thụ công suất giữa các nút trong mạng.

Giải thuật này sử dụng mô hình cấu trúc dạng chuỗi.

Dự trên mô hình này các nút sẽ giao tiếp với nút hang xóm gần nó nhất. Cấu trúc chuỗi bắt đầu với nút xa sink nhất, các nút mạng được thêm dần vào chuỗi làm chuỗi lớn dần lên, bắt đầu từ nút hang xóm gần nút cuối nhất. Các nút sẽđược gán vào chuỗi theo cách greedy từ nút lân cận gần nhất cho tới các nút còn lại trong mạng. Để xác định được nút lân cận gần nhất mỗi nút sẽ sử dụng cường độ tín hiệu đểđo khoảng cách tới các nút lân cận của nó. Sử dụng dữ kiện này các nút sẽđiều chỉnh cường độ tín hiệu sao cho chỉ có nút lân cận gần nhất nghe được.

Một nút trong chuỗi sẽđược trọn làm nút chủ, trách nhiệm của nút chủ là truyền dữ liệu tập hợp được tới trạm cơ sở. Vai trò nút chủ sẽ bị dịch chuyển vị trí trong chuỗi sau mỗi vòng chu kỳ. Chu kỳ này được quản lý bởi sink và việc chuyển trạng thái từ ạ

Đỗ Thị Tuyết ĐT6-K48 53 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

vòng này đến vòng tiếp theo có thểđược khởi tạo bởi việc đưa ra dấu hiệu công suất cao bởi sink. Việc quay vòng nút chủ trong chuỗi nhằm đảm bảo công bằng trong tiêu thụ năng lượng giữa các nút trong mạng. Tuy nhiên cũng cần chú ý rằng việc thay đổi có khi dẫn đến nút chủ rời xa trạm cơ sở, sink, khi đó nút này lại cần yêu cầu công suất cao để truyền đến trạm cơ sở.

Việc tập trung dữ liệu trong mạng dọc theo chuỗi. Đầu tiên chain leader sẽ gửi một thẻ bài tới nút cuối cùng bên phải cuối chuỗi. Trong khi nhận được tín hiệu này nút cuối sẽ gởi dữ liệu nó thu lượm được đến nút lân cận theo chiều xuôi trong chuỗi, sau đó nút này tập trung dữ liệu và lại tiếp tục gửi đến nút lân cận gần nó nhất, cứ như vậy cho đến khi gửi đến nút chủ. Sau đó nút chủ sẽ lại tập trung dữ liệu và gửi đến sink.

Mặc dù đơn giản nhưng mô hình tập trung dạng chuỗi dễ gây ra trễ trước khi dữ liệu tập trung được truyền đến sink. Một phương pháp để giảm độ trễ này là tập trung dữ liệu song song dọc theo chuỗi, và sẽ càng giảm nhiều hơn nếu các nút được trang bị bộ thu phát sử dụng CDMA.

Dùng PEGASIS sẽ giải quyết được vấn đề về mào đầu gây ra bởi việc hình thành các cụm động trong LEACH và giảm được số lần truyền và nhận bằng việc tập hợp dữ liệu. Tuy nhiên PEGASIS lại có độ trễđường truyền lớn đối với các nút ở xa trong chuỗi. Hơn nữa ở nút chính có thể xảy ra hiện tượng thắt cổ chai.

3.7. Giao thức dựa trên vị trí

Mục tiêu chính của giải thuật định tuyến này là dựa vào các thông tin về vị trí của các nút cảm biến để tìm một đường đi hiệu quảđến đích. Loại định tuyến này rất phù hợp với mạng cảm biến nơi mà việc tập trung dữ liệu là kỹ thuật hữu ích để giảm thiểu việc truyền bản tin đến trạm cơ sở bằng cách loại bỏ sự dư thừa giữa các gói đến từ các nguồn khác nhau. Loại định tuyến này còn yêu cầu sự tính toán và lượng mào đầu truyền dẫn thấp.

Ta sẽ xem xét một số giao thức định tuyến dựa trên vị trí như sau: ụ

Đỗ Thị Tuyết ĐT6-K48 54 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

3.7.1. GAF

Giải thuật chính xác theo địa lý (GAF) dựa trên vị trí có hiệu quả về mặt năng lượng được thiết kế chủ yếu cho các mạng ad hoc di động, nhưng cũng có thể áp dụng cho mạng cảm biến. GAF khai thác việc dư thừa dữ liệu trong mạng bằng cách coi một tập hợp các nút con trong mạng là tương đương nhau khi nhìn từ giao thức lớp trên. GAF chia vùng quan sát thành các hình vuông đủ nhỏ, bất kỳ các nút nào trong hình vuông cũng đều có thể giao tiếp vô tuyến với bất kỳ nút nào nằm trong hình vuông bên cạnh.GAF dự trữ năng lượng bằng cách tắt các nút không cần thiết trong mạng mà không ảnh hưởng đến mức độ chính xác của định tuyến. Nó tạo ra một lưới ảo cho vùng bao phủ. Mỗi nút dùng GPS của nó - vị trí xác định để kết hợp với cùng một điểm trên lưới mà được coi là tương đương khi tính đến giá của việc định tuyến gói. Sự tương đương như vậy được tận dụng để giữ các nút định vị trong vùng lưới xác định trong trạng thái nghỉđể tiết kiệm năng lượng. Vì vậy GAF có thể tăng đáng kể thời gian sống của mạng cảm biến khi mà số lượng các nút tăng lên. Một ví dụ cụ thểđược đưa ra ở hình (3.7). Trong hình vẽ này, nút 1 có thể truyền đến bất kì nút nào trong số các nút 2, 3 và 4 và các nút 2, 3, 4 có thể truyền tới nút 5. Do đó các nút 2, 3, và 4 là tương đương và 2 trong số 3 nút đó có thểở trạng thái nghỉ.

Các nút chuyển trạng thái từ nghỉ sang hoạt động lần lượt để cho các tải được cân bằng. Có ba trạng thái được định nghĩa trong GAF, đó là phát hiện (discovery), để xác định các nút lân cận trong lưới, hoạt động (active), thể hiện sự tham gia vào quá trình định tuyến và nghỉ (sleep) khi sóng được tắt đi. Sự chuyển trạng thái trong GAF được miêu tảở hình (3.8) . Nút nào nghỉ trong bao lâu liên quan đến các thông sốđược điều chỉnh trong quá trình định tuyến. Đểđiều khiển độ di động, mỗi nút trong lưới ước đoán thời gian rời khỏi lưới của nó và gửi thông tin này đến nút lân cận. ng cho m

Đỗ Thị Tuyết ĐT6-K48 55 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Hình 3.7 Ví dụ về lưới ảo trong GAF

Các nút đang không hoạt động điều chỉnh thời gian nghỉ của chúng phù hợp các thông tin nhận được từ các nút lân cận đó để giữ cho việc định tuyến được chính xác. Trước khi thời gian rời khỏi lưới của các nút đang hoạt động quá hạn, các nút đang nghỉ thoát khỏi trạng thái đó và một trong số các nút đó trở nên hoạt động. GAF được triển khai cho cả những mạng bao gồm các nút không di động (GAF cơ bản) và mạng bao gồm các nút di động (GAF thích ứng di động).

Hình 3.8 Sự chuyển trạng thái trong GAF

GAF cố gắng giữ mạng hoạt động bằng cách giữ cho các nút đại diện luôn ở chế độ hoạt động trong mỗi vùng ở lưới ảo của nó. Các kết quả mô phỏng đã chỉ ra rằng GAF thực hiện tối thiểu sẽđược như giao thức định tuyến trong mạng ad hoc thông cho vi

Đỗ Thị Tuyết ĐT6-K48 56 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

thường khi nói đến tổn thất gói và làm tăng thời gian sống của mạng bằng cách tiết kiệm năng lượng. Mặc dù GAF là một giao thức dựa trên vị trí, nó cũng có thểđược coi là như một giao thức phân cấp khi mà các cụm dựa trên vị trí địa lý. Đối với mỗi vùng lưới xác định, mỗi nút đại điện hoạt động như một nút chủđể truyền dữ liệu đến các nút khác. Tuy nhiên nút chủ này không thực hiện bất cứ một nhiệm vụ hợp nhất hay tập trung dữ liệu nào như trong các giao thức phân cấp thông thường.

3.7.2. GEAR

Yu et al. đã đưa ra việc sử dụng thông tin vềđịa lý trong khi phổ biến các yêu cầu đến các vùng thích hợp vì các yêu cầu dữ liệu thường bao gồm các thuộc tính địa lý. Giao thức GEAR (Geographic and Energy-Aware Routing) dùng sự nhận biết về năng lượng và các phương pháp thông báo thông tin vềđịa lý tới các nút lân cận. Việc định tuyến thông tin theo vùng địa lý rất có ích trong các hệ thống xác định vị trí, và đặc biệt là trong mạng cảm biến. Ý tưởng này hạn chế số lượng các yêu cầu ở Directed Diffusion bằng cách quan tâm đến một vùng xác định hơn là gửi các yêu cầu tới toàn mạng. GEAR cải tiến hơn Directed Diffusion ởđiểm này và vì thế dự trữđược nhiều năng lượng hơn.

Trong giao thức GEAR, mỗi một nút giữ một estimated cost và một learned cost trong quá trình đến đích qua các nút lân cận. Estimated cost là sự kết hợp của năng lượng còn dư và khoảng cách đến đích. Learned cost là sự cải tiến của estimated cost giải thích cho việc định tuyến xung quanh các hốc trong mạng. Hốc xảy ra khi mà một nút không có bất kì một nút lân cận nào gần hơn so với vùng đích hơn là chính nó. Trong trường hợp không có một hốc nào thì estimated cost bằng với learned cost. Learned cost được truyền ngược lại 1 hop mỗi lần một gói đến đích làm cho việc thiết lập đường cho gói tiếp theo được điều chỉnh.

Có 2 pha trong giải thuật này: m

Đỗ Thị Tuyết ĐT6-K48 57 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Chuyển tiếp gói đến vùng đích: GEAR dùng cách tự chọn nút lân cận dựa trên sự nhận biết về năng lượng và vị trí địa lý để định tuyến gói đến vùng đích. Có 2 trường hợp cần quan tâm:

khi tồn tại nhiều hơn một nút lân cận gần hơn so với đích: GEAR sẽ chọn hop tiếp theo trong số tất cả các nút lân cận gần đích hơn.

Khi mà tất cả các nút đều xa hơn: trong trường hợp này sẽ có một lỗ hổng. GEAR chọn hop tiếp theo mà làm tối thiểu giá chi phí của nút lân cận này. Trong trường hợp này, một trong số các nút lân cận được chọn để chuyển tiếp gói dựa trên learned cost. Lựa chọn này có thểđược cập nhật sau theo sự hội tụ của learned cost trong suốt quá trình truyền gói.

Chuyển tiếp gói trong vùng

Nếu gói được chuyển đến vùng, nó có thể truyền dữ liệu trong vùng đó có thể bằng cách chuyển tiếp địa lý đệ quy hoặc flooding có giới hạn. Flooding có giới hạn áp dụng tốt trong trường hợp các sensor triển khai không dày đặc. Ở những mạng có mật độ sensor cao, flooding địa lý đệ quy lại hiệu quả về mặt năng lượng hơn là flooding có giới hạn. Trong trường hợp đó, người ta chia vùng thành 4 vùng nhỏ và tạo ra 4 bản copy của gói đó. Việc chia nhỏ này và quá trình chuyển tiếp tiếp tục cho đến khi trong vùng chỉ còn 1 nút, ví dụ như hình (3.9).

Để thỏa mãn các điều kiện chúng ta dùng giải thuật chuyển tiếp địa lý đệ qui để truyền gói trong vùng này. Tuy nhiên, với những vùng mật độ thấp, chuyển tiếp địa lý đệ quy đôi khi không hoàn thành, định tuyến vô tác dụng trong một vùng đích rỗng trước khi số hop gói đi qua vượt quá giới hạn. Trong trường hợp này chúng ta dùng flooding có giới hạn. ợ

Đỗ Thị Tuyết ĐT6-K48 58 Đồ án tốt nghiệp Chương 3 Định tuyến trong mạng cảm biến

Hình 3.9 Chuyển tiếp địa lý đệ quy trong GEAR

3.8. Kết luận

Chương này đã tổng kết và đưa ra khá nhiều các giao thức định tuyến. Mỗi giao thức đều có những ưu và nhược điểm riêng. Hiện nay, đã có rất nhiều các cải tiến của các loại giao thức này được đưa ra, và cho kết quả rất khả quan. Việc lựa chọn loại giao thức nào hoàn toàn phụ thuộc vào ứng dụng mà chúng ta triển khai. Mặc dù sự hoạt động của các giải thuật định tuyến này đầy hứa hẹn trong vấn đề sử dụng hiệu quả năng lượng, các nghiên cứu sau này cần phải xác định rõ các vấn đề như chất lượng dịch vụ của các ứng dụng của các cảm biến hình ảnh và các ứng dụng thời gian thực. ể

Đỗ Thị Tuyết ĐT6-K48 59 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Chương 4. Mô phỏng PEGASIS bằng Mobility Framework của OMNeT++

4.1. Giới thiệu về OMNeT++ và Mobility Framework

4.1.1. Giới thiệu về OMNeT++

OMNeT++ là viết tắt của cụm từ Objective Modular Network Testbed in C++. OMNeT++ là một ứng dụng cung cấp cho người sử dụng môi trường để tiến hành mô phỏng hoạt động của mạng. Mục đích chính của ứng dụng là mô phỏng hoạt động mạng thông tin, tuy nhiên do tính phổ cập và linh hoạt của nó, OMNeT++ còn được sử dụng trong nhiều lĩnh vực khác như mô phỏng các hệ thống thông tin phức tạp, các mạng kiểu hàng đợi (queueing networks) hay các kiến trúc phần cứng... OMNeT++ cung cấp sẵn các thành phần tương ứng với các mô hình thực tế. Các thành phần này (còn được gọi là các module) được lập trình theo ngôn ngữ C++, sau đó được tập hợp lại thành những thành phần hay những mô hình lớn hơn bằng một ngôn ngữ bậc cao (NED). OMNeT++ hỗ trợ giao diện đồ hoạ, tương ứng với các mô hình cấu trúc của nó đồng thời phần nhân mô phỏng (simulation kernel) và các module của OMNeT++ cũng rất dễ dàng nhúng vào trong các ứng dụng khác.

Một mô hình trong OMNeT++ bao gồm các module lồng nhau có cấu trúc phân cấp. Độ sâu của của các module lồng nhau là không giới hạn, điều này cho phép người sử dụng có thể biểu diễn các cấu trúc logic của các hệ thống trong thực tế bằng các cấu trúc mô hình. Các module trao đổi thông tin với nhau thông qua việc gửi các message (message). Các message này có thể có cấu trúc phức tạp tuỳ ý. Các module có thể gửi các message này theo hai cách, một là gửi trực tiếp tới địa chỉ nhận, hai là gửi đi theo một đường dẫn được định sẵn, thông qua các cổng và các kết nối.

Các module có thể có các tham số của riêng nó. Các tham số này có thểđược sử dụng để chỉnh sửa các thuộc tính của module và để biểu diễn cho topology của mô hình. Các module ở mức thấp nhất trong cấu trúc phân cấp đóng gói các thuộc tính. i s

Đỗ Thị Tuyết ĐT6-K48 60 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Các module này được coi là các module đơn giản, và chúng được lập trình trong ngôn ngữ C++ bằng cách sử dụng các thư viện mô phỏng.

Cấu trúc phân cấp của các module

Một mô hình trong OMNeT++ chứa các module lồng nhau có cấu trúc phân cấp, trao đổi thông tin với nhau bằng cách gửi các message. Cấu trúc của mô hình có thể được mô tả bằng ngôn ngữ NED của OMNeT++.

Hình 4.1 Cấu trúc phân cấp module trong OMNeT++

Các module có thể chứa nhiều module con và được gọi là module kết hợp. Các module đơn giản là các module có cấp thấp nhất trong cấu trúc phân cấp. Các module đơn giản chứa các thuật toán của mô hình. Người sử dụng triển khai các module đơn giản bằng ngôn ngữ C++, sử dụng các thư viện mô phỏng của OMNeT++.

Message, cổng, liên kết

Các module trao đổi thông tin bằng việc gửi các message.Trong thực tế, message có dạng khung (frame) hoặc là các gói tin (packet) được truyền đi trong mạng. Các message có thể có cấu trúc phức tạp tuỳ ý. Các module đơn giản có thể gửi các message đi một cách trực tiếp đến vị trí nhận hoặc gửi đi theo một đường dẫn định sẵn thông qua các cổng và các liên kết.

"Thời gian mô phỏng địa phương" (local simulation time) của một module tăng lên khi module nhận được một message. Message có thểđến từ một module khác hoặc đến từ cùng một module (message của chính bản thân module - self-message được dùng để thực hiện bộ định thời). Cổng (gate) là các giao tiếp vào ra của module. ớ

Đỗ Thị Tuyết ĐT6-K48 61 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Message được gửi đi qua các cổng ra và được nhận vào thông qua các cổng vào. Mỗi kết nối (connection) hay còn gọi là liên kết (link) được tạo bên trong một mức đơn trong cấu trúc phân cấp của các module: bên trong một module kết hợp, một kết nối có thể được tạo ra giữa các cổng tương ứng của hai module con, hoặc giữa cổng của module con với cổng của module kết hợp.

Hình 4.2 Các kết nối trong OMNeT++

Mô hình truyền gói tin:

Một kết nối có thể có ba tham sốđặc trưng. Những tham số này rất thuận tiện cho các mô hình mô phỏng mạng thông tin nhưng không hữu dụng lắm cho các kiểu mô hình khác. Ba tham số này bao gồm:

Độ trễđường truyền (propagation delay) tính bằng s - giây.

Tỉ số lỗi bit, được tính bằng số lỗi/bit.

Tỉ số dữ liệu, được tính bằng số bit/s.

Các tham số này là tuỳ chọn. Giá trị của các tham số này là khác nhau trên từng kết nối, phụ thuộc vào kiểu của liên kết (hay còn gọi là kiểu của kênh truyền - channel type).

Độ trễđường truyền là tổng thời gian đến của message bị trễđi khi truyền qua kênh.

Tỉ số lỗi bit ảnh hưởng đến quá trình truyền message qua kênh. Tỉ số này là xác suất các bit bị truyền sai. Do đó xác suất để một message độ dài n bit truyền đi chính xác là: t h

Đỗ Thị Tuyết ĐT6-K48 62 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

P(message gửi đi được nhận chính xác) = (1 - ber)n Trong đó ber là tỉ số lỗi bit và n là số bit của message. Các message truyền đi đều có một cờ lỗi, cờ này sẽ được thiết lập khi việc truyền message có lỗi. Tỉ số dữ liệu được tính theo đơn vị bit/s, và nó được sử dụng để tính thời gian để truyền một gói tin. Khi tỉ số này được sử dụng, quá trình gửi message đi trong mô hình sẽ tương ứng với việc truyền bit đầu tiên và message được tính là đến nơi sau khi bên nhận đã nhận được bit cuối cùng.

Xây dựng và chạy thử các mô hình mô phỏng

Một mô hình OMNeT++ bao gồm những phần sau: Ngôn ngữ mô tả topology - NED (file có phần mở rộng .ned): mô tả cấu trúc của module với các tham số, các cổng... Các file .ned có thểđược viết bằng bất kỳ bộ soạn thảo hoặc sử dụng chương trình GNED có trong OMNeT++. Định nghĩa cấu trúc của các message (các file có phần mở rộng .msg): Người sử dụng có thểđịnh nghĩa rất nhiều kiểu messsage và thêm các trường dữ liệu cho chúng. OMNeT++ sẽ dịch những định nghĩa này sang các lớp C++ đầy đủ. Mã nguồn của các module đơn giản. Đây là các file C++ với phần mở rộng là .h hoặc .cc.

Quá trình tiếp theo giống như biên dịch mã nguồn C/C++:

Trong Linux: các file .cc liên kết thành file .o.

Trong Windows: các file .cpp lien kết thành file .obj.

Sau đó, tất cả các file trên sẽđược liên kết (link) với các thư viện cần

thiết để tạo thành file .exe .

Chạy các ứng dụng mô phỏng bằng OMNeT++: i. T

Đỗ Thị Tuyết ĐT6-K48 63 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Ta thực hiện đánh hai lệnh sau:

opp_nmakemake để tạo ra Makefile.vc

Để tạo file chạy ta gõ:

nmake -f Makefile.vc.

4.1.2. Giới thiệu về Mobility

Mobility là frame work được xây dựng trên OMNeT++ để nhằm hỗ trợ mô phỏng mạng vô tuyến và di động. Phần lõi của frame work hỗ trợ di động của các nút, quản lý kết nối động và mô hình kênh vô tuyến. Thêm vào đó, phần lõi này còn cung cấp các module cơ bản mà ta có thể dựa vào đó mà xây dựng module của mình. Với khái niệm này người lập trình dễ dàng mô phỏng được giao thức của mình dựa trên Mobility frame work.

Frame work này chủ yếu được dùng để mô phỏng:

Mạng vô tuyến cốđịnh.

Mạng vô tuyến di động.

Mạng tập trung và phân bố.

Mạng cảm biến.

Mạng vô tuyến đa kênh.

Nhiều sự mô phỏng khác mà cần hỗ trợ di động và giao diện vô

tuyến. Các khái niệm cơ bản của Mobility FW:

Channel control :

Hỗ trợ di động và quản lý kết nối động. Điều khiển và duy trì các kết nối tiềm ẩn giữa các host trong mạng. ỏ

Đỗ Thị Tuyết ĐT6-K48 64 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Host: Cấu trúc của một host di động được miêu tả như hình vẽ dưới đây. Host là module kết hợp gồm có các lớp(chính là các module) cơ bản sau: lớp ứng dụng appl, lớp mạng Net, lớp Nic. Trong đó module nic bao gồm các module con là: Mac, decider, snrEval. Tương ứng với các lớp là các module được tạo ra trongthư mục / template.

Hình 4.3 Cấu trúc của host di động

Cấu trúc này cũng dựa trên một phần của tiêu chuẩn ISO/OSI. Tuy nhiên host còn có thêm hai module nữa là: blackboard và mobility. Mobility cung cấp thông tin về vị trí địa lý và điều khiển sự di chuyển của host. Blackboard được sử dụng qua các lớp giao tiếp. Nó cung cấp thông tin qua một hay nhiều lớp và rất có ích khi ta đánh giá giao thức.

Cài đặt Mobility FW:

Ban đầu bạn down Mobility FW trên trang web của OMNeT++ và để chúng vào thư mục cài đặt OMNeT++. Sau đó bạn làm theo các bước sau:

Sửa biến OMNETPP_ROOT trong file mkmk.cmd chỉ đến thư mục bạn cài OMNeT++.

Chạy mkmk.cmd Nic.

Đỗ Thị Tuyết ĐT6-K48 65 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Sau đó bạn cần lien kết các thư viện của Mobility bằng cách vào cmd chỉđến thư mục Mobility chạy lệnh sau:

nmake /f Makefile.vc core_dir && nmake /f Makefile.vc contrib_dir && nmake /f Makefile.vc networks_dir

Đến đây thì bạn có thể sử dụng được Mobility và sẵn sàng xây dựng một chương trình của chính mình. Mobility FM cung cấp các module cơ bản tương ứng với các lớp của host. Module cung cấp các khai báo hàm cần thiết, các hướng dẫn cơ bản để tạo module của chính bạn. Hoặc bạn có thể tham khảo các module trong thư mục /core hoặc /contric. Bạn cũng có thể kế thừa các Module này.

Sau khi xây dựng các module cần thiết cho mô phỏng, bạn cần copy file Makefile.gen.vc vào thư mục Yournetwork mà bạn tạo ra, thay đổi biến MOBFW chỉ đến đường dẫn của mobility. Và cuối cùng bạn vẫn phải tạo file Omnetpp.ini để thiết lập các tham sốđầu vào cho mô phỏng.

Mobility chỉ cung cấp các module cần thiết cho quá trình mô phỏng. Tuy nhiên nếu bạn cũng có thể tạo ra một module mới mà phù hợp với mục đích của bạn. Module mới được tạo ra phải bao gồm 3 file: a.cc,a.h, a.ned.

Module cơ bản

Module cơ bản sử dụng khởi tạo nhiều giai đoạn của OMNeT++ cho nên các module của MF khởi tạo bằng hai giai đoạn. Trong trường hợp bạn sử dụng Blackboard thì bạn phải public ở giai đoạn 0 và subcribe ở giai đoạn 1. Điều này để tránh trường hợp việc miêu tả một tham số trước khi tham sốấy được public

Trong các file ở phần template có chứa hàm initialize(int) của module đơn giản . Bạn không được xóa dòng này vì nó được coi như là điều bắt buộc của giai đoạn khởi tạo module cơ bản.

Khái niệm địa chỉ Chúng ta sử dụng id() của module đểđánh địa chỉ trong MF. Id() của lớp Nic được dùng đểđánh địa chỉ lớp Mac và id() của lớp Net được dùng đểđánh địa chỉ lớp a chính mình.

Đỗ Thị Tuyết ĐT6-K48 66 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

mạng và lớp ứng dụng. Để lấy được địa chỉ của các module này MF cung cấp các hàm cơ bản để lấy địa chỉ: myApplAddr(), myNetwAddr() và myMacAddr() đối với các lớp BasicApplLayer, BasicNetwLayer và BasicMacLayer tương ứng. Hàm netw2mac() của module Channel Control cung cấp giao thức ARP đơn giản để chuyển đổi địa chỉ giữa lớp mạng và lớp Mac. Tuy nhiên bạn cũng có thểđịnh nghĩa lại hàm getMacAddr() của lớp BasicNetwLayer để thực hiện chức năng này.

Quy ước đặt tên

Có một số các quy ước đặt tên trong các module file .ned và bạn phải tuân theo. Tất cả các module của host phải chứa từ Host hoặc host trong tên của module. Ví dụ: BaseStationHost hoặc MobileHost. Ngoài ra còn có một số module ned bạn không thể thay đổi tên được như channelcontrol, blackboard, net, phy, snrEval.

Module *Basic

MF cung cấp cho mỗi lớp một module tương ứng lấy từ lớp module cơ bản. Bạn cũng có thể mở rộng các module này. Cấu trúc kế thừa module của MF được thể hiện như hình vẽ.

Hình 4.4 Cấu trúc kế thừa module trong MF

Khái niệm bản tin : ứ

Đỗ Thị Tuyết ĐT6-K48 67 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Để cung cấp các chức năng cơ bản như là đóng gói(encapsulate) và dỡ gói (decapsulate) trong module *Basic chúng ta cần thiết phải có những header cho mỗi lớp tương ứng. Những bản tin này có những trường bắt buộc và quan trọng cần thiết cho mô phỏng. Bạn chỉ có thể mở rộng các loại bản tin này. Sau đây là một số loại bản tin tương ứng với các lớp:

Bảng 4.1 Các loại bản tin tương ứng của các lớp ỏ

Đỗ Thị Tuyết ĐT6-K48 68 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Blackboard

Khi bạn muốn đánh giá hoạt động một giao thức, bạn cần thiết phải biết thông tin về trạng thái bên trong một giao thức. Khi đó bạn cần sử dụng Blackboard. Sự thay đổi trạng thái được publish trên Blackboard, và đơn giản bạn chỉ cần đăng ký tham số đó với Blackboard và sau đó truy cập đến tham số này.

Ngoài ra Blackboard còn cho phép bạn trao đổi thong tin giữa các lớp mà không cần sử dụng biến con trỏđể liên lạc vòng quanh giữa các module. Ví dụ lớp vật lý có thể cảm nhận xem kênh bận hay rỗi. Nếu giao thức lớp mạng dựa trên cảm nhận sóng mang thì nó cần thong tin này từ lớp vật lý. Blackboard là một module mà các thong tin tương ứng có thể publish trên nó và sau đó có thể truy cập bởi bất kỳ module nào mà đăng ký với nó. BasicModule cung cấp mọi thứ cần thiết để tương tác với lớp Blackboard. c

Đỗ Thị Tuyết ĐT6-K48 69 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Nếu bạn muốn subcribe() một tham số, bạn bắt buộc phải làm điều này ở giai đoạn 0 khi khởi tạo module:

void YourClass::initialize(int stage) { BaseClass::initialize(stage);if (stage == 0){SomeBBItem item;catItem = bb->subscribe(this, &item, -1); ... }else if(stage == 1) { ...

Biến item của lớp SomeBBItem thể hiện cho tham số mà bạn muốn đăng ký.

Ví dụ bạn muốn đăng ký thông tin về vị trí của host bạn có thể khai báo biến:

SomeBBItem catHostMove. Tiếp theo đó bạn cần phải thực hiện đăng ký biến

này với module Blackboard như sau:

catItem = bb->subscribe(this, &item, -1);

catItem trả về kiểu số nguyên, this là con trỏđến module mà bạn sau này bạn

muốn lấy thông tin về sự thay đổi của tham số item, -1 là phạm vi của tham số.

Hủy đăng ký: unsubscribe()

Muốn hủy đăng ký bạn làm như sau:

bb->unsubscribe(this, catItem);

Lấy thông tin đăng ký: bạn sử dụng hàm receiveBBItem:

void YourClass::receiveBBItem(int category, \const BBItem *details, int scopeModuleId) {// in case you want to handle messages hereEnter_Method_Silent();// in case not you but your base class subscribed:BaseClass::receiveBBItem(category, details,scopeModuleId);// react on the stuff that you subscribedif(category == catItem) {someBBItemPtr = static_cast<const SomeBBItem *>(details);// do something

} ..

Đỗ Thị Tuyết ĐT6-K48 70 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Tham sốđầu tiên của hàm này là category là số nguyên mà hàm đăng ký trả lại , tham số thứ hai là đối tượng của lớp mà bạn đăng ký và tham số thứ ba là phạm vi của tham số này. Bạn cũng có thểđặt hai macro Enter_Method or Enter_Method_Silent ở đầu. Điều này cho phép bạn sắp xếp hoặc hủy bản tin. Bạn cũng nên thông báo cho lớp cơ sở. Bây giờ bất kỳ sự thay đổi nào cua tham số này, lớp cơ sở sẽ thong báo cho bạn.

Phần này chỉ trình bày tóm tắt về Mobility, bạn có thể tham khảo thêm cách sử dụng các hàm API trong thư mục /doc sau khi cài đặt Mobility.

4.2. Giới thiệu về PEGASIS

Mạng cảm biến bao gồm những nút giới hạn năng lượng và truyền thông vô tuyến để thu lượm thông tin hữu ích trong trường cảm biến. Việc hợp nhất dữ liệu cảm nhận được theo một cách có hiệu quả năng lượng là vấn đề then chốt trong hoạt động kéo dài thời gian sống của mạng. Trong bài toán tập hợp dữ liệu, trong mỗi vòng truyền thông mỗi nút sẽ có một gói dữ liệu để truyền đến trạm cơ sở. Nếu mỗi nút truyền trực tiếp dữ liệu đến trạm cơ sở thì nó sẽ nhanh chóng bị tiêu hao năng lượng. Giao thức LEACH khắc phục bằng cách tạo ra các cụm, trong mỗi cụm sẽ bầu chọn một nút chủđể tập hợp dữ liệu từ các nút thành viên và truyền đến đến trạm cơ sở. Bằng cách ngẫu nhiên lựa chọn nút chủ, LEACH đạt được sự cải thiện 8 lần so với cách truyền trực tiếp khi đo tỷ lệ nút chết. Mặc dù đạt được những cải thiện đáng kể nhưng LEACH vẫn còn một số giới hạn sau:

Tiêu tốn lượng mào đầu để thiết lập các cụm.

Truyền dữ liệu trức tiếp từ mỗi cụm chủđến trạm cơ sởở xa.

Số lượng các lần truyền ở khoảng cách xa sẽ tăng khi kích thước mạng tăng và tiêu hao tổng năng lượng của mạng.

Giao thức PEGASIS em đưa ra ởđây có sự cải thiện đáng kể hơn so với LEACH. PEGASIS (Power-Efficient Gathering in Sensor Information Systems) là giao thức dựa trên xây dựng chuỗi gần tối ưu. Tức là mỗi nút chỉ giao tiếp với một nút lân ạ

Đỗ Thị Tuyết ĐT6-K48 71 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

cận gần nó nhất, và lần lượt truyền dữ liệu đến trạm cơ sở, do đó nó làm giảm tối thiểu năng lượng sử dụng trong một vòng.

4.2.1. PEGASIS cơ bản

PEGASIS hỗ trợ tối thiểu hóa khoảng cách truyền trong mạng, tối thiểu hóa lượng mào đầu quảng bá, tối thiểu hóa khối lượng bản tin truyền đến trạm cơ sở và phân bố năng lượng đồng đều giữa các nút trong mạng.

Ý tưởng của PEGASIS là tạo một chuỗi các nút cảm biến để mỗi nút có thể nhận và truyền dữ liệu tới nút bên cạnh, việc truyền dữ liệu từ nút đến nút, tập hợp lại và sau cùng truyền đến trạm cơ sở. Các nút này sẽ thay nhau truyền dữ liệu đến trạm cơ sở, để năng lượng trung bình được sử dụng bởi mỗi nút được giảm ở mỗi vòng.

Để thực hiện thuật toán chúng ta giả sử tất cả các nút cảm biến đều có hiểu biết toàn cục về mạng và đều có thể sử dụng thuật toán Greedy. Thuật toán greedy thực hiện rất tốt và việc xây dựng chuỗi được thực hiện trước khi một vòng truyền dữ liệu bắt đầu.

Để xây dựng một chuỗi chúng ta bắt đầu từ nút xa trạm BS nhất. Chúng ta làm điều này đểđảm bảo các ở xa BS đều có nút lân cận gần nó, vì trong thuật toán greedy khoảng cách giữa các nút sẽ tăng dần vì các nút nằm trong chuỗi sẽ không được thăm lại. Hình (4.5) chỉ ra thứ tự liên kết, nút 0 nối với nút 3, nút 3 nối với nút 1, nút 1 nối với nút 2. Khi một nút chết, các nút sẽ phải xây dựng lại chuỗi và bỏ qua nút chết ấy.

Hình 4.5 Xây dựng chuỗi sử dụng thuật toán Greedy

Để tập hợp dữ liệu mỗi vòng, mỗi nút sẽ nhận dữ liệu từ nút hàng xóm và hợp nhất với dữ liệu nó cảm nhận được và truyền đến nút hàng xóm tiếp theo trong chuỗi. ể

Đỗ Thị Tuyết ĐT6-K48 72 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Sau khi chuỗi được thành lập, bước tiếp theo là chọn nút chủ. Nút chủ được chọn bằng cách sau: ở vòng thứ i thì nút thứ i mod N (N là số nút trong mạng ) sẽ làm chủ. Như vậy năng lượng sẽđược san sẻ giữa các nút. Khi một nút chết, chuỗi sẽđược cập nhật lại bằng cách bỏ qua nút đó trong chuỗi. Như hình 4.6 khi nút 7 chết , nút 8 sẽ cố gắng liên lạc với nút 6.

Hình 4.6 Xử lý lỗi khi một nút trong chuỗi chết.

4.2.2. PEGASIS cải tiến

Trong giải thuật PEGASIS cơ bản, chúng ta thấy rằng mặc dù năng lượng đã được chia sẻ cho các nút nhưng các nút ở xa trạm BS sẽ bị tiêu thụ năng lượng nhiều hơn và do đó nhanh chóng chết đi. Như vậy sẽảnh hưởng đến thời gian sống của toàn mạng. Sau đây, ta đưa ra một cải tiến trong quá trình chọn nút chủđể làm tăng thời gian sống của mạng. Chúng ta sẽ không cho các nút ở xa trạm BS và có năng lượng thấp làm nút chủ.

Chúng ta chọn nút chủ như sau:

Tất cả các nút sẽ tính toán tỉ số Ri như sau: c c

Đỗ Thị Tuyết ĐT6-K48 73 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Ri=Pai/PTxi

Trong đó: Pai : năng lượng của nút i tại thời điểm hiện tại.

PTxi : năng lượng cần thiết để nút i truyền đến trạm cơ sở.

Nút cuối chuỗi sẽ bắt đầu gửi gói chứa giá trị Ri của nó về phía nút hàng xóm trong chuỗi. Mỗi nút nhận gói này sẽ so sánh giá trị hiện tại trong gói với giá trị R của nó. Nếu cao hơn, nó đơn giản sẽ chuyển tiếp gói, còn nếu nhỏ hơn, nó sẽ biến đổi gói với giá trị hiện tại của nó và chuyển tiếp đến nút cạnh nó trong chuỗi.

Nút có giá trị R cao nhất sẽ là nút chủ. Nút chủ sẽ thông báo cho cách thành viên trong chuỗi biết.

Việc bầu chọn nút chủđược thực hiện theo một số vòng nào đó.

Số vòng để lựa chọn nút chủ thay đổi thích ứng theo mức năng lượng hiện tại của mỗi nút. Tại thời điểm bắt đầu, mức năng lượng của mỗi nút khác nhau tương đối nhỏ và các nút vẫn có mức năng lượng rất cao. Một khi được lựa chọn làm nút chủ, nút sẽ giữ vai trò này trong một số vòng. Sau đó nó khỏi tạo chu kỳ lựa chọn nút chủ khác và do đó làm giảm số mào đầu liên kết với nút chủ. Khi mức năng lượng của các nút giảm thì số vòng để chọn lại nút chủ cũng giảm và do đó tránh được một nút tiêu thụ năng lượng quá nhiều khi làm nút chủ. Khi mức năng lượng của nút trở nên quá thấp, việc chọn nút chủ sẽ diễn ra thường xuyên ở mỗi vòng. Kỹ thuật này đảm bảo các nút có năng lượng cao và gần trạm BS sẽ có nhiều cơ hội làm nút chủ hơn. Việc chọn nút gần trạm BS làm nút chủ sẽ giảm tổng chi phí truyền trong mạng.

Sau khi chọn nút chủ. Nút chủ sẽ truyền thẻ bài dọc theo chuỗi đến nút cuối chuỗi. Nút này bắt đầu cảm nhận dữ liệu và truyền đến nút bên cạnh nó trong chuỗi. Nút này sẽ tập hợp dữ liệu của nó và dữ liệu nhận được trong một gói và truyền đến nút bên cạnh nó trong chuỗi. Cứ như thế, dữ liệu được truyền đến trạm cơ sở. ẽ

Đỗ Thị Tuyết ĐT6-K48 74 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Như vậy về mặt thuật toán chúng ta thấy rằng PEGASIS có những cải tiến đáng

kể hơn so với LEACH về thời gian sống. PEGASIS tiết kiệm năng lượng ở một số giai

đoạn. Cụ thể như sau:

Đầu tiên, việc tập hợp dữ liệu cục bộ, khoảng cách mà hầu như các nút trong mạng truyền dữ liệu nhỏ hơn nhiều so với việc truyền dữ liệu của các nút thành viên đến nút chủ trong cụm của LEACH.

Thứ hai, khối lượng dữ liệu nút chủ trong PEGASIS nhận được nhiều nhất là hai bản tin trong khi đó của LEACH là 20 (nếu mạng có 100 nút), nhiều hơn rất nhiều.

Thứ ba, chỉ có một nút trong mạng truyền dữ liệu đến trạm cơ sở trong khi đó ở LEACH có 5% số nút truyền đến trạm cơ sở.

Mặc dù có những cải tiến đáng kể so với LEACH, nhưng PEGASIS vẫn tồn tại một số hạn chế như sau:

Trễ trong mạng khá lớn, đặc biệt là nếu kích thước mạng lớn thì chuỗi sẽ rất dài và số lượng bước nhảy rất cao khi truyền dữ liệu từ cuối chuỗi đến trạm cơ sở.

Thêm vào đó, các nút trong chuỗi phải biết cấu hình mạng và điều này không phải luôn luôn dễ dàng đối với mạng cảm biến.

Xảy ra hiện tượng thắt cổ chai tại nút chủ. Tức là dữ liệu tập hợp được đến nút chủ thì nút chủ không còn đủ năng lượng truyền đến trạm BS nữa.

Khắc phục:

Để khắc phục trễ chúng ta có thể chia mạng ra thành nhiều khu vực con, mỗi khu vực con này sẽ thiết lập nên một chuỗi. Tương ứng với mỗi chuỗi con sẽ có một nút chủ. Các nút chủ này lại có thể liên kết với nhau tạo thành chuỗi cấp cao hơn và chuỗi này sẽ lại chọn nút chủđể truyền đến trạm BS. Mô tả như hình (4.7) sau: ể

Đỗ Thị Tuyết ĐT6-K48 75 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Hình 4.7 Khắc phục của PEGASIS

4.3. Mô phỏng

4.3.1. Mô hình năng lượng

Đặc điểm của kênh vô tuyến

Trong kênh vô tuyến, quá trình truyền sóng điện từ có thểđược mô hình bằng quy luật hàm giảm công suất ở khoảng cách giữa bộ phát và bộ thu. Thêm vào đó, nếu giữa bộ phát và bộ thu không truyền theo đường truyền thẳng mà bị cản trở bởi chướng ngại vật thì khi đó song điện từ sẽđến bộ thu bằng các đường khác nhau tại thời điểm khác nhau. Điều này gây ra hiện tượng phading đa đường. Vấn đề là ta sử dụng mô hình nào (mô hình đường truyền thẳng hay mô hình phading đa đường) trong mạng cảm biến. Ta biết công suất thu được tại bộ thu sẽ giảm khi khoảng cách giữa bên phát và bên nhận tăng lên. Theo "Wendi" thì cả hai mô hình này đều được sử dụng tùy thuộc vào khoảng cách giữa bên truyền và bên phát. Nếu khoảng cách giữa bên phát và bên thu nhỏ hơn khoảng cách dcross-over thì mô hình không gian được sử dụng (suy hao d2) và nếu ngược lại thì mô hình 2 đường dẫn được sử dụng (suy hao d4). thu. Thêm vào

Đỗ Thị Tuyết ĐT6-K48 76 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Điểm cắt (cross-over) được định nghĩa như sau:4π

d =

Lhrht (4.1)

crossover

λ

Trong đó: L ≥ 1 : hệ số suy hao hệ thống không liên quan đến quá trình truyền hr: chiều cao của ănten bên nhận so với mặt đất ht: là chiều cao của ăn ten phát so với mặt đất λ: là bước song của tín hiệu song mang Nếu khoảng cách truyền nhỏ hơn dcross-over thì công suất truyền suy hao được

tính như sau :

PG G λ2

P (d) =ttr (4.2)

(4πd)2 L

Trong đó :

Pr(d) : công suất nhận được ở khoảng cách d

Pt : công suất bên truyền

Gt : hệ số khuếch đại của anten bên truyền

Gr hệ số khuếch đại của anten bên nhận

λ: là bước song của tín hiệu sóng mang

L ≥1 : hệ số suy hao hệ thống không liên quan đến quá trình truyền

d : khoảng cách giữa bên truyền và bên nhận Phương trình này mô hình sự suy hao khi bên phát và bên thu có sự thông tin tầm nhìn thẳng (truyền thẳng không có chướng ngại vật), điều này chỉ xảy ra nếu như

bên phát và bên thu gần nhau(d<dcross-over). Nếu khoảng cách d> dcross-over thì ta có công thức sau : đế

Đỗ Thị Tuyết ĐT6-K48 77 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Pr (d) =PtGtGr 4 ht 2 hr 2 (4.3)d

Trong đó : Pr(d) : công suất nhận được ở khoảng cách d Pt : công suất bên truyền hr: chiều cao của ănten bên nhận so với mặt đất ht: là chiều cao của ăn ten phát so với mặt đất

d : khoảng cách giữa bên truyền và bên nhận Gt : hệ số khuyêch đại của anten bên truyền Gr hệ số khuyêch đại của anten bên nhận Trong trường hợp này tín hiệu nhận được theo cả hai hướng, hướng trực tiếp và

hướng phản xạ. Vì có một hay nhiều đường truyền mà tín hiệu đến, nên tín hiệu sẽ suy giảm theo d4. Ví dụ : Cho Gt=Gr=1, ht=hr=1.5m, hệ thống không suy hao L=1, f=914 MHZ Suy ra : λ =3*108 /914*106 =0.328m, thay giá trị này vào hai biểu thức trên Ta có:

⎧−4 Pt Pr = ⎨⎪6.82 ×10 Pd 2:d < 86.2m (4.4)

⎪2.25 t :d ≥ 86.2m ⎩ d 4

Trong phần này, chúng ta sẽ xem xét một mô hình đơn giản sẽ áp dụng trong phần mô phỏng. n

Đỗ Thị Tuyết ĐT6-K48 78 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Hình 4.8 Mô hình năng lượng đơn giản

Như thảo luận ở trên sự suy giảm công suất trong quá trình truyền phụ thuộc vào khoảng cách giữa bên phát và bên thu, nếu khoảng cách tương đối ngắn, ta có thể áp dụng mô hình tỉ lệ nghịch với d2, và ngược lại nếu khoảng cách dài ta áp dụng mô hình tỉ lệ với d4. Bộđiều khiển công suất có thểđảo ngược sự suy hao này bằng cách thiết lập khuếch đại công suất đểđảm bảo mức công suất nào đó tại bên nhận, do đó để truyền một bản tin dài l bit, ở khoảng cách d ta có:

E (l, d )= E −(l)+ E amp (l, d ) (4.5)

Tx Tx elec Tx−

ETx (l, d )= ⎪⎨⎧ lEelec + lε friss−ampd 2: d < dcrossover (4.6)⎪lEelec +lε : d ≥ dcrossover

⎩ two−ray−ampd 4

Bên nhận:

ERx (l)= ERx−elec (l) (4.7)

ERx (l)= lEelec (4.8)

Trong đó năng lượng điện tử, Eelec phụ thuộc vào các hệ số như: mã hóa số, điều chế, lọc tín hiệu trước khi được gửi đến bộ khuyêch đại.Thêm vào đó việc sử dụng kỹ thuật trải phổ năng lượng điện tử phải tính đến cả năng lượng trải phổ tín hiệu khi ấ

Đỗ Thị Tuyết ĐT6-K48 79 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

truyền và tương quan dữ liệu với mã trải phổ khi nhận. Các nhà nghiên cứu đã thiết kế chip thu phát baseband hỗ trợ thông tin trải phổđa người dùng và hoạt động ở 165mW ở chếđộ truyền và 46.5 mW ở chếđộ nhận, theo "windy", người ta đã tập hợp năng lượng tiêu thụ trên 1 bit dữ liệu ở bộ thu phát là Eelec=50nJ/bit đối với bộ thu phát tốc độ 1Mpbs. Điều này có nghĩa là phần điện tử sẽ tiêu tán 50mW khi hoạt động (thu hoặc phát dữ liệu).

Hai tham số: €friss-amp và €two-ray-amp tùy thuộc vào độ nhạy máy thu yêu cầu, và nhiễu tạp âm máy thu, do đó công suất truyền cần phải điều chỉnh để công suất máy thu lớn hơn một mức ngưỡng PR-thresh. Chúng ta có thể làm ngược lại từ ngưỡng của công suất máy thu để tính toán công suất truyền tối thiểu. Nếu tốc độ truyền là Rb thì công suất truyền Pt sẽ bằng năng lượng truyền trên bit ETx-amp(1,d) nhân với tốc độ:

Pt= ETx-amp(1,d)*Rb. (4.9)

Khi đó ta có :

Pt = ⎪⎨⎧εfruss−ampRbd 24 : d <dcrossover (4.10)

⎪⎩εtwo−ray−ampRbd : d ≥dcrossover

Sử dụng mô hình kênh truyền ở trên chúng ta sẽ có :

⎧εfriss−ampRbGtGr λ2 Pr =⎨⎪()4π2: d <dcrossover (4.11)

⎪22

⎩εtw0−ray−ampRbGtGrht hr : d ≥dcrossover

Và

εfriss−amp = Pr−thresh (4π 2 )2 (4.12)

RbGtGr λ

εtwo−ray−amp = Pr−thresh 2 2 (4.13)RbGtGrht hr

Do đó công suất truyền Pt sẽ là hàm của ngưỡng công suất bên thu và khoảng cách d

Đỗ Thị Tuyết ĐT6-K48 80 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Pt = ⎨⎧α1 Pr−threshd 24 : d < dcrossover (4.14)⎩α2 Pr −threshd : d ≥ dcrossover

Với α1 =G (4 tG π r )λ 22 ; α2 = GtGt 1 ht 2 hr 2 (4.15)

Chúng ta có thể xác định mức ngưỡng ở máy thu sử dụng việc đánh giá nhiễu ở máy thu. Nếu nhiễu sàn nhiệt là 99dBm và tạp âm nhiễu máy thu là 17dB2 và chúng ta yêu cầu tỉ số tín hiệu trên nhiễu ít nhất là 30dB để nhận tín hiệu k nhiễu, thì công suất nhận tối thiểu là :

PR-thresh > 30 + (-82)=-52 dBm (4.16) Do đó công suất nhận được ít nhất phải là -52dBm hay 6.3 nW để nhận thành công gói. Thay các giá trị vào (Gt=Gr=1, ht=hr=1.5m, L=1, f=914 MHZ, λ=0.328m, Rb=1Mbps). Ta có:

ε friss amp =10 pJ / bit / m2 (4.17)

−

εtwo−ray−amp =0.0013 pJ / bit / m4 (4.18)

Chúng ta sẽ sử dụng mô hình vô tuyến đơn giản kiểu thứ nhất như sau: Truyền bản tin k bit ở khoảng cách d sử dụng mô hình vô tuyến. ETx-elec : năng lượng/bit truyền ERx-elec: năng lượng /bit nhận €amp : hệ số của bộ khuêch đại Phương trình bên truyền:

ETx (k, d )= ETx−elec (k)+ ETx−amp (k, d )

2

ETx (k, d )= Eelec ∗ k +εamp ∗ k ∗ d

Phương trình bên nhận: Tx

Đỗ Thị Tuyết ĐT6-K48 81 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

ERx (k)= ERx−elec (k )

ERx (k )= Eelec ∗ k

Việc nhận bản tin cũng tiêu tốn năng lượng khá cao cho nên chúng ta cũng cần tối thiểu số lần truyền và nhận ở mỗi nút.

4.3.2. Giả thiết và thiết lập thông số ban đầu cho quá trình mô phỏng

Chúng ta có một số các giả thiết ban đầu như sau: Các nút trong mạng đều biết về topology của mạng Tất cả các nút trong toàn mạng đều có thể truyền dữ liệu trực tiếp

đến trạm cơ sở (Sink). Số nút trong mạng N=100 nút. Phạm vi mô phỏng mạng (50m x 50m), trạm BS đặt ở vị trí

(25m,150m).

Nếu phạm vi mô phỏng mạng là 100m x 100m , trạm BS đặt ở vị trí (50m,300m). Năng lượng ban đầu iniPower =0.25J ; 0.5J Năng lượng tiêu tốn khi xử lý một bit : Eelec=50nJ/bit Hệ số khuêch đại: ε friss−amp = 10 pJ / bit / m2

Chiều dài mỗi bản tin DATA k=2000 bit. Chúng ta sẽ mô phỏng trên Mobility Framework. Các nút trong mạng được phân

bố vị trí một cách ngẫu nhiên. Quá trình mô phỏng gồm các bước như sau: Bước 1: Tìm nút xa trạm BS nhất Bước 2: Thiết lập chuỗi Bước 3: Chọn nút chủ ế

Đỗ Thị Tuyết ĐT6-K48 82 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Bước 4: Truyền dữ liệu và xử lý lỗi khi nút chết

Chúng ta sẽđi lần lượt từng bước như trên.

Bước 1: Tìm nút xa nhất

Ban đầu BS sẽ đưa ra lệnh xây dựng mạng thông qua bản tin INITIATE_CONFIGURE_NETWORK. Sau đó BS broadcast bản tin BROADCASTING_POSITION cho toàn bộ nút trong mạng để tính toán khoảng cách từ các nút đó đến BS. Bản tin BROADCASTING_POSITION:

cplusplus {{#include "NetwPkt_m.h"}};

class NetwPkt;

message BSP extends NetwPkt {

fields:

int posX;

int posY;

}

Tham số posX và posY chứa tọa độ của trạm BS. Chúng ta có thể lấy được vị trí hiện tại của BS thông qua việc đăng ký biến HostCoor với Blackboard

posX = (int)(HostCoor.x) posY = (int)(HostCoor.y)

Hình (4.9) là giao diện của Mobility khi mô phỏng, miêu tả quá trình broadcast của trạm cơ sở (BS) đến các nút trong mạng, host[0] trong hình chính là trạm cơ sở. Đường nét đứt là đường truyền vô tuyến của bản tin. Channel control điều khiển việc di động của các host và tính toán khoảng cách giao thoa giữa các nút. Trong phần mô phỏng này ta giả sử các nút cảm biến không di động. đ

Đỗ Thị Tuyết ĐT6-K48 83 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Hình 4.9 Trạm BS gửi broadcast đến cho các nút trong mạng

Các nút nhận được bản tin này sẽ tính toán khoảng cách đến BS nhờ thông số tọa chứa trong bản tin. Và sau đó gửi reply lại bằng bản tin REPLY_BROADCASTING_POSITION:

cplusplus {{#include "NetwPkt_m.h"}};

class NetwPkt;

message RBSP extends NetwPkt {

fields:

double distance;

};

Trong đó: Tham số distance sẽ chứa khoảng cách của các nút đến BS. Sau khi BS nhận được bản tin này, BS sẽ so sánh các giá trị distance và tìm ra MaxDistance, tức là sẽ tìm ra nút xa nhất so với BS.

Bước 2: Thiết lập chuỗi

Sau khi tìm được nút xa nhất, BS gửi thông báo đến nút đó thông qua bản tin MAX_DISTANCE (hình 4.10). ị

Đỗ Thị Tuyết ĐT6-K48 84 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Nút xa nhất này chính là nút gốc của chuỗi. Nút này nhận được bản tin MAX_DISTANCE sẽ bắt đầu tìm nút khác gần nó nhất và cho vào chuỗi. Nó sử dụng bản tin FIND_NODE_INTO_CHAIN có các trường giống như bản tin BROADCASTING_POSITION của BS .

Hình 4.10 Trạm BS gửi bản tin Max Distance đến nút xa nhất

Các nút xung quanh nhận được bản tin này và gửi bản tin đáp trả lại REPLY_FIND_NODE_INTO_CHAIN. Nút này căn cứ vào các giá trị distance trong các bản tin để lựa chọn ra nút gần mình nhất có địa chỉ MinAddr và khoảng cách Min. Sau đó nó gửi bản tin mời gọi vào chuỗi INVITE_INTO_CHAIN như sau:

cplusplus {{#include "NetwPkt_m.h"}}; class NetwPkt; message InvitePkt extends NetwPkt { fields: int vitri; int index; }; ứ

Đỗ Thị Tuyết ĐT6-K48 85 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Hình 4.11 Nút xa nhất chuỗi gửi bản tin Invite mời nút gần nhất vào chuỗi

Cứ như vậy, sau khi nút này vào chuỗi thì lại tiếp tục mời gọi các nút còn lại trong chuỗi vào chuỗi.

Hình 4.12 Các nút kết nối vào nhau tạo thành chuỗi http://www.ebook.edu.vn

Đỗ Thị Tuyết ĐT6-K48 86 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Chú ý: Ta nên khai báo thêm một biến vaoChuoi kiểu bool đểđánh dấu khi một nút đã vào chuỗi rồi. Điều này sẽ rất thuận lợi và các nút một khi đã vào chuỗi rồi sẽ không tính toán khoảng cách khi nhận được bản tin FIND_NODE_INTO_CHAIN.

Hình 4.13 Chuỗi sau khi thiết lập xong.

Sau khi tất cả các nút đều đã vào chuỗi, nút cuối cùng vào chuỗi sẽ gửi bản tin REQUEST_CHOSING_HEADER đến cho trạm BS. BS sẽ bắt đầu khởi tạo quá trình chọn nút chủ bằng cách gửi đến nút gốc của chuỗi, chính là nút có khoảng cách xa BS nhất.

Bước 3: Chọn nút chủ

Nút xa nhất bắt đầu tính toán tỉ lệ: Ratio=curPower/distance

Với curPower là năng lượng hiện tại của nút và cho vào bản tin truyền dọc theo chuỗi, tại các nút: khi nhận được bản tin cũng tính toán giá trị này và sau đó gửi so sánh giá trị Ratio của nó và của bản tin nhận được. Nếu nhỏ hơn nó đơn giản sẽ foreward đi còn ngược lại sẽ thay thế bằng Ratio của mình và lại truyền đi. Nút có giá ử

Đỗ Thị Tuyết ĐT6-K48 87 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

trị Ratio cao nhất sẽđược chọn làm nút chủ. Nút chủ sẽ thông báo cho các nút khác biết vị trí của các nút và nó là nút chủ.

Bước 4: Truyền dữ liệu và xử lý lỗi khi một nút chết

Nút chủ bắt đầu gửi TOKEN đến nút gốc chuỗi để bắt đầu một vòng truyền dữ liệu, sau đó như thuật toán đã nêu ở trên, các nút sẽ lần lượt tích hợp dữ liệu của nó và truyền đến nút chủ. Sau đó nút chủ sẽ tập hợp dữ liệu của nó và hai bản tin từ hai phía truyền về và truyền đến Sink. Mỗi bản tin có kích thước k=2000 bit.

Tại các nút mỗi khi nhận được bản tin sẽ tính toán năng lượng nhận và truyền theo công thức đã đề cập ở mô hình mô phỏng.

Phương trình tính toán năng lượng khi truyền bản tin:

ETx (k, d )= ETx−elec (k)+ ETx−amp (k, d )

2

ETx (k, d )= Eelec ∗ k +ε amp ∗k ∗dPhương trình tính toán năng lượng khi nhận bản tin:

ERx (k)= ERx−elec (k )

ERx (k )= Eelec ∗ k

Sau mỗi lần nhận gói tin, các nút sẽ kiểm tra xem còn đủ năng lượng để truyền và nhận không? Nếu không đủ năng lượng thì nó sẽ không truyền gói đi và cũng sẽ không nhận gói tin. Lúc này một nút coi như là đã chết, các nút khác dựa vào thời gian timeout, không thấy nút đó gửi dữ liệu đến sẽ thông báo đến nút chủđể cập nhật lại chuỗi. Chuỗi mới sẽ bỏ qua nút chết. Sau đó nút chủ lại gửi TOKEN để bắt đầu thu thập dữ liệu.

Khi nút chết, nút chủ có nhiệm vụ gửi thông báo đến BS, BS đếm số nút chết và sau đó BS đưa ra kết quả. đế

Đỗ Thị Tuyết ĐT6-K48 88 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

4.3.3. Kết quả mô phỏng

Sau đây ta sẽđưa ra kết quả mô phỏng của ba giao thức: truyền tin trực tiếp, LEACH, PEGASIS. Trong bảng (4.10) là kết quả khi mô phỏng, phần đậm ứng với kích thước mạng là (50m,50m), phần còn lại là kết quả mô phỏng ứng với mạng có kích thước (100m, 100m).

Trong bảng (4.2) ta thấy, các nút bắt đầu chết đồng loạt sau khi 20% nút chết. Bởi vì khoảng cách giữa các nút lúc này lớn hơn rất nhiều, việc lựa chọn nút chủ diễn ra thường xuyên mỗi vòng và các nút cũng nhanh chóng tiêu hao năng lượng hơn.

Bảng 4.2 Số vòng khi 1%, 20%, 50%, và 100% nút chết

Hình (4.14) và (4.15) chỉ ra số vòng khi 1% , 20%, 50% và 100% nút chết với kích thước mô phỏng mạng là (50m,50m) và (100m,100m). Từ kết quả ta nhận thấy rằng, số vòng PEGASIS đạt được gấp 2 lần so với LEACH với kích thước mạng là (50m,50m). ế

Đỗ Thị Tuyết ĐT6-K48 89 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

Hình 4.14 Kết quả khi mô phỏng mạng có kích thước (50m,50m) với năng lượng ban đầu của nút là 0.25 J

Hình 4.15 Kết quả mô phỏng khi kích thước mạng là (100m.100m) với năng lượng của nút ban đầu là 0.5J

Năng lượng ban đầu của nút trong hình (4.9) là 0.25J và hình (4.10) là 0.5J . Mức năng lượng tăng gấp đôi dẫn đến số vòng cũng tăng gấp đôi . Với kích thước mạng (100m,100m) thì số vòng khi thực hiện PEGASIS gấp ba so với LEACH. đ

Đỗ Thị Tuyết ĐT6-K48 90 Đồ án tốt nghiệp Chương 4 Mô phỏng PEGASIS

4.4. Kết luận và hướng nghiên cứu tiếp theo

Trong chương này đã đưa ra kết quả mô phỏng của PEGASIS. Kết quảđã cho thấy PEGASIS khắc phục được nhược điểm của LEACH bằng cách loại bỏ lượng mào đầu của thông tin các cụm động, tối thiểu hóa khoảng cách truyền và nhận giữa các nút trong mạng, và chỉ sử dụng một lần truyền dữ liệu hợp nhất trên mỗi vòng đến trạm cơ sở. Các nút thay nhau truyền dữ liệu hợp nhất đến trạm cơ sở làm cân bằng năng lượng tiêu tán trong mạng và tăng khả năng chống lại lỗi khi các nút chết ở vị trí ngẫu nhiên.

Việc phân bố năng lượng trong mạng tải làm tăng thời gian sống và chất lượng của mạng. Việc mô phỏng cho thấy giao thức PEGASIS tốt hơn LEACH và thậm chí cải thiện hơn khi kích thước mạng tăng.

Tuy nhiên, một vấn đề nổi trội trong PEGASIS là trễ truyền, nút chủ phải đợi nhận được bản tin dữ liệu hợp nhất của các nút sau đó mới truyền đến trạm cơ sở. Hơn nữa thường xảy ra hiện tượng nút cổ chai tại nút chủ. Hướng nghiên cứu tiếp theo cần khắc phục được các nhược điểm này. d

Đỗ Thị Tuyết ĐT6-K48 91

KẾT LUẬN

Khái niệm mạng cảm biến tương đối còn lạ lẫm đối với nhiều người làm việc trong lĩnh vực viễn thông. Đồ án này em đã trình bày một cách tổng quan nhất về mạng cảm biến. Với tính năng ưu việt và ứng dụng đa dạng mà không phải mạng nào cũng có, trong tương lai không xa mạng cảm biến sẽ được phát triển rộng rãi và nhanh chóng. Em hy vọng với đồ án này, sẽ góp phần vào việc nghiên cứu về lĩnh vực còn tương đối mới mẻ này ở Việt Nam.

Trong phạm vi đồ án tốt nghiệp này, em đã nghiên cứu được những nét khái quát nhất về mạng cảm ứng và mô phỏng được một giao thức định tuyến thường được dùng trong mạng. Do kiến thức còn hạn chế, nên đồ án tốt nghiệp của em không thể tránh khỏi những thiếu sót, em rất mong nhận được sự phê bình, đóng góp của các thầy trong bộ môn cũng như trong khoa đểđồ án của em được hoàn thiện.

Một lần nữa em xin chân thành cám ơn TS. Trần Ngọc Lan - Bộ môn Kỹ thuật thông tin - Khoa Điện Tử Viễn Thông - Trường Đại Học Bách Khoa Hà Nội đã nhiệt tình giúp đỡ em trong thời gian vừa qua.

Hà Nội, Tháng 5 Năm 2008

Sinh viên thực hiện

Đỗ Thị Tuyết ạ

Đỗ Thị Tuyết ĐT6-K48 92

Tài liệu tham khảo

[1]. Holger Karl Andreas Willig, Protocols and Architectures for Wireless Sensor Networks, Wiley, 2005.

[2]. S. Linsay, PEGASIS: power-Efficient Gathering in Sensor Information Systems, Computer Systems Reasearch Department The Aerospace Corporation

P.O. Box 92957, Los Angeles, CA 90009-2957.

[3]. Jamal N. Al-Karaki Ahmed E. Kamal, Routing Techniques in Wireless Sensor Networks, Dept. of Electrical and Computer Engineering Iowa State University, Ames, Iowa 50011.

[4]. Armin Veichtlbauer, Peter Dorfinger Salzburg, Modeling of Energy Efficient Wireless Communication, Research Forschungsgesellschaft mbH, Advanced Networking Center Salzburg, Austria.

[5]. I.F. Akyildiz, W. Su*, Y. Sankarasubramaniam, E. Cayirci, "Wireless sensor networks: a survey", Broadband and Wireless Networking Laboratory, School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA, Received 12 December 2001; accepted 20 December 2001

[6]. http://ceng.usc.edu/~anrg/SensorNetBib.html truy nhập cuối cùng ngày 10/5/2008. http://www.ebook.edu.vn

Đỗ Thị Tuyết ĐT6-K48 93