ĐỒ ÁN TỐT NGHIỆP
1 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
LỜI NÓI ĐẦU
Ngày nay, nhờ có sự tiến bộ vượt bậc trong khoa học và kỹ thuật, các công
nghệ mạng không dây ngày nay đang được phát triển mạnh mẽ và có nhiều ứng
dụng thiết thực trong cuộc sống. Với khả năng cơ động cao, thuận tiên trong sử
dụng, các công nghệ này đang dần dần thay thế các công nghệ mạng có dây truyền
thống. Song cũng do sự di chuyển của các thiết bị di động trong mạng làm cho topo
mạng luôn thay đổi, cùng với đó là tỷ lệ lỗi cao và giới hạn về băng thông, năng
lượng so với mạng có dây, nên các giao thức định tuyến trong mạng không dây trở
nên phức tạp hơn. Mô hình mã hóa nguồn phân tán trong mạng cảm biến không dây
là một chủ đề mới với khả năng giảm dung lượng tín hiệu tại nguồn bằng cách khai
thác sự tương quan giữa các nguồn với nhau, cho nên làm giảm khối lượng tính toán
cũng như năng lương tiêu thụ. Đồ án này được thực hiện nhằm mục đích tìm hiểu
sâu hơn về mã hóa nguồn phân tán sử dụng mã LDPC trong mạng cảm biến không
dây.
Trong quá trình thực hiện đồ án, em đã gặp rất nhiều khó khăn. Tuy nhiên
được sự giúp đỡ tận tình của thầy giáo Nguyễn Trung Dũng, cùng bạn trong nhóm
cũng như các bạn trong phòng lab em đã hoàn thành đồ án này.
Mặc dù đã cố gắng hết sức nhưng đồ án chắc chắn không tránh khỏi nhiều
thếu sót, vì thế em rất mong nhận được sự góp ý từ các thầy, cô giáo và các bạn để
hoàn thiện hơn.
Em xin gửi lời cảm ơn chân thành đến:
- Thầy giáo Nguyễn Trung Dũng
- Các bạn trong phòng lab WSN
- Cùng toàn thể gia đình, bạn bè đã hỗ trợ cho em.
Hà Nội, ngày 20/05/2014
Sinh viên thực hiện
distributed source coding using syndrome. The goal of the work is to find the best
practical implementation with respect to compression and coding of the data to be
transmitted by sensors in a wireless network. This is desirable because compression
will help reaching the tight requirements on transmitted effect in each sensor. The
recently developed scheme of distributed source coding is a revolutionary way of
doing this. LDPC code is the code used in the scheme reduces the number of data
bits transmitted power, reduce bit error rate and reducing energy consumption. The
effectiveness of this distributed network model will be tested using simulation tools
Matllab.
ĐỒ ÁN TỐT NGHIỆP
3 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
MỤC LỤC
LỜI NÓI ĐẦU 1
TÓM TẮT ĐỒ ÁN 2
MỤC LỤC 3
CÁC HÌNH VẼ SỬ DỤNG TRONG ĐỒ ÁN 5
CÁC TỪ VIẾT TẮT SỬ DỤNG TRONG ĐỒ ÁN 6
CHƯƠNG I : TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY 7
1.1 Giới thiệu về mạng cảm biến không dây 7
1.2 Cấu trúc mạng WSN 7
1.2.1 Cấu trúc 1 node mạng WSN 7
1.2.2 Cấu trúc mạng cảm biến không dây 9
1.2.3 Kiến trúc giao thức mạng WSN 10
1.2.4 Các yếu tố ảnh hưởng đến mạng WSN 13
1.3 Các vấn đề và mô hình trong mạng cảm biến không dây 16
CHƯƠNG II : MÃ NGUỒN PHÂN TÁN TRONG MẠNG CẢM BIẾN KHÔNG
DÂY 18
PHỤ LỤC 52
ĐỒ ÁN TỐT NGHIỆP
5 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
CÁC HÌNH VẼ SỬ DỤNG TRONG ĐỒ ÁN
Hình 1.1. Mô hình mạng cảm biến không dây………………………………………8
Hình 1.2. Các thành phần của một node cảm ứng………………………………… 9
Hình 1.2.2. Cấu trúc mạng cảm biến không dây………………………………… 11
Hình 1.2.3. Kiến trúc giao thức của mạng cảm biến………………………………12
Hình 1.4. Mạng WSN với hai mô hình mạng khác nhau………………………… 19
Từ trong tiếng Anh
Nghĩa tiếng Việt
WSN
Wireless Sensor Network
Mạng cảm biến không dây
DSC
Distributed Source Coding
Mã hóa nguồn phân tán
LDPC
Low Density Parity Check
Mã kiểm tra chẵn lẻ mật độ thấp
DISCUS
DSC in Sensor Network
Using Syndrome
Mã hóa nguồn phân tán trong mạng
cảm biến sử dụng Syndrome
ADC
Analog to Digital
Converter
Bộ chuyển đổi tín hiệu tương tự sang
tín hiệu số
S-W
Slepian-Wolf
Mã hóa Slepian-Wolf
QoS
Quanlity of Service
Chất lượng dịch vụ
MAC
Hình 1.1. Mô hình mạng cảm biến không dây
WSN là mạng liên kết các node với nhau nhờ sóng radio. Nhưng trong đó,
mỗi node mạng bao gồm đầy đủ các chức năng để cảm nhận, thu thập, xử lý và
truyền dữ liệu. Các node mạng thường là các thiết bị đơn giản, nhỏ gọn, giá thành
thấp,… và có số lượng lớn, được phân bố không có hệ thống trên phạm vi rộng, sử
dụng nguồn năng lượng (pin) hạn chế thời gian hoạt động lâu dài.
1.2 Cấu trúc mạng WSN
1.2.1 Cấu trúc 1 node mạng WSN
Mỗi node cảm ứng được cấu thành bởi 4 thành phần cơ bản như ở hình 1.2, bộ
cảm nhận (sensing unit), bộ xử lý (a processing unit), bộ thu phát (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).
ĐỒ ÁN TỐT NGHIỆP
8 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54 Bộ nguồn
Cảm biến ADC
Lưu trữ
Xử lý
Bộ phận
phát
Hệ thống định vị
Bộ phát
nguồn
Tự động cấu hình: Mạng cảm biến không dây cần phải cấu hình các thông số
một các tự động. Chẳng hạn như các nút có thể xác định vị trí địa lí của nó thông
qua các nút khác (gọi là tự định vị).
Xử lí trong mạng và tập trung dữ liệu: Trong một số ứng dụng một nút cảm
biến không thu thập đủ dữ liệu mà cần phải có nhiều nút cùng cộng tác hoạt động
thì mới thu thập đủ dữ liệu, khi đó mà từng nút thu dữ liệu gửi ngay đến sink sẽ rất
tốn băng thông và năng lượng. Cần phải kết hợp các dữ liệu của nhiều nút trong một
vùng rồi mới gửi tới sink sẽ tiết kiệm băng thông và năng lượng.
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 ứng được phân bố trong một sensor field như hình 1.2.2. Mỗi
một nút cảm ứng có khả năng thu thập dữ liệu và định tuyến lại đến các sink. Dữ
liệu được định tuyến lại đến các sink bởi một cấu trúc đa điểm. 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.
ĐỒ ÁN TỐT NGHIỆP
10 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54 Hình 1.2.2. Cấu trúc mạng cảm biến không dây
1.2.3 Kiến trúc giao thức mạng WSN
Trong mạng cảm ứng, dữ liệu sau khi được thu thập bởi các nút sẽ được định
tuyến gửi đến sink. Sink sẽ gửi dữ liệu đến người dùng đầu cuối thông qua internet
hay vệ tinh. Kiến trúc giao thức được sử dụng bởi nút gốc và các nút cảm biến (hình
người dùng (nút quản lí nhiệm vụ) thì có thể là giao thức gói ngừời dùng (UDP –
User Datagram Protocol) hay giao thức điều khiển truyền tải (TCP – Transmission
Control Protocol) thông qua internet hoặc vệ tinh. C.n giao tiếp giữa sink và các nút
cảm biến cần các giao thức kiểu như UDP v. các nút cảm biến bị hạn chế về bộ nhớ.
Hơn nữa các giao thức này cần phải tính đến sự tiêu thụ công suất, tính mở rộng và
định tuyến tập trung dữ liệu .
Lp mng : quan tâm đến việc định tuyến dữ liệu được cung cấp bởi lớp
truyền tải. 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 như mật độ các nút dày đặc, hạn chế về năng lượng…Do vậy thiết kế lớp mạng
trong mạng cảm biến phải theo các nguyên tắc sau:
- Hiệu quả về năng lượng luôn được xem là vấn đề quan trọng hàng đầu.
- Các mạng cảm biến gần như là tập trung dữ liệu
- Tích hợp dữ liệu và giao thức mạng.
- Phải có cơ chế địa chỉ theo thuộc tính và biết về vị trí
Có rất nhiều giao thức định tuyến được thiết kế cho mạng cảm biến không
dây. Nhìn tổng quan, chúng được chia thành ba loại dựa vào cấu trúc mạng, đó là
định tuyến ngang hàng, định tuyến phân cấp, định tuyến dựa theo vị trí. Xét theo
hoạt động thì chúng được chia thành định tuyến dựa trên đa đường
ĐỒ ÁN TỐT NGHIỆP
12 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
(multipathbased), định tuyến theo truy vấn (query- based), định tuyến thỏa thuận
(negotiation - based), định tuyến theo chất lượng dịch vụ (QoS – Quanlity of
Service), định tuyến kết hợp (coherent-based).
Lp kt ni d liu : Lớp kết nối dữ liệu chịu trách nhiệm cho việc ghép các
luồng dữ liệu, dữ khung dữ liệu, điều khiển lỗi và truy nhập môi trường. 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 – Media Access Control) 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.
gần 1 tháng hoạt động. Sự tiêu tốn và tính khả thi của giám sát và thay thế pin cho
một mạng rộng, thì thời gian sống dài hơn được thiết kế. Trong thực tế, pin rất cần
thiết trong rất nhiều ứng dụng để bảo đảm mạng WSN có thể tự động sử dụng
không cần thay thế trong vài năm. Sự cải thiện của phần cứng trong thiết kế pin và
kĩ thuật thu năng lượng sẽ giúp ta một phần trong việc tiết kiệm pin.
1.2.4.2 Sự đáp ứng
Giải pháp đơn giản nhất để kéo dài thời gian sống bên ngoài là điều khiển
các node trong 1 chu kì làm việc với chu kì chuyển mạch giữa 2 chế độ: chế độ ngủ
(mode sleep) và chế độ hoạt động (mode active). Trong khi quá trình đồng bộ ở chế
độ ngủ là 1 thách thức của WSN, vấn đề lớn liên quan đến nữa là chu trình ngủ 1
cách tùy ý có thể làm giảm khả năng đáp ứng cũng như hiệu suất của các sensor.
Trong một số ứng dụng, các sự kiện trong tự nhiên được tìm thấy và thông báo
nhanh, thì sự trễ bởi lịch ngủ phải được giữ ở giới hạn chính xác, thậm chí trong sự
tồn tại của nghẽn mạng.
1.2.4.3 Tính chất mạnh
Mục tiêu của WSN là cung cấp ở phạm vi rộng lớn, độ bao phủ chính xác
(fine-grained coverage). Mục tiêu này phổ biến ở số lượng lớn các thiết bị không
đắt tiền. Tuy nhiên các thiết bị rẻ thường kém tin cậy và thường dễ xảy ra lỗi. Tốc
độ lỗi cũng sẽ cao khi các thiết bị cảm ứng được triển khai trong các môi trường
khắt khe và trong vùng của kẻ địch. Giao thức thiết kế do đó cũng phải xây dựng kỹ
sảo để có thể đáp ứng tốt. Rất khó để chắc chắn rằng việc định dạng toàn cầu của hệ
thống là không bị hỏng với các thiết bị lỗi.
1.2.4.4 Hiệu suất
Các cải tiến của luật Moore trong công nghệ đảm bảo dung năng của thiết bị
về các mặt: xử lí nguồn, bộ nhớ - lưu trữ, thực hiện truyền nhận vô tuyến, cải thiện
ĐỒ ÁN TỐT NGHIỆP
14 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
nhanh chóng sự chính xác của bộ cảm biến. Tuy nhiên, vấn đề kinh tế được đặt ra ở
Ngoài ra, một điều trước tiên không biết chắc được là môi trường mà WSN
hoạt động có thể thay đổi mạnh mẽ qua thời gian. Các giao thức WSN sẽ làm cho
thiết bị có thể thích nghi với môi trường năng động trong khi nó đang sử dụng.
1.2.4.9 Thiết kế có hệ thống
WSN có thể là một ứng dụng cao cho từng chức năng riêng, nên cần có sự
cân bằng giữa hai yếu tố:
Mỗi ứng dụng cần có những đặc điểm khai thác ứng dụng riêng để đưa ra
những hoạt động phát triển cao.
Tính mềm dẻo: các phương pháp thiết kế phải phổ biến cho các hoạt động.
1.2.4.10 Cách biệt và bảo mật
Phạm vi hoạt động lớn, phổ biến rộng, nhạy của thông tin thu được bởi vì WSN làm
tăng yêu cầu chính cuối cùng là: bảo đảm sự cách biệt và bảo mật.
1.3. Ứng dụng của mạng WSN
WSN được ứng dụng đầu tiên trong các lĩnh vực quân sự. Cùng với sự phát
triển của ngành công nghiệp điều khiển tự động, robotic, thiết bị thông minh, môi
trường, y tế WSN ngày càng được sử dụng nhiều trong hoạt động công nhiệp và
dân dụng.
Một số ứng dụng cơ bản của WSN:
Cảm biến môi trường:
Quân sự: phát hiện mìn, chất độc, dịch chuyển quân địch,…
Công nghiệp: hệ thống chiếu sáng, độ ẩm, phòng cháy, rò rỉ,…
Dân dụng: hệ thống điều hòa nhiệt độ, chiếu sáng…
Điều khiển:
Quân sự: kích hoạt thiết bị, vũ khí quân sự,…
Công nghiệp: điều khiển tự động các thiết bị, robot,…
Môi trường: Giám sát lũ lụt, bão, gió, mưa, phát hiện ô nhiễm, chất thải
Y tế: định vị, theo dõi bệnh nhân, hệ thống báo động khẩn cấp,…
ĐỒ ÁN TỐT NGHIỆP
16 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
17 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
biệt (ad hoc). Sự khác nhau cơ bản giữa 2 mô hình này như dưới đây. Trong sơ đồ
ad hoc mỗi mút cần được trang bị cả 2 khả năng truyền và nhận, trong khi với sơ đồ
tập trung thì các nút chỉ cần phải truyền. được minh họa ở hình dưới đây:
(a) Fusion (b) Ad Hoc
Hình 1.4. Mạng WSN với hai mô hình mạng khác nhau
Trong bài luận này, ta sẽ tập trung vào sự thách thức ngày càng cao của việc
sử dụng năng lượng hiệu quả. Một cách để làm được điều này là tìm kiếm các
phương pháp tốt hơn cho việc nén cục bộ tại các nút bằng việc sử dụng sự tương
quan về thời gian. Ngoài ra, trong hầu hết các trường hợp là quan tâm đến sự tương
quan giữa các dữ liệu cảm ứng khác nhau. Chúng ta có thể sử dụng cá dư thừa để
giảm khối lượng dữ liệu của mỗi nút cần phải truyền. Để giải quyết vấn đề này thì
chúng ta sử dụng mã hóa nguồn phân tán (Distributed source coding). ĐỒ ÁN TỐT NGHIỆP
18 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
CHƯƠNG II. MÃ NGUỒN PHÂN TÁN TRONG MẠNG CẢM BIẾN
KHÔNG DÂY
2.1. Mã nguồn phân tán
Mã nguồn phân tán sử dụng khi mà có sự tương quan giữa tập các nguồn với
nhau. Đây chính là một trường hợp cụ thể của mạng cảm biến, mà có tương quan rất
là cao giữa các nút hàng xóm. Cá nhân mỗi nút sẽ nén dữ liệu không chỉ của chính
Y
Ẍ
Hình 2.1a. Mã hóa nguồn phân tán với thông tin biên tại bộ giải mã
Nếu muốn giải mã dữ liệu nén không tổn thất, theo lý thuyết mã hóa nguồn
cổ điển, có thể mã hóa với tốc độ bít Rx ≥ H(X) và Ry ≥ H(Y) lần lượt đối với
nguồn X và Y. Nếu xét đến sự tương quan giữa X và Y thì có thể mã hóa cả hai
nguồn với entropy chung của chúng thỏa mãn Rx + Ry ≥ H(X,Y). Nói cách khác,
với H(X,Y) = H(X) + H(X|Y) = H(Y) + H(Y|X), thì có thể mã hóa một nguồn với
entropy điều kiện tương ứng là Rx ≥ H(X|Y) hoặc là Ry ≥ H(Y|X). Slepian và Wolf
cho rằng có thể thực hiện được không cần liên lạc mạng giữa các nút cảm biến và
tốc độ bít đạt được là H(X) - H(X|Y) hoặc H(Y) - H(Y|X). Có thể dễ dàng nhìn thấy
rằng nó suy biến đến đến giá trị giới hạn của mã hóa không tổn thất cổ điển là H(X)
khi mà độ tương quan bằng không (tức là H(X|Y)=0). Chúng ta sẽ hiểu hơn về
nguyên lý mã Slepian-Wolf trong chương 2.2.
Lý thuyết mã hóa không tổn thất hiện nay chỉ được sử dụng trong trường hợp
là các nguồn riêng rẽ. Wyner và Ziv phát triển thêm bởi việc xem xét nguồn giá trị
liên tiếp, dẫn đến méo mó tín hiệu để có thể entropy hữu hạn. Bây giờ nó thường là
trường hợp đặc biệt của phân khúc mạng cảm biến. Cái chính là giới thiệu bước
lượng tử trước khi mã hóa S-W, tương tự như lượng tử hóa đi kèm với mã hóa
entropy bằng việc nén nguồn đơn. Bước lượng tử hóa này là một phần trong lý
thuyết biến dạng tốc độ và có thể được thực hiện bằng nhiều cách khác nhau phụ
thuộc vào sự phân bố cũng như bộ nhớ của giá trị đầu vào. Có thể tham khảo thuyết
biến dạng tốc độ ở phần phụ lục, mã Wyner-Ziv sẽ được miêu tả ở chương 2.4.
ĐỒ ÁN TỐT NGHIỆP
20 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
Sự tương quan giữa các nguồn có thể được mô hình hóa như là một kênh
tương quan ảo trong đó X là đầu vào và Y là đầu ra của kênh (hình 2.1b). Kênh này
21 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
Wolf chỉ ra rằng có thể mã hóa cùng tốc độ bít nếu hiểu được bộ mã hóa đã gửi cái
gì hay không. Lý thuyết này được nén theo công thức sau:
R
1
≥ H(X|Y), (1a)
R
2
≥ H(Y|X), (1b)
R
1
+ R
2
≥ H(X,Y), (1c)
Và có thể được vẽ như hình 2.2
Ry
Rx
H(X,Y)
H(Y|X)
H(X|Y)
Hình 2.2. Vùng tốc độ bít của 2 nguồn
Các điểm trong góc có thể đạt được bởi mô hình mã hóa bất đối xứng. Tất cả các
điểm trên đường H(X,Y) nhận được bởi cả mô hình mã hóa thời gian chung và mô
hình mã hóa đối xứng.
Slepian và Wolf chỉ ra rằng hai biến riêng biệt với các chữ cái giới hạn. Later
Cover mở rộng nó thành quá trình đặc biệt tùy ý, các chữ cái có thể đếm giới hạn và
một số bất kỳ của các nguồn tương quan. Trong thực tế các quá trình riêng rẽ không
010 101
011 100
001 110
X
U
00
01
10
11Hình 2.2.1: Cấu trúc coset
2.3. DSC tổn thất
Mã hóa Wyner – Ziv chính là mã hóa Slepian – Wolf với một phép đo gần
đúng, có nghĩa nó là sự nén tổn hao lấy từ sự méo tương quan nằm trong sự quan
tâm. Mã hóa nguồn tổn hao là cần thiết khi ta không có hẳn một kênh với công suất
vĩnh cửu ở sự bố trí ( hay nếu ta muốn có đủ khả năng để giải mã tín hiệu với một
ĐỒ ÁN TỐT NGHIỆP
23 | Sinh viên thực hiện : Hoàng Thanh Tùng– Điện Tử 1-K54
tiêu chuẩn chính xác ). Mã hóa Wyner – Ziv có thể được mô tả như một phép lượng
tử hóa bằng mã hóa Slepian Wolf như trong hình 2.4a.
Q Slepian-Wolf
X
U
Z
Nếu Y chỉ được hiểu tại phép giải mã, thì chức năng méo tỷ lệ Wyner – Ziv
được cho là :
2.3.2. Trường hợp Gaussian bậc hai
Trong trường hợp này, chúng ta có hai giá trị thống kê ngẫu nhiên Gaussian
là X
k
và Y
k
với tham số σ
x
2
và σ
y
2
và sự tương quan cùng hiệu quả ρ ( Chú ý : giá
trị ρ lớn hơn đưa ra nhiều nguồn tương quan trong trường hợp này ), và ta để D =
(D
x
, D
y
) là tiêu chuẩn méo. Sau đó nếu [23] :
d
x
≤
σ
, d
,
Ta lấy tỷ lệ nhỏ nhất bằng việc thiết lập d
x
= D
x
/ σ
x
2
og d
y
= D
y
/ σ
y
2
được lấy :
β
max
= β
Kèm theo thuyết làm méo tỷ lệ điển hình, chúng ta có thể mã hóa các nguồn
Gaussian ít ghi nhớ để
R
X
+ R
Y
=
σ
σ
2.4. Lựa chọn mã LDPC
Mã hóa nguồn phân tán sử dụng syndrome có thể được thực hiện bằng vài
cách phụ thuộc vào kỹ thuật mã hóa kênh mà ta lựa chọn. Kỹ thuật chung hay dùng
nhất sử dụng mã khối tuyến tính, mã cuộn và mã móc. Nghiên cứu về mã hóa kênh
dẫn đến hai kỹ thuật, là mã LDPC và mã Tubor. Mã Tubor là một mã móc được
ghép bởi một interleaving và một mã cuộn. Mã Tubor được sử dụng trong mã hóa
nguồn phân tán không được trình bày trong bài luận này. Trong bài luận này chúng
Copyright: Tài liệu đại học ©