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


CHƯƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY 1
1.1 Giới thiệu chung 1
1.2 Đặc điểm và kiến trúc giao thức mạng 3
1.2.1 Đặc điểm

3

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

4

1.3 Ứng dụng 6
1.3.1 Thu thập dữ liệu môi trường 6
1.3.2 Giám sát an ninh

7

1.3.3 Theo dõi đối tượng

8

1.4 Kết luận 8
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 09
2.1
Các vấn đề gặp phải khi sử dụng TCP/IP trong mạng WSN
09
2.2 Giải pháp sử dụng TCP/IP cho mạng cảm biến không dây 11
2.2.1 Gán địa chỉ IP theo không gian

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

ROM Read-Only Memory
RAM Random Access Memory
GPS Global Positioning System
RF Radio Frequency
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 Shortest Paths Tree
GIT Greedy Incremental Tree
RTP Real-time Transport Protocol
ESB Embedded Sensor Board
uIP Micro IP
RFC Request for Comments
ICMP Internet Control Message Protocol
RTT Round-Trip Time
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
Luận văn thạc sĩ Đại học Công nghệ - ĐHQGHNĐặng Thị Sương -

Hình 2.5: Gán địa chỉ cho các node với z = 1, SN = 0 15
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
Luận văn thạc sĩ Đại học Công nghệ - ĐHQGHNĐặng Thị Sương -
K16Đ2

văn được hoàn thiện hơn.
Luận văn thạc sĩ Đại học Công nghệ - ĐHQGHNĐặng Thị Sương -
K16Đ2Em 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 quá 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è luôn 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ư quá trình
nghiên cứu, hoàn thành luận này.
Hà Nội, tháng 10 năm 2014
Học viên

Đặng Thị Sương Luận văn thạc sĩ Đại học Công nghệ - ĐHQGHNĐặng Thị Sương -
K16Đ2

tháng đến vài năm) và có thể hoạt động trong môi trường khắc nghiệt (chất độc, ô nhiễm,
nhiệt độ không ổn định ).
Các node cảm biến được triển khai trong một trường cảm biến (sensor field) được minh
họa trên hình 1.1. Mỗi node cảm biến trong mạng có khả năng thu thập số liệu, định tuyến
về bộ thu nhận (sink) để chuyển tới người dùng và định tuyến các bản tin mang theo lệnh
hay yêu cầu từ node sink đến các node cảm biến. Số liệu được định tuyến về phía node
sink theo cấu trúc đa liên kết không có cơ sở hạ tầng nền tảng tức là không có các trạm
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:
Luận văn thạc sĩ
2
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2Hì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 (10100kbps) và

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ố node 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 node cảm
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
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 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 soá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
Luận văn thạc sĩ
4
Đại học Công nghệ - ĐHQGHN

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

Luận văn thạc sĩ
5
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2Hì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

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.

Luận văn thạc sĩ
7
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2

Hình 1.4: Tô pô dạng cây cho mạng thu thập dữ liệu môi trường
Những vấn đề nảy sinh với cấu hình mạng này là:
- Hiện tượng thắt cổ chai (bottleneck) khi số lượng nút mạng lớn.
- Một vài nút mạng, vì một số lý do nào đó, không hoạt động. Để mạng tiếp tục hoạt
động nó phải có khả năng tự cấu hình lại, nghĩa là phải phát hiện ra các nút bị hỏng

8
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2

Trong các mạng an ninh việc giảm thời gian trễ của việc truyền cảnh báo quan trọng
hơn việc giảm chi phí năng lượng khi truyền. Điều này do các sự kiện cảnh báo rất hiếm
khi xảy ra. Đối với sự kiện xảy ra 1 lần năng lượng chủ yếu được dành cho việc truyền.
Giảm độ trễ truyền sẽ làm tăng năng lượng tiêu thụ vì các nút định tuyến phải giám sát
các kênh radio thường xuyên hơn.
Trong các mạng an ninh, phần lớn năng lượng tiêu thụ dành cho việc xác nhận chức
năng của các nút láng giềng và chuẩn bị chuyển tiếp thông báo cảnh báo. Việc truyền dữ
liệu hiện thời sẽ tốn một phần năng lượng của mạng.
1.3.3 Theo dõi đối tượng
Với các mạng cảm biến không dây, các đối tượng có thể được theo dõi đơn giản gắn
chúng với một nút cảm biến nhỏ. Nút cảm biến này sẽ được theo dõi khi chúng đi qua một
trường các nút cảm biến được triển khai tại những vị trí đã biết. Thay vì cảm nhận dữ liệu
môi trường, những nút này sẽ được triển khai để cảm nhận các thông điệp RF của các nút
gắn với các đối tượng. Những nút này có thể được sử dụng như những thẻ để thông báo
sự có mặt của một thiết bị. Một cơ sở dữ liệu có thể được sử dụng để ghi lại vị trí tương
đối của đối tượng với các nút mạng, do đó có thể biết vị trí hiện thời của đối tượng.
Không như mạng cảm biến hay mạng an ninh, các ứng dụng theo dõi sẽ liên tục thay
đổi topology khi các nút đi qua mạng. Trong khi sự kết nối giữa các nút tại các vị trí cố
định tương đối ổn định, sự kết nối tới các nút di động sẽ liên tục thay đổi. Thêm vào đó
tập hợp các nút bị theo dõi sẽ liên tục thay đổi khi các nút gia nhập hay rời khỏi hệ thống.
Điều chủ yếu là mạng có khả năng nhận biết một cách hiệu quả sự có mặt của các nút mới
đi vào mạng.
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

tâm
Luồng dữ liệu đặc
trưng
Tùy ý, một - một
Đến/ đi từ node sink, nhiều
node - một node, một node -
nhiều node
Tốc độ truyền Cao Thấp
Tài nguyên hạn chế Băng thông
Năng lượng, bộ nhớ, năng lực
xử lý
Thời gian sống của
mạng
Dài (năm, thập kỷ) Ngắn (ngày, tháng)
Hoạt độ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
Luận văn thạc sĩ
10
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -

11
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2

Đị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 hoà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

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
Luận văn thạc sĩ
13
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2

đ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
lân cận có cùng địa chỉ IP, SLIPA sẽ di chuyển các node lân cận này để đảm bảo mỗi địa
chỉ chỉ thuộc về một node mà không ảnh hưởng đến mỗi quan hệ không gian giữa các
node.
Giả sử tọa độ của node N
m

Sắp xếp thứ tự các node theo hướng Y:
Gán giá trị j bắt đầu từ 0 cho thứ tự các node theo hướng Y. Nếu hai hoặc nhiều node
có cùng tọa độ theo hướng Y, chúng có cùng giá trị số thứ tự j. Trong ví dụ 1, có 5 node
được gán giá trị j=0 và node trong tọa độ Y tiếp theo được gán j=1 chứ không phải j=6.

Hình 2.3: Sắp xếp các node theo hướng Y
Gán giá trị cho octet C trong địa chỉ IP
Trong bước này, ta biến đổi X
m
vào trong C trong khoảng từ 0 đến 255 theo phương
trình (1) và gán giá trị C theo phương trình (2).
Q = ( max{ X
m
} – min{ X
m
} )/ 255 (1)
C
m
= round( ( X
m
– min{ X
m
} ) / Q ) (2)
Luận văn thạc sĩ
14
Đại học Công nghệ - ĐHQGHN

Đặng Thị Sương -
K16Đ2


tới node N
m
sau khi quét.
a, Node thứ nhất trong zone, số dòng SN:
D
m
= D (k, SN) = SN, nếu k =1 (3)
b, Các node khác trong cùng một zone và có cùng số dòng SN: Node được quét
đầu tiên N
m
được gán D
m
= SN, node thứ hai N
m+1
được gán D
m+1
= SN + 1, …
D
m
= D (k, SN) = D (k - 1, SN) + 1 = D
m-1
+ 1, nếu k > 1 (4)
2, Gán SN: Số của dòng quét đầu tiên là 0 và việc gán của dòng quét tiếp được xác
định theo các dòng quét trước đó.
a, Khi j=0, SN = Scan(j) = 0 (5)
b, Khi j > 0, SN = Scan(j) = Scan(j - 1) + max{ R(z, Scan(j - 1)) } (6)
Ví dụ
Luận văn thạc sĩ
15
Đại học Công nghệ - ĐHQGHN