ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
----------------*****----------------
ĐẶNG THỊ SƯƠNG
NGHIÊN CỨU CÁC GIẢI PHÁP ĐỂ SỬ DỤNG TCP/IP
CHO MẠNG CẢM BIẾN KHÔNG DÂY
(WIRELESS SENSOR NETWORKS)
LUẬN VĂN THẠC SỸ
NGÀNH CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG
Hà Nội - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
----------------*****----------------
ĐẶNG THỊ SƯƠNG
NGHIÊN CỨU CÁC GIẢI PHÁP ĐỂ SỬ DỤNG TCP/IP
CHO MẠNG CẢM BIẾN KHƠNG DÂY
(WIRELESS SENSOR NETWORKS)
Ngành: Cơng nghệ Điện tử - Viễn thông
Chuyên ngành: Kỹ thuật Điện tử
Mã số: 60 52 02 03
LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG
2.2.2 Nén tiêu đề .................................................................................................................... 16
2.2.3 Định tuyến ứng dụng phủ ........................................................................................... 19
2.2.4 Bộ giao thức TCP/IP uIP ............................................................................................ 21
2.2.5 Lưu trữ TCP phân tán.................................................................................................. 29
2.3 Kết luận ....................................................................................................................... 34
CHƯƠNG 3: PHÂN TÍCH, ĐÁNH GIÁ CÁC GIẢI PHÁP ĐỀ XUẤT ............................. 35
3.1 Đánh giá các giải pháp đề xuất để sử dụng TCP/IP trong mạng WSN ...................... 35
3.1.1 Gán địa chỉ IP theo không gian .................................................................................. 35
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
Đại học Công nghệ - ĐHQGHN
3.1.2 Nén tiêu đề .................................................................................................................... 37
3.1.3 Bộ giao thức TCP/IP uIP ............................................................................................ 38
3.1.4 Lưu trữ TCP phân tán.................................................................................................. 39
3.2 Tìm hiểu một ứng dụng của mạng WSN sử dụng TCP/IP ......................................... 44
3.2.1 Giới thiệu ...................................................................................................................... 44
3.2.2 Nền tảng phần cứng ..................................................................................................... 44
3.2.3 Hệ điều hành ................................................................................................................. 45
3.2.4 Cơ chế và giao thức mạng .......................................................................................... 45
3.2.5 Đánh giá ........................................................................................................................ 47
3.3 Kết luận ....................................................................................................................... 48
KẾT LUẬN ...................................................................................................................................
TÀI LIỆU THAM KHẢO ...........................................................................................................
Đặng Thị Sương - K16Đ2
MAC
Medium Access Control
UDP
User Datagram Protocol
DHCP
Dynamic Host Configuration Protocol
SIPA
Spatial IP Assigment
SLIPA
Scan-line IP Assignment
RAHC
Routing-Assisted Header Compression
CNS
Center at Nearest Sourc
SPT
API
Application Program Interface
ACK
Acknowledgement
SACK
Selective Acknowledgement
DTC
Distributed TCP Caching
RTO
Retransmission timeout
PDA
Personal Digital Assistant
NNTP
Network News Transfer Protocol
Đặng Thị Sương - K16Đ2
Hình 2.6: Gán địa chỉ cho các node với z=2, SN=0 ..................................................... 16
Hình2.7: Gán các node với z=0, SN=3 ......................................................................... 16
Hình 2.8: Hiển thị địa chỉ của tất cả các node ............................................................. 16
Hình 2.9: a, Định tuyến địa chỉ trung tâm b, Định truyến dữ liệu trung tâm ............... 20
Hình 2.10: Vịng lặp điều khiển chính........................................................................... 22
Hình 2.11: Lưu trữ TCP phân tán ................................................................................. 30
Hình 2.12: Việc truyền lại sai ....................................................................................... 32
Hình 2.13: DTC với SACK ............................................................................................ 34
Hình 3.1: Tỷ lệ gán thành công đối với các node cảm biến phân bố ngẫu nhiên ......... 36
Hình 3.2: Tỷ lệ gán thành công đối với các node cảm biến phân bố theo chiều dọc ... 36
Hình 3.3: uIP gửi dữ liệu với trễ mơ phỏng 10ms ........................................................ 39
Hình 3.4: Cấu trúc mơ phỏng........................................................................................ 40
Hình 3.5: Giảm tải DTC gần bộ gửi ............................................................................. 41
Hình 3.6: So sánh RTT bởi bộ gửi TCP với DTC ......................................................... 42
Hình 3.7: RTT nội bộ gần với bộ gửi ............................................................................ 43
Hình 3.8: RTT nội bộ gần với bộ nhận.......................................................................... 43
Hình 3.9: Mạng với các node backbone, node cảm biến .............................................. 46
Hình 3.10: Mạng cảm biến kết nối với mạng sao chép gồm các server NNTP ............ 47
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
Đại học Công nghệ - ĐHQGHN
LỜI MỞ ĐẦU
Ngày nay, nhờ có những tiến bộ nhanh chóng trong khoa học và công nghệ các 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 đã và đang
phát triển ngày càng mạnh mẽ và ứng dụng trong mọi lĩnh vực của đời sống xã hội. Mạng
Luận văn thạc sĩ
Đại học Công nghệ - ĐHQGHN
Em xin chân thành cảm ơn PGS.TS Vương Đạo Vy – Bộ môn Hệ thống Viễn thông –
Khoa Điện tử Viễn thông – Đại học Công nghệ – Đại học Quốc gia Hà Nội đã tận tình chỉ
bảo, hướng dẫn về chuyên mơn, phương pháp làm việc trong suốt q trình thực hiện luận
văn.
Em cũng xin gửi lời cảm ơn chân thành đến các thầy cô trong Khoa Điện tử Viễn thông
– Đại học Công nghệ – Đại học Quốc gia Hà Nội, gia đình và bạn bè ln tạo mọi đ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ư q trình
nghiên cứu, hồn thành luận này.
Hà Nội, tháng 10 năm 2014
Học viên
Đặng Thị Sương
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
Đại học Công nghệ - ĐHQGHN
LỜI CAM ĐOAN
Sau thời gian dài nghiên cứu và học tập, tôi đã hồn thành luận văn của mình với sự
giúp đỡ của thầy giáo hướng dẫn, các thầy cô trong khoa. Tơi xin cam đoan luận văn
khơng có sự trùng lặp với các cơng trình khoa học, luận văn đã cơng bố, đảm báo tính
trung thực rõ ràng và trích dẫn đầy đủ trong phần tài liệu tham khảo.
Tôi xin chịu trách nhiệm về nghiên cứu của mình.
Hà Nội, tháng 10 năm 2014
thu phát gốc hay các trung tâm điều khiển. Bộ thu nhận có thể liên lạc trực tiếp với người
dùng hoặc gián tiếp thông qua Internet hay vệ tinh.
Hình 1.2: Mơ hình triển khai các node cảm biến
Cấu tạo của một node cảm biến [1] như sau:
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
2
Đại học Cơng nghệ - ĐHQGHN
Hình 1.2: Cấu tạo của một node cảm biến
Bộ xử lý nhúng năng lượng thấp: Bộ xử lý có nhiệm vụ xử lý thông tin cảm
biến cục bộ và thông tin truyền bởi các node cảm biến khác. Các bộ xử lý gắn vào
thiết bị thường bị hạn chế về công suất nên được chạy trên các hệ điều hành có các
thành phần đặc biệt như hệ điều hành TinyOS.
Bộ nhớ: Lưu trữ dưới dạng ROM và RAM cả bộ nhớ chương trình (các lệnh
được thực hiện bởi bộ xử lý) và bộ nhớ dữ liệu (lưu các kết quả đo chưa qua xử lý và
đã qua xử lý bởi bộ cảm biến, lưu các thông tin cục bộ khác). Bộ nhớ của thiết bị
WSN thường bị giới hạn đáng kể do giá thành thiết bị thấp.
Bộ thu phát sóng vơ tuyến: Các thiết bị WSN có tốc độ thấp (10100kbps) và
là thiết bị vô tuyến không dây dải ngắn (nhỏ hơn 100m). Trong WSN thì truyền vơ
tuyến là một q trình sử dụng cơng suất mạnh nhất, do đó nó cần phải kết hợp có hiệu
quả cơng suất giữa chế độ ngủ (sleep) và chế độ hoạt động.
Cảm biến: Do giới hạn băng thông và nguồn, các thiết bị WSN chỉ hỗ trợ bộ
cảm biến tốc độ dữ liệu thấp. Với các ứng dụng bộ cảm biến đa chức năng, mỗi thiết
biến được triển khai có thể đến hàng trăm nghìn node, 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 node 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 node
cảm biến nên chi phí của mỗi node rất quan trọng trong việc điều chỉnh chi phí của
tồn mạng. Nếu chi phí của tồ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 node 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 node trong mạng rất nhiều nên các
node 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, 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 sốt, thích nghi với môi trường.
Môi trường hoạt động: Các node 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: Trong những mạng cảm biến đa hop, các node liên kết
với nhau bằng kết nối không dây. Các 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 node 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 node trong mạng giao tiếp với
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
4
vậy, việc duy trì và quản lý nguồn năng lượng đóng một vai trị quan trọng.
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 [2] đượ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 node có thể làm việc cùng nhau theo cách 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 node cảm biến.
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
5
Đại học Cơng nghệ - ĐHQGHN
Hình 1.3 Kiến trúc giao thức mạng cảm biến
Mặt phẳng quản lý năng lượng: điều khiển việc sử dụng nguồn năng lượng của node
cảm biến. Ví dụ: node cảm biến có thể tắt bộ thu sau khi nhận được một bản tin. Khi mức
năng lượng của node cảm biến thấp, nó sẽ phát quảng bá tới các node cảm biến lân cận
thông báo rằng nó có mức năng lượng thấp và 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à ghi lại sự chuyển động của các
node cảm biến để duy trì tuyến tới người sử dụng và các node cảm biến có thể theo dõi
các node cảm biến lân cận. Nhờ xác định được các node cảm biến lân cận, các node cảm
biến có thể cân bằng giữa giữa cơng suất và nhiệm vụ thực hiện.
Mặt phẳng quản lý nhiệm vụ: cân bằng và sắp xếp nhiệm vụ cảm biến giữa các node
trong một vùng quan tâm. Không phải tất cả các node cảm biến đều thực hiện nhiệm vụ
cảm nhận tại cùng một thời điểm. Kết quả là một số nút cảm biến thực hiện nhiều hơn các
nút khác tuỳ theo mức cơng suất của nó. Phần quản lý này là cần thiết để các nút cảm biến
quả của các node cảm biến.
Lớp truyền tải: Lớp giao vận cung cấp các dịch vụ tổ chức liên lạc đầu cuối từ các
node cảm biến có báo cáo cần chuyển tới node thu nhận (Sink) và node người sử dụng.
Lớp giao vận đặc biệt 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 ngồi khác.
Lớp cao hơn (ứ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.
Kiến trúc mạng như trên góp phần quản lý năng lượng của các nút mạng đồng thời
duy trì hoạt động của toàn mạng trong thời gian dài hơn.
1.3 Ứng dụng
Hầu hết các ứng dụng chủ yếu của mạng cảm biến không dây đều thuộc ba dạng ứng
dụng sau [3]: thu thập dữ liệu môi trường, giám sát an ninh và theo dõi đối tượng.
1.3.1 Thu thập dữ liệu môi trường
Mạng cảm biến không dây thu thập dữ liệu môi trường ra đời đáp ứng cho nhu cầu thu
thập thông tin về môi trường tại một tập hợp các điểm xác định trong một khoảng thời
gian nhất định nhằm phát hiện xu hướng hoặc quy luật vận động của môi trường. Bài toán
này được đặc trưng bởi một số lớn các nút mạng, thường xuyên cung cấp thông số môi
trường và gửi về một hoặc một tập trạm gốc (base station) có kết nối với trung tâm xử lý
(thường là hệ thống máy tính) phân tích, xử lý, đưa ra các phương án phù hợp hoặc cảnh
báo hay đơn thuần chỉ là lưu trữ số liệu. Yêu cầu đặt ra đối với các mạng kiểu này là thời
gian sống phải dài hay nói cách khác là các nút mạng phải tiêu thụ năng lượng ít. Mạng
cho ứng dụng thu thập dữ liệu môi trường thường sử dụng topology dạng cây, mỗi nút
mạng có một nút cha duy nhất. Trạm gốc sẽ là gốc của cây. Dữ liệu từ một nút bất kỳ sẽ
được gửi đến cho nút cha của nó, nút này lại tiếp tục chuyển đến cho nút cha tiếp theo
(nút ông), cứ như vậy, dữ liệu sẽ được chuyển về trạm gốc.
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
Giám sát an sinh
Một ứng dụng thứ hai của mạng cảm biến là giám sát an ninh. Các mạng giám sát an
ninh được tạo bởi các nút đặt ở những vị trí cố định trong mơi trường liên tục theo dõi
một hay nhiều cảm biến để nhận biết sự bất thường. Sự khác nhau chủ yếu giữa giám sát
an ninh và giám sát môi trường là các mạng an ninh không thu thập bất kỳ dữ liệu nào.
Điều này có tác động lớn đến việc tối ưu kiến trúc mạng. Mỗi nút thường xuyên kiểm tra
trạng thái các cảm biến của chúng nhưng chỉ truyền dữ liệu khi có sự vi phạm an ninh.
Việc truyền tức thời và tin cậy của thông điệp cảnh báo là u cầu chính của hệ thống.
Thêm vào đó, nó cần được xác nhận là mỗi nút vẫn hiện diện và hoạt động. Nếu một
nút bị lỗi, nó sẽ thể hiện một sự vi phạm an ninh cần được thông báo. Đối với các ứng
dụng giám sát an ninh, mạng cần được cấu hình sao cho các nút chịu trách nhiệm xác
nhận trạng thái các nút khác. Một cách tiếp cận là mỗi nút ngang hàng sẽ thông báo nếu
một nút khơng hoạt động. Mơ hình tối ưu của một mạng giám sát an ninh sẽ hoàn toàn
khác với mạng thu thập dữ liệu.
Trong cây thu thập số liệu, mỗi nút phải truyền dữ liệu của tất cả con cháu. Do đó, tối
ưu là cây ngắn và rộng. Ngược lại, với mạng an ninh cấu hình tối ưu sẽ có mơ hình mạng
tuyến tính. Cơng suất tiêu thụ của mỗi nút chỉ tỷ lệ với số các con của nó. Trong mạng
tuyến tính, mỗi nút chỉ có 1 con. Điều này phân phối đều năng lượng tiêu thụ của mạng.
Sự tiêu thụ năng lượng chủ yếu trong mạng an ninh là gặp các yêu cầu báo hiệu cảnh
báo khi có sự vi phạm an ninh. Mỗi khi nhận thấy, một sự vi phạm an ninh cần được
truyền tới trạm gốc ngay lập tức. Độ trễ của việc truyền dữ liệu qua mạng tới trạm gốc có
ảnh hưởng nhất định tới hiệu quả của ứng dụng. Các nút mạng cần có khả năng trả lời
nhanh chóng với các yêu cầu của các nút láng giềng để chuyển tiếp dữ liệu.
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
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.
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
9
Đại học Công nghệ - ĐHQGHN
CHƯƠNG 2: ĐỀ XUẤT CÁC GIẢI PHÁP ĐỂ SỬ DỤNG TCP/IP CHO
MẠNG CẢM BIẾN KHÔNG DÂY
2.1 Các vấn đề gặp phải khi sử dụng TCP/IP trong mạng WSN
Mạng cảm biến là một hệ thống thu thập thông tin dựa trên sự kết hợp của nhiều node
cảm biến nhỏ. Hầu hết các ứng dụng của node cảm biến là phát hiện, giám sát các hiện
tượng như giám sát hiện tượng tự nhiên, môi trường trong tòa nhà. Đối với các ứng dụng
này, mạng cảm biến không dây không thể hoạt động độc lập một cách hoàn toàn mà phải
được kết nối tới mạng ngoài để quản lý dữ liệu thu được bởi mạng cảm biến. Việc truy
nhập từ xa có thể thực hiện bằng cách kết nối mạng cảm biến với cơ sở hạ tầng mạng sẵn
có như mạng Internet tồn cầu, mạng nội bộ…Việc kết nối này gặp nhiều thử thách do
mạng WSN có nhiều đặc điểm khác biệt so với mạng IP truyền thống. Bảng 2.1 chỉ ra
một số điểm khác biệt giữa hai mạng này.
Bảng 2.1: Một số điểm khác biệt giữa mạng WSN và mạng IP truyền thống
Kiểu mạng
Mạng IP truyền
thống
Ứng dụng độc lập
xử lý
Dài (năm, thập kỷ)
Ngắn (ngày, tháng)
Giám sát, quản lý
Độc lập, tự cấu hình
TCP/IP là bộ giao thức phổ biến được sử dụng trong các mạng và được xem là một
phương pháp tiềm năng cho việc kết nối mạng cảm biến với mạng TCP/IP. Bằng cách
chạy trực tiếp bộ giao thức TCP/IP trong mạng cảm biến khơng dây có thể kết nối trực
tiếp mạng cảm biến với cơ sở hạ tầng mạng có dây mà không cần gateway hoặc node
trung gian đặc biệt nào. Hơn nữa kết nối được thực hiện đơn giản bằng cách kết nối một
hoặc nhiều node tới mạng TCP/IP. Trong khi, UDP được dùng để truyền dữ liệu cảm biến
tới nút sink, TCP được sử dụng cho các nhiệm vụ quản trị đòi hỏi sự tin cậy như truyền
cấu hình từ máy chủ trung tâm hoặc tải chương trình tới các node cảm biến và các nhiệm
vụ quản trị khác. Tuy nhiên, bộ giao thức TCP/IP được xem không phù hợp với mạng
cảm biến do các yêu cầu và điều kiện kết nối khắt khe mà mạng cảm biến thực hiện. Mặc
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
10
Đại học Công nghệ - ĐHQGHN
Luận văn thạc sĩ
11
Đại học Công nghệ - ĐHQGHN
Định tuyến địa chỉ trung tâm: Định tuyến trong mạng IP truyền thống dựa trên địa
chỉ host và mạng, mỗi gói tin được định tuyến xuyên suốt qua mạng. Các tuyến dựa vào
địa chỉ IP và tôpô mạng. Tuy nhiên, các ứng dụng tự nhiên của mạng cảm biến cho thấy
việc sử dụng cơ chế định tuyến dữ liệu trung tâm tốt hơn cơ chế định tuyến địa chỉ trung
tâm. Định tuyến dữ liệu trung tâm sử dụng các thuộc tính của các node và dữ liệu chứa
trong các gói để định tuyến các gói tới đích. Thêm vào đó, cơ chế định tuyến dữ liệu trung
tâm chấp nhận sự kết hợp dữ liệu và loại bỏ dữ liệu dư thừa trong mạng. Sử dụng định
tuyến ứng dụng phủ là phương pháp để thực hiện định tuyến dữ liệu trung tâm và tập
trung dữ liệu cho mạng cảm biến không dây TCP/IP
Giới hạn của node cảm biến: Để mạng cảm biến không dây có tính khả thi, các node
cảm biến thường bị giới hạn về bộ nhớ và năng lực xử lý. Việc thực hiện TCP/IP truyền
thống đòi hỏi quá nhiều nguồn tài nguyên cả về kích thước mã và bộ nhớ sử dụng đối với
các hệ thống nhỏ 8 hoặc 16 bit. Bộ giao thức TCP/IP hoàn chỉnh với vài trăm kilobyte
kích thước mã và vài trăm kilobyte yêu cầu RAM không thể đưa vào trong hệ thống với
hàng chục kilobyte RAM và ít hơn một trăm kilobyte mã.
Giao thức uIP được thiết kế cho mạng WSN chỉ có một tập hợp tối thiểu tuyệt đối các
tính năng sử dụng của bộ giao thức TCP/IP hồn chỉnh và có thể chạy bộ vi điều khiển 8
bít chỉ với vài trăm byte RAM.
Hiệu quả năng lượng và hiệu suất TCP: Giao thức chuỗi byte tin cậy TCP có vấn đề
về chất lượng nghiêm trọng trong mạng cảm biến cả về mặt lưu lượng và hiệu quả năng
lượng. Hơn nữa, báo nhận và cơ chế truyền lại end to end thực hiện bởi TCP dẫn đến việc
truyền lại tốn kém dọc tuyến giữa bộ phát và bộ nhận nếu một gói tin bị mất. Bởi vì mạng
cảm biến thường được thiết kế theo kiểu multi-hop, việc truyền lại riêng lẻ sẽ chịu chi phí
truyền nhận tại mỗi hop mà các gói được truyền qua. Có thể sử dụng TCP như là giao
Ta xem xét ví dụ về một mạng với địa chỉ IP được gán theo khơng gian được mơ tả
trong hình 2.2 . Trong mạng cụ thể này, mỗi node xây dựng địa chỉ của nó bằng cách kết
hợp tọa độ của nó với tiền tố địa chỉ của mạng. Tọa độ (x,y) của node được gán cho hai
octet cuối cùng trong địa chỉ IP. Tiền tố địa chỉ của mạng được cấu hình trong suốt thời
gian thực thi và thường là một trong các dải địa chỉ riêng.
Hình 2.2: Ví dụ về gán địa chỉ theo không gian và hai mạng con theo khu vực
Vì thơng tin định vị được mã hóa trong địa chỉ IP, ta có thể định nghĩa mạng con theo
miền như là một tập hợp các node cùng chia sẻ một tiền tố và thực hiện cơ chế quảng bá
theo miền tương tự với quảng bá mạng con IP truyền thống.
SIPA lợi dụng mối quan hệ giữa các vị trí khơng gian để tạo ra giao thức định tuyến.
Các node với địa chỉ lặp lại ở lân cận nhau giúp tránh các vấn đề định tuyến: các node
cùng địa chỉ có khả năng chia sẻ phần lớn các tuyến về phía các node. Tuy nhiên, nhược
Đặng Thị Sương - K16Đ2
Luận văn thạc sĩ
Đại học Công nghệ - ĐHQGHN
13
điểm của phương pháp này không đảm bảo là địa chỉ duy nhất vì hai hoặc nhiều hơn các
node lân cận có thể có cùng tọa độ vị trí và do đó thiết lập cùng địa chỉ.
2.2.1.2 Phương pháp gán địa chỉ SLIPA
Phương pháp gán địa chỉ quét dòng (Scan-Line IP Assignment (SLIPA)) [5] khắc
phục nhược điểm trên của SIPA. SLIPA sẽ quét mỗi node với cùng giá trị tọa độ Y nhỏ
nhất từ trái sang phải sau đó quét các node này với giá trị tọa độ Y kế tiếp. Lặp lại quá
trình này cho tới khi tất cả các node đều được quét và nếu hai hoặc nhiều hơn các node
14
Đại học Công nghệ - ĐHQGHN
Cách này đảm bảo rằng Cm không lớn 255 hoặc nhỏ hơn 0 và mối quan hệ không gian
theo hướng X được duy trì. Ta có thể phân chia tất cả các node trong mạng cảm biến
thành 256 vùng (zone) theo chiều ngang, mỗi vùng kí hiệu là z.
Gán giá trị cho octet cuối cùng (D) trong địa chỉ IP
Đầu tiên quét mọi node với cùng giá trị tọa độ Y bé nhất, sau đó quét tất cả các node
với giá trị tọa độ Y tiếp theo. Gán Dm cho nút Nm sau khi quét. Lặp lại quá trình cho đến
khi tất cả các node được quét để tìm hai hoặc nhiều hơn các node lân cận có thể có cùng
địa chỉ. Điều chỉnh các node này từng cái một cho đến khi khơng cịn node nào có cùng
địa chỉ. Một số thơng số và hàm cần để thực hiện thuật tốn này:
1, Định nghĩa thông số:
SN là số đường quét, phụ thuộc nhiều vào thời gian quét và bắt đầu từ 0.
k: node thứ k trong các node thuộc vùng z với cùng giá trị SN, sắp xếp từ trái
sang phải và bắt đầu từ 1.
2, Định nghĩa hàm:
R(z, SN): trả về số node trong cùng một vùng với cùng giá trị SN.
Scan(j): với giá trị j, hàm trả về giá trị SN tương ứng. Ví dụ Scan (0) bằng 0 và
thể hiện lần quét theo chiều ngang đầu tiên, Scan(1) là lần quét thứ 2…
D(k, SN): Hàm trả về octet cuối cùng trong địa chỉ IP của node thứ k trong vùng,
số đường quét SN.
Cách gán octet cuối cùng D trong địa chỉ IP của mỗi node và cách xử lý giá trị SN
như sau:
1, Gán D: Quét từ trái sang phải qua 256 zone với cùng số đường quét SN. Gán
Dm tới node Nm sau khi quét.
a, Node thứ nhất trong zone, số dòng SN:
Dm = D (k, SN) = SN, nếu k =1
Hình 2.4 : Quét tất cả các node với j = 0
Có hai node trong zone 1 có cùng số đường quét, node bên trái với k=1 không cần
phải di chuyển và gán D = 0 cho octet cuối cùng (hình 2.5). Node tiếp theo với k=2 phải
di chuyển lên 1 và được gán D = 1.
Hình 2.5: Gán địa chỉ cho các node với z = 1, SN = 0
Tron hình 2.6 có 3 node trong zone 2 với SN = 0. Tương tự như ở zone 1, node với k =
1 không phải di chuyển và được gán D = 0, node k=2 và k=3 di chuyển và được gán D=1
và D=2.
Đặng Thị Sương - K16Đ2
Copyright: Tài liệu đại học ©