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 .

Để có thể hoàn thành được 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.

Hà nội, tháng 5 năm 2008

Sinh viên

Đỗ Thị Tuyết

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.

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 .

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.

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.

Mục lục

DANH SÁCH HÌNH VẼ.............................................................................................. iii

DANH SÁCH BẢNG BIỂU ..........................................................................................v

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

Chươ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........................................................39

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

DANH SÁCH HÌNH VẼ

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

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

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

Hình 1.4 Cấu trúc phẳng của mạng cảm biến ...............................................................10

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

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

Hình 1.7 Ứng dụng trong quân đội ...............................................................................15

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

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

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

Hình 2.2 Đồng bộ bên phát/bên nhận và bên nhận/bên nhận. ......................................23

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

Hình 2.4 LTS multihop phân bố ...................................................................................29

Hình 2.5 Ví dụ về RBS ..................................................................................................31

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Hình 4.12 Các nút kết nối vào nhau tạo thành chuỗi .....................................................86

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

Hì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....................................................90

Hình 4.15 Kết quả mô phỏng khi kích thước mạng......................................................90

là (100m.100m) với năng lượng của nút ban đầu là 0.5J...............................................90

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

v

ID

ADC

RF

MAC

UTC

GPS

LTS

RBS

RSS

TDOA

AOA

TDOA

RSSI

PLF

TDMA

CDMA

ARP

BS

WSN

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

Identification

Analog to Digital Converter

Radio frequency

Media Access Control

Coordinated Universal Time

Global Positioning System

Lightweight time synchronization protocol

Reference broadcast synchronization).

Received signal strength

Time of arrival

Angle of arrival

Time difference of arrival

Receiver Signal Strength Indicator

Perceptive localization framework

Time Division Multiple Access

Code Division Multiple Access

Address Resolution Protocol

BaseStation

Wireless Sensor Network

vi

1.1. Giới thiệu

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

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

1

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.

2

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

3

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.

4

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

5

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ể

6

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ữ

7

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.

8

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.

9

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.

10

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 2: Phân phối

Cấp 1 : Tính toán

Cấp 0: Cảm

nhận

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

11

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

n ⎟⎟⎠

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

12

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.

13

• 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

14

đượ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

15

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

16

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.

17

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.

18

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.

19

• 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 đó θ = arcsinx. 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.

20

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

21

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

x ×10−6 s cần

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

1

≤

d

H t

≤ + ρ

( ) 1

(2.1)

1

+ ρ

dt

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.

22

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

23

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

3=2+τ + tP,

24

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

25

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

(t6cộ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 = Δ

L t

(t1) := Li(1) −j(1) , chúng ta giả sử không có bất kì sự trôi nào giữa các

đồng hồ trong khoảng thời gian từ t1đến t8, do đó O = Δ(t*) với các nút t*∈ [ ]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 Ljt

( ) − L t

( ) .

6

j

5

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

[

I = Lit

+ τ + t t − τ − t − t −

L

(t5))] . Nếu chúng ta giả sử thời gian sử

P

, Li( )

P

(Lj( )

j

1

8

6

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)

L t τ −τ − − −

( ) + + tP+ L t t t L t

1

8

(Lj( )

j

L t

=

6

5

(2.2)

5

2

Vì thế,

26

L t

( ) + L t

− L t

− L t

8

j

j

O

= Δ(t ) =

L t

−

L t

=

1

6

5

(2.3)

j

5

5

5

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.

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

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à hihop 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 σi2 = 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ó.

27

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.

28

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ể

29

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.

30

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ễ

31

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

32

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

33

đượ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.

34

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

35

đế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ể

36

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.

37

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.

38

• 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

39

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

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

40

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.

41

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

42

Giao thức

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

thức thức thức loại chuyển vào hợp số định phức năng đường

Dựa

vào

chọn

đường

trung

tâm

dữ

liệu

phân

cấp

dựa

trên

vị trí

hỏi/đáp

liệu

vị trí

tạp

của

trạng

thái

định

cỡ

yêu

cầu

SPIN

x

Ngang

hàng

Có thể Có

Có

Không Không Thấp Hạn

chế

Có

Có

Directed

Diffusion

x

Ngang

hàng

Hạn

chế

Có

Có

Có

Không Thấp Hạn

chế

Có

Có

Rumor

GBR

x

x

Ngang

hàng

Ngang

hàng

Rất

hạn

chế

Hạn

chế

Không Có

Không Có

Không Không Thấp Tốt Không Có

Không Không Thấp Tốt Không Có

CADR

x

Ngang

hàng

Không Không Có

Không Không Thấp Hạn

chế

Không Không

COUGAR x

Ngang

hàng

Không Không Có

Không Không Thấp Hạn

chế

Không Có

ACQUIRE x

Ngang

hàng

Hạn

chế

Không Có

Không Không Thấp Hạn

chế

Không Có

LEACH

X

Phân

cấp

Nút

gốc cố

định

Không Có

Có

Không Nút

chủ

nhóm

Tốt Không Không

TEEN&

APTEEN

x

X

Phân

cấp

Nút

gốc cố

định

Không Có

Có

Không Nút

chủ

nhóm

Tốt Không Không

PEGASIS

X

Phân

cấp

Nút

gốc cố

định

Không Không Có

Không Nút

chủ

nhóm

Tốt Không Không

MECN&

SMECN

X

Phân

cấp

Không Không Không Không Không Thấp Thấp Không Không

GAF

GEAR

X

x

x

Dựa

theo

vị trí

Dựa

theo

vị trí

Không Không Không Không Không Thấp Tốt Không Không

Không Không Không Không Không Thấp Hạn Không Không

chế

SAR

x

Dựa

theo

vị trí

Không Có

Có

Không Có

Trung

bình

Hạn

chế

Không Có

SPEED

x

Dựa

theo

QoS

Không Không Không Không Có

Trung

bình

Hạn

chế

Không Có

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.

43

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

44

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

45

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

46

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.

47

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ị

Type = chim ruồi

Interval=20ms

Duration=10s

Field=[(x1,x2),(y1,y2)]

Miêu tả

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

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

Thời gian sống của Interest

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ữ

48

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

49

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ề

50

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

nếu n ∈ G (3.1)

1 − p * (r mod1/ )

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à

51

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.

52

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ừ

53

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:

54

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.

55

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

56

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:

57

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.

58

3.8. Kết luận

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

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.

59

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.

60

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.

61

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

62

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

63

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.

64

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

65

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

66

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 :

67

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

68

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.

69

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 here

Enter_Method_Silent();

// in case not you but your base class subscribed:

BaseClass::receiveBBItem(category, details,

scopeModuleId);

// react on the stuff that you subscribed

if(category == catItem) {

someBBItemPtr =

static_cast<const SomeBBItem *>(details);

// do something

}

70

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

71

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.

72

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:

73

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

74

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:

75

4.3. Mô phỏng

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

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

76

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

Trong đó:

d

crossover

=

4π

λ

h

Lhrt (4.1)

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 :

PtG G λ2

( ) =

P d

(4.2)

Trong đó :

(4 )

2

πd L

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 :

77

2 2

P G G h h

P d

r=

4

(4.3)

Trong đó :

d

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

⎧

−

P

42

:d

<

86.2m

Pr= ⎨

⎪6.82 10

P

d

:d ≥

86.2m

(4.4)

⎪

2.25

⎩

d4

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.

78

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

( ) =

ETxd E

−

( ) +

E

−

( )d

(4.5)

Tx elec

lE + lε

Tx amp

<

ETxd

=

⎪

⎨

lE

elec

+ lε

−

friss amp

d2: d d

4:≥

crossover

(4.6)

Bên nhận:

⎪⎩

elec

− −

two ray ampd

d dcrossover

E

Rx

E

= −

Rx elec

(4.7)

ERx( ) = 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

79

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à Rbthì 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ó :

⎪

ε

−

R d2

:

<

d d

P

=

⎨

fruss amp b

crossover

(4.10)

ε

⎪⎩

− −

R d4

:

d d

two ray amp b

crossover

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

⎧

ε

−

G λ2

P =

⎪

friss ampRbGt r

( )2

:

<

d d

crossover

(4.11)

⎨

⎪ε

2 2

:

⎩

− −

h

d d

Và

tw0 ray ampRbGtGrht r

ε −=−

friss ampPr thresh

( )2

λ2

crossover

(4.12)

ε

−=

two−ray amp

G

RbGtr

−

Prthresh

2 2

(4.13)

cách d

h

RbGtGrhtr

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

80

⎧α

−

d2

:

<

d d

P = ⎨

1Pr thresh

crossover

(4.14)

α

⎩

2

−

d

4

:

d d

Prthresh

( )2

crossover

1

Với α

=

; α =

(4.15)

1

GtGr

λ2

2

2 2

GtGththr

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à 17dB2và 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:

E

Tx

( ) =

d E

−

( ) +

E

−

( )d

E

( ) =

Tx elec

∗ + ε

Tx amp

∗ k ∗ d2

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

Tx

d Eelec

k

amp

81

E

Rx

E

= −

Rx elec

ERx( ) = 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ủ

82

• 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

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.

83

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

84

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;

};

85

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

86

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á

87

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:

E

Tx

( ) =

d E

−

( ) +

E

−

( )d

E

( ) =

Tx elec

∗ + ε

Tx amp

∗ k ∗ d2

Tx

d Eelec

k

amp

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

E

Rx

E

= −

Rx elec

ERx( ) = 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ả.

88

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

89

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.

90

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.

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

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.

93