1
A. MỞ ĐẦU
Sự ra đời của mạng nội bộ không dây (Wireless Local Area Network –
WLAN) đã tạo điều kiện thuận lợi cho người sử dụng thiết bị di động có thể truy
cập các ứng dụng mạng Internet mọi lúc mọi nơi và duy trì kết nối Internet ngay cả
khi họ đang di chuyển trong vùng phủ sóng. Trước đây, WLAN thường được triển
khai ở các phạm vi địa lý hẹp như quán cà phê, nhà hàng, khách sạn, trung tâm
thương mại,… Tuy nhiên, với sự phát triển nhanh chóng của thiết bị di động như
điện thoại Internet (VoIP phone hay IP phone, iPhone ), điện thoại thông minh
(smart phones), máy tính bảng (iPad), máy nghe nhạc (iPod),… và sự phát triển của
công nghệ mạng không dây đã tạo điều kiện thuận lợi cho việc mở rộng phạm vi
vùng phủ sóng và được gọi là mạng nội bộ không dây phạm vi rộng (Wide Wireless
Local Area Networks - WWLANs) hay mạng nội bộ không dây công cộng (Public
Wireless Local Area Networks – PWLANs). WWLANs thường được quan tâm xây
dựng ở các thành phố lớn, như New York, London, Paris, St. Cloud, …và các
trường đại học, như trường đại học Dartmouth, Học viện kỹ thuật Massachusetts
(Massachusetts Institute of Technology – MIT), đại học Florida, … Tại Việt Nam,
các thành phố du lịch như Hội An, Đà Nẵng, Huế, Hải Phòng, … đã được phủ sóng
Wi-fi miễn phí nhằm đáp ứng nhu cầu truy cập Internet cùng lúc cho hàng ngàn
người dân thành phố và khách du lịch. Riêng thành phố Hồ Chí Minh đã thí điểm
lắp đặt WWLAN trên các tuyến xe buýt nhằm thu hút người dân thành phố sử dụng
loại phương tiện công cộng này [nguồn: http://vnreview.vn]. Bên cạnh đó, một số
trường đại học cũng đã triển khai WWLAN phục vụ cho hàng ngàn cán bộ, giảng
viên và sinh viên như: ĐH Công nghiệp TPHCM, ĐH Quốc gia TPHCM, ĐH Việt
Đức, ĐH Kiểm sát Hà Nội, ĐH Tài chính kế toán Quảng Ngãi, …
Một mạng nội bộ không dây công cộng như vậy thường bao gồm hàng trăm
điểm truy nhập mạng (Access Point – AP) và phục vụ cho hàng ngàn người sử dụng
thiết bị di động tại mỗi thời điểm. Trong hệ thống mạng WWLAN, mỗi AP có vùng
phủ sóng từ vài chục mét (indoor AP) đến vài trăm mét (outdoor AP). Do bán kính
phủ sóng của các AP nhỏ nên mỗi khi nút di động (Mobile Node – MN) di chuyển,
2
nó thường đi qua nhiều vùng phủ sóng của nhiều AP khác nhau. Vì WWLAN phải
phục vụ nhiều thiết bị di động và chúng thường xuyên thay đổi điểm kết nối mạng
như vậy nên trong hệ thống mạng thường phát sinh những vấn đề về Quản lý vị trí
và Cấp phát tài nguyên mạng cho thiết bị di động.
Dự báo sự di chuyển của nút di động trong mạng không dây là xác định điểm
truy nhập mạng nào mà nút di động có thể kết nối trong quá trình nó di chuyển
xung quanh vùng phủ sóng. Theo đó, dự báo di chuyển có thể cung cấp cho hệ
thống mạng tri thức về sự di chuyển kế tiếp của các MN cũng như tri thức về nhu
cầu sử dụng tài nguyên mạng trong tương lai tại mỗi AP. Với những tri thức như
vậy, dự báo di chuyển có thể hỗ trợ giải quyết các vấn đề về quản lý vị trí và cấp
phát tài nguyên mạng.
Trong hơn một thập niên qua, bài toán dự báo sự di chuyển của thiết bị di
động trong mạng không dây thu hút được nhiều sự quan tâm của cộng đồng nghiên
cứu. Cho đến nay, đã có nhiều công trình khảo sát về các phương pháp kỹ thuật
được sử dụng trong dự báo di chuyển. Kết quả khảo sát cho thấy rằng phần lớn cơ
chế dự báo được đề xuất trong những năm gần đây đều dựa trên khai phá dữ liệu
(data mining). Do đặc trưng dữ liệu di chuyển của người dùng di động có nhiều
nhiễu, không đầy đủ và biến đổi liên tục, nên kỹ thuật khai phá mẫu tuần tự
(sequential pattern mining) được cho là thích hợp và thu hút nhiều quan tâm nghiên
cứu. Tuy nhiên, những công trình trước đây còn tồn tại hai vấn đề chính như sau:
Trong các công trình trước đây, thuộc tính thời gian trong dữ liệu di chuyển
hoặc là bị loại bỏ sau khi được sử dụng để tạo các mẫu di chuyển hợp lệ
hoặc là không được sử dụng trong quá trình khai phá mẫu di chuyển phổ
biến. Do đó, các cơ chế dự báo di chuyển này chưa khai thác được giá trị
của thời điểm di chuyển trong quá trình thực hiện dự báo. Trong khi đó,
hành vi di chuyển của con người thường có mối quan hệ mạnh với thời gian
biểu của họ. Nghĩa là, vào một số thời điểm cố định trong ngày, con người
thường xuất hiện ở một số nơi cố định.
Hạn chế thứ hai của những công trình trước đây là sử dụng hành vi di
3
chuyển trong quá khứ của cá nhân người dùng di động để dự báo sự di
chuyển tương lai của họ. Trong những trường hợp người sử dụng mới gia
nhập vào hệ thống mạng hoặc thay đổi hành vi di chuyển, dữ liệu di chuyển
của cá nhân họ sẽ không nhiều. Do đó, các cơ chế này có thể không dự báo
thành công trong những trường hợp như vậy.
Mục tiêu và phạm vi của luận án
Mục tiêu của luận án là nghiên cứu các giải pháp khai thác những tri thức ẩn
chứa trong dữ liệu di chuyển để nâng cao độ chính xác của cơ chế dự báo di chuyển
trong mạng không dây. Luận án tập trung vào hai chủ đề chính sau đây:
Nghiên cứu cách khai thác đồng thời cả hai đặc trưng không gian và thời
gian của dữ liệu di chuyển nhằm nâng cao độ chính xác dự báo. Để đạt
được mục tiêu này, luận án đề xuất một cách biểu diễn mẫu di chuyển theo
hai thuộc tính không gian và thời gian. Cách biểu diễn này sau đó được áp
dụng để đề xuất một cơ chế dự báo di chuyển dựa trên khai phá mẫu không
gian – thời gian.
Nghiên cứu cách khai thác đặc trưng di chuyển theo nhóm của người dùng
di động và đề xuất giải pháp dự báo cho những di chuyển thiếu thông tin.
Để đạt mục tiêu này, trước hết luận án định nghĩa một độ đo tương tự nhằm
xác định mức độ giống nhau về hành vi di chuyển của người dùng di động.
Độ đo tương tự mới này sau đó được áp dụng để phát triển một giải pháp
phân nhóm dữ liệu di chuyển của người dùng di động. Dựa trên giải pháp
phân nhóm, luận án đề xuất một cơ chế dự báo di chuyển nhằm khắc phục
tình trạng thiếu thông tin của dữ liệu di chuyển cá nhân.
Những đóng góp chính của luận án
Luận án đã đề xuất các cơ chế dự báo di chuyển dựa trên sự khai thác các đặc
trưng của dữ liệu di chuyển nhằm nâng cao độ chính xác dự báo, bao gồm:
Mô hình biểu diễn sự di chuyển của thiết bị di động trong mạng không dây
theo thuộc tính không gian và thời gian. Mô hình này đã được công bố trên
Tạp chí Southeast-Asian Journal of Sciences, 2012 và đã được báo cáo tại
4
Hội nghị quốc tế International Conference in Mathematics and
Applications – ICMA, Thailand, 2011.
Cơ chế dự báo di chuyển dựa trên khai phá mẫu tuần tự không gian – thời
gian. Cơ chế dự báo này khai thác giá trị của thuộc tính thời gian trong cả
bốn giai đoạn của quá trình dự báo di chuyển. Kết quả nghiên cứu đã được
công bố trên kỷ yếu của Hội nghị quốc gia lần 5 về nghiên cứu Cơ bản và
Ứng dụng (FAIR’05), 2011, trên Tạp chí Journal of Communication and
Computer (JCC), 2012 và trên Tạp chí International Journal of Computer
Science and Telecommunications (IJCST), 2012.
Độ đo tương tự giữa các mẫu di chuyển nhằm khai thác đặc trưng di chuyển
theo nhóm trong dữ liệu di chuyển. Độ đo tương tự này là một sự kết hợp
có trọng số theo hai thuộc tính không gian và thời gian của mẫu di chuyển.
Luận án đã lập luận chứng minh tính đúng đắn của độ đo tương tự và kiểm
định bằng thực nghiệm. Độ đo này đã được công bố trên Tạp chí
International Journal of Computer Networks & Communications (IJCNC),
2012 (DBLB) và trên Tạp chí Khoa học và Công Nghệ của Viện Khoa học
và Công nghệ Việt Nam, 2013.
Thuật toán gom nhóm hành vi di chuyển của người dùng di động trong
mạng không dây dựa trên độ đo tương tự được đề xuất bởi luận án. Hiệu
quả của thuật toán gom nhóm được đánh giá bằng thực nghiệm trên nhiều
tham số khác nhau và thông qua nhiều phương pháp đo chất lượng gom
nhóm chuẩn. Kết quả nghiên cứu này đã được công bố trên kỷ yếu của Hội
nghị quốc gia lần 6 về nghiên cứu Cơ bản và Ứng dụng (FAIR’06), 2013 và
trên Tạp chí International Journal of Innovative Computing, Information
and Control (IJICIC), 2013, (Scopus| SJR impact factor = 0.812).
Cơ chế dự báo di chuyển dựa trên nhóm hành vi di chuyển tương tự. Cơ chế
này khai thác sự giống nhau về hành vi di chuyển của người dùng di động
nhằm khắc phục sự thiếu thông tin của dữ liệu di chuyển cá nhân. Kết quả
nghiên cứu này đã được công bố trên kỷ yếu của Hội nghị quốc tế
5
International Conference on Context-Aware Systems and Applications –
ICCASA, 2013, Lecture Notes of ICST (Springer) và trên kỷ yếu của Hội
nghị quốc tế Science and Information Conference – SAI, London, 2015
(IEEE Xplore) và trên Tạp chí Journal of Communications and Networks
(JCN), 2015 (ISI, impact factor = 1.007).
Bố cục của luận án
Về cấu trúc, luận án được trình bày trong 3 chương, có phần mở đầu, phần kết
luận, phần các công trình đã công bố liên quan đến luận án, tài liệu tham khảo và
phần phụ lục. Chương 1 trình bày tổng quan về những vấn đề liên quan đến dự báo
di chuyển trong mạng không dây và những cơ sở lý thuyết cho các giải pháp được
đề xuất trong các chương còn lại của luận án. Chương 2 tập trung nghiên cứu và đề
xuất một cách biểu diễn mẫu di chuyển theo hai thuộc tính không gian và thời gian
của dữ liệu di chuyển. Với cách biểu diễn mẫu di chuyển như vậy, chương này đề
xuất một cơ chế dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian.
Phần còn lại của chương là xây dựng dữ liệu kiểm thử, phương pháp đánh giá thực
nghiệm và các kịch bản thực nghiệm, cài đặt thực nghiệm trên các tập dữ liệu mô
phỏng để phân tích và đánh giá hiệu quả của việc sử dụng đồng thời cả hai thuộc
tính không gian và thời gian vào dự báo di chuyển. Hiệu quả của cơ chế dự báo đề
xuất cũng được đánh giá so sánh với các công trình liên quan bằng thực nghiệm.
Trong chương 3, luận án đề xuất một độ đo tương tự cho mẫu di chuyển nhằm xác
định mức độ giống nhau giữa chúng. Độ đo tương tự này sau đó được áp dụng để đề
xuất một giải pháp gom nhóm mẫu di chuyển. Dựa trên giải pháp gom nhóm, luận
án đề xuất một cơ chế dự báo di chuyển với mục tiêu khai thác đặc trưng di chuyển
theo nhóm của người sử dụng thiết bị di động nhằm khắc phục sự thiếu thông tin
của dữ liệu di chuyển cá nhân. Hiệu quả của các giải pháp được đề xuất trong
chương này đều được đánh giá bằng thực nghiệm và so sánh với các công trình liên
quan. Do đó, phần còn lại của chương trình bày về tập dữ liệu kiểm thử, phương
pháp đánh giá thực nghiệm và các kịch bản thực nghiệm, kết quả thực nghiệm.
6
B. NỘI DUNG
Chương 1 – Tổng quan về dự báo di chuyển trong mạng không dây
1.1. Tổng quan về các cơ chế dự báo di chuyển
Loại tri thức và kỹ thuật
Đặc điểm
Hạn chế
được sử dụng
Tôpô giao thông,
tôpô đường đi, …
- Dựa vào tôpô hay bản
đồ khái niệm không gian cảnh mạng hay tôpô thay đổi.
Bản đồ khái niệm để tính xác suất di chuyển
không gian
- Không dự báo tốt khi ngữ
- Yêu cầu tập hợp và xử lý
từ một vị trí đến các vị trí một lượng thông tin cực kỳ lớn.
có thể.
- Thích hợp cho các hệ
thống mạng ổn định và có
qui mô nhỏ
Tri thức
ngữ
Độ mạnh tín hiệu
cảnh
nhận được
- Dựa vào độ mạnh tín
- Làm tăng lưu lượng mạng vì
hiệu để theo dõi (tracking) các AP liên tục gửi tín hiệu
liên tục khoảng cách giữa chứa thông tin về khoảng cách.
MN và những AP lân cận.
- Số vị trí dự báo thường
- Độ mạnh tín hiệu nhận nhiều hơn một vì dự báo không
được càng lớn nghĩa là theo hướng di chuyển.
MN ở càng gần AP, do đó
có khả năng MN đang di
chuyển đến AP.
Hành vi
di
chuyển
trong
quá khứ
Mô hình xác suất
- Sự di chuyển của MN
- Sử dụng tài nguyên tính toán
từ AP này đến AP khác lớn.
được mô hình là một sự
chuyển trạng thái.
- Dựa vào ma trận xác
- Cần huấn luyện lại mô hình
định kỳ.
- Không khai thác được thông
suất chuyển trạng thái để tin di chuyển theo nhóm.
7
dự báo sự chuyển trạng
thái kế tiếp của MN.
Phân tích thống kê
- Phân tích dữ liệu di
- Khó mở rộng thêm đặc điểm
ngữ cảnh.
- Không thích nghi với dữ liệu
chuyển để rút trích tri không đầy đủ hoặc biến đổi
thức về hành vi di chuyển. liên tục.
- Kết quả phân tích thường rất
lớn và trừu tượng.
Phân lớp
Thích hợp cho các hệ Phải huấn luyện lại mô hình khi
thống mạng ổn định và có thêm dữ liệu mới hay loại bỏ
quy mô nhỏ.
dữ liệu cũ.
Gom nhóm Sử dụng đặc điểm di Kết quả dự báo sẽ không tốt
chuyển theo nhóm của nếu dữ liệu di chuyển có tỷ lệ
người dùng di động để di chuyển ngẫu nhiên cao.
tiên đoán di chuyển tương
lai.
Khai
phá
dữ
Khai
phá Thích nghi tốt với dữ liệu
mẫu
tuần di chuyển có tỷ lệ di thời gian trong mẫu di chuyển.
tự
chuyển ngẫu nhiên cao.
- Chưa khai thác thuộc tính
- Không dự báo tốt khi dữ liệu
Đề xuất giải pháp đáp ứng di chuyển cá nhân không đầy
liệu
thời gian thực khi sử dụng đủ.
khai phá mẫu tuần tự.
Khai
phá Sử dụng thuộc tính thời
mẫu
tuần gian trong giai đoạn khai gian ở một giai đoạn của quá
tự
không phá mẫu di chuyển phổ trình dự báo di chuyển.
gian – thời biến.
gian
- Chỉ khai thác thuộc tính thời
- Không dự báo tốt khi dữ liệu
Sử dụng ràng buộc thời di chuyển cá nhân không đầy
gian để sinh tập chuỗi di đủ.
chuyển có nghĩa.
8
1.2. Độ đo tương tự cho dữ liệu di chuyển
1.2.1. Các khái niệm về độ đo tương tự
Cho S là một tập hợp khác rỗng, một hàm số d: S S R được gọi là một
mêtric (metric) trên S nếu d thỏa các tính chất sau:
Tiên đề 1 (tính phản xạ - self-identity): với mọi x thuộc S, d(x, x) = 0.
Tiên đề 2 (tính luôn dương – positivity): với mọi x, y thuộc S, x ≠ y, d(x, y) > 0
Tiên đề 3 (tính đối xứng – symmetry): với mọi x, y thuộc S, d(x, y) = d(y, x)
Tiên đề 4 (tính bất đẳng thức tam giác - triangle inequality): với mọi x, y, z thuộc S,
d(y, z) ≤ d(y, x) + d(x, z)
Độ đo tương tự (similarity measure) của hai đối tượng dữ liệu là độ sai khác
(dissimilarity) của đối tượng dữ liệu này với đối tượng dữ liệu còn lại. Độ sai khác
này được tính dựa trên một hàm số d. Nếu hàm số d chỉ thỏa các tính chất phản xạ,
luôn dương và đối xứng (các tiên đề 1, 2, 3) thì độ đo tương tự là một nửa mêtric
hay bán mêtric (semi-metric). Nếu hàm số d chỉ thỏa các tính chất phản xạ, đối
xứng và bất đẳng thức tam giác (các tiên đề 1, 2, 4) thì độ đo tương tự là một giả
mêtric hay gần mêtric (pseudo-metric). Nếu hàm số d chỉ thỏa các tính chất phản xạ
và đối xứng (các tiên đề 1, 3) thì độ đo tương tự là nửa giả mêtric hay nửa gần
mêtric (semipseudo-metric).
1.2.2. Tổng quan về các độ đo tương tự
Việc xác định mức độ tương tự giữa các mẫu đường đi đóng vai trò quan trọng
trong việc khai thác sự di chuyển giống nhau của các đối tượng di chuyển. Mặc dù
đã có nhiều độ đo được đề xuất để tính độ tương tự giữa các mẫu đường đi nhưng
phần lớn được tính dựa trên khoảng cách Ơ-clit (Euclidean distance). Tuy nhiên,
cũng có một số độ đo được đề xuất cho không gian mạng thay cho không gian Ơclit nhưng chưa quan tâm thuộc tính thời gian của dữ liệu đường đi. Một số ít độ đo
sử dụng khoảng cách mạng (network distance) và tính toán dựa trên đồng thời thuộc
tính không gian và thời gian. Tuy nhiên, yếu tố thời gian được phản ảnh thông qua
khía cạnh thời khoảng giữa hai vị trí liên tiếp tương ứng trong hai mẫu hoặc thứ tự
9
giữa các vị trí tương ứng trong hai mẫu, chưa quan tâm đến thời điểm của hai vị trí
tương ứng trong hai mẫu.
1.3. Mở rộng thuật toán gom nhóm k-means
Với ưu điểm đơn giản và độ phức tạp tính toán thấp, thuật toán gom nhóm kmeans ngày càng trở nên phổ biến. Độ phức tạp của thuật toán k-means là O(n.k.l)
với k là số lượng nhóm được sinh ra, n là số phần tử của tập dữ liệu cần phân hoạch
và l là số lần lặp của vòng lặp while trong thuật toán. Với độ phức tạp tính toán đa
thức, thuật toán k-means thường được đề xuất sử dụng cho các tập dữ liệu lớn.
Tuy nhiên, thuật toán k-means kinh điển tập trung vào dữ liệu định lượng
(numerical data, còn gọi là dữ liệu số) và do đó sử dụng khoảng cách Ơ-clit để đo
độ tương tự giữa các đối tượng dữ liệu. Nhiều công trình nghiên cứu đã chứng minh
sự không hiệu quả khi sử dụng khoảng cách Ơ-clit để đo độ tương tự giữa các đối
tượng dữ liệu định tính (categorical data, còn gọi là dữ liệu phân loại). Hơn nữa,
thuật toán k-means kinh điển được đề xuất cho miền giá trị định lượng nên rất khó
áp dụng trực tiếp cho miền giá trị định tính như trong hầu hết các ứng dụng khai phá
dữ liệu.
Để khắc phục hạn chế này, nhiều nhóm nghiên cứu đã đề xuất các giải pháp để
áp dụng k-means cho miền giá trị định tính. Trong đó, một số công trình đề xuất
chuyển miền giá trị định tính sang miền giá trị định lượng. Cách tiếp cận này khá
đơn giản tuy nhiên sẽ có thể dẫn đến mất ngữ nghĩa trong các khái niệm định tính.
Một cách tiếp cận khác là xây dựng các độ đo tương tự cho dữ liệu định tính và sử
dụng độ đo tương tự để phân nhóm đối tượng dữ liệu, điển hình là k-modes và krepresentatives. Tuy nhiên, những giải pháp gom nhóm này có thể tạo ra các phân
hoạch không ổn định do mỗi nhóm có nhiều hơn một trung vị như k-modes hoặc do
khởi tạo đại diện nhóm ngẫu nhiên như k-representatives.
1.4. Tập dữ liệu kiểm thử
Mặc dù các hệ thống mạng WWLAN phổ biến nhưng phần lớn chúng đều
được phát triển dần dần theo sự phát triển của thành phố / trường đại học. Do đó, sơ
10
đồ bố trí tổng thể các điểm truy nhập mạng APs của một hệ thống mạng WWLAN
thường thay đổi theo thời gian. Hơn nữa, vì lý do bảo mật hệ thống mạng nên các
nhà quản trị hệ thống phải có trách nhiệm bảo mật sơ đồ bố trí tổng thể các điểm
truy nhập mạng. Vì không thể tiếp cận được sơ đồ bố trí tổng thể các điểm truy
nhập mạng của một hệ thống mạng trong thực tế nên phần lớn các nhóm nghiên cứu
đều tự xây dựng tập dữ liệu kiểm thử từ các hệ thống mạng mô phỏng.
Mặt khác, nhằm khảo sát mức độ ảnh hưởng của tỷ lệ di chuyển ngẫu nhiên
trong dữ liệu di chuyển đối với độ chính xác dự báo của cơ chế đề xuất, luận án cần
xây dựng các tập dữ liệu kiểm thử theo các tỷ số ngẫu nhiên khác nhau. Tỷ số ngẫu
nhiên là tỷ lệ số đường đi ngẫu nhiên trên tổng số đường đi trong tập. Với tập dữ
liệu thực (real dataset), số đường đi ngẫu nhiên trong tập là cố định và khó nhận
diện nên việc điều chỉnh tỷ số ngẫu nhiên cho tập dữ liệu kiểm thử thực là khó thực
hiện được.
Từ những lý do trên, luận án thực hiện đánh giá các đề xuất bằng thực nghiệm
trên các tập dữ liệu kiểm thử mô phỏng. Tập dữ liệu kiểm thử là tập những đường đi
của thiết bị di động xung quanh vùng phủ sóng của một hệ thống mạng. Do đó, để
xây dựng tập dữ liệu kiểm thử, trước hết luận án mô phỏng một hệ thống mạng có
vùng phủ sóng (coverage region) bao gồm một số lượng điểm truy nhập mạng
(APs) cụ thể và sơ đồ bố trí các điểm truy nhập cụ thể. Hệ thống mạng này được
biểu diễn bởi một đồ thị di chuyển có số nút và cấu trúc mạng lưới các nút tương
ứng với số điểm truy cập mạng và sơ đồ bố trí các điểm truy cập mạng trong hệ
thống. Dựa trên đồ thị di chuyển, luận án xây dựng một bộ sinh dữ liệu để sinh ra
tập đường đi mô tả sự đi qua các nút trên đồ thị nhằm mô phỏng sự di chuyển xung
quanh vùng phủ sóng của hệ thống mạng mô phỏng. Cách xây dựng tập dữ liệu
kiểm thử này cũng đã được nhiều công trình nghiên cứu trước đây thực hiện.
1.5. Phương pháp đánh giá thực nghiệm
Để đảm bảo tính chính xác, ngẫu nhiên và khách quan, luận án tính toán các
tiêu chí đánh giá thông qua phương pháp kiểm thử chéo (n-folds cross-validation)
11
trên các tập dữ liệu kiểm thử được sinh ra. Theo phương pháp này, tập dữ liệu kiểm
thử được phân chia ngẫu nhiên thành n tập dữ liệu con có số lượng phần tử bằng
nhau. Lần lượt từng tập dữ liệu con trong n tập dữ liệu con được chọn làm tập kiểm
tra và (n-1) tập dữ liệu con còn lại được sử dụng làm tập huấn luyện. Tiến trình
đánh giá chéo được thực hiện lặp lại n lần tương ứng với n bộ tập huấn luyện/tập
kiểm tra. Kết quả thực nghiệm trên mỗi lần huấn luyện/kiểm tra được ghi lại và sau
đó tính kết quả trung bình. Giá trị trung bình của n kết quả được sử dụng để đánh
giá tổng thể kết quả thực nghiệm.
Luận án sử dụng các độ đo đánh giá chuẩn để thực nghiệm trên nhiều tham số
khác nhau và từ đó đánh giá hiệu quả của các cơ chế dự báo di chuyển và gom
nhóm hành vi di chuyển. Cụ thể về các độ đo đánh giá được trình bày trong phần
tiếp theo.
Độ đo đánh giá độ chính xác dự báo
Tương tự các công trình nghiên cứu trước đây, luận án đánh giá độ chính xác
dự báo dựa trên hai độ đo chuẩn sau:
Độ đo đầy đủ (Recall): Số lần dự báo đúng chia cho tổng số lần yêu cầu dự
báo. Như vậy, độ đo đầy đủ xem trường hợp “không dự báo được (noprediction)” như một lần dự báo sai.
Độ đo chính xác (Precision): Số lần dự báo đúng chia cho tổng số lần dự
báo được thực hiện thành công. Nghĩa là độ đo chính xác bỏ qua trường
hợp “không dự báo được”.
Vì độ đo chính xác (precision measure) không xét trường hợp “không dự báo
được” nên độ đo này thích hợp cho việc đánh giá độ chính xác dự báo trong trường
hợp dữ liệu di chuyển không đầy đủ. Ngược lại, khi dữ liệu di chuyển hoàn thiện thì
“không dự báo được” phải được xem là một lần dự báo sai, vì lúc này cơ chế dự báo
đã không tìm được vị trí kết nối kế tiếp. Do đó, độ đo đầy đủ nên được sử dụng
trong trường hợp này. Độ đo đầy đủ có giá trị càng lớn thì độ chính xác dự báo của
cơ chế càng lớn.
12
Độ đo đánh giá chất lượng gom nhóm
Kết quả gom nhóm được xem là tốt nếu khoảng cách giữa các đối tượng dữ
liệu trong cùng nhóm là thấp, trong khi đó khoảng cách giữa các đối tượng dữ liệu
trong các nhóm khác nhau là cao. Cho đến nay, có ba phương pháp thường được sử
dụng để đánh giá chất lượng của kết quả gom nhóm:
Đánh giá dựa vào các độ đo Entropy (Entropy measures): Chất lượng gom
nhóm được đánh giá bởi độ đo nội (internal measure) và độ đo ngoại
(external measure). Độ đo nội phản ánh khoảng cách trung bình giữa các đối
tượng dữ liệu trong cùng nhóm. Ngược lại, độ đo ngoại phản ánh khoảng
cách trung bình giữa các nhóm với nhau.
Đánh giá dựa vào sự khác biệt thông tin (Variation of Information – VI): Ký
hiệu C* = C1* C2* …Ck* là phân hoạch đúng của tập dữ liệu kiểm thử
và C = C1 C2 …Ck là phân hoạch được sinh ra bởi thuật toán gom
nhóm đề xuất. Giá trị của VI(C, C*) xác định sự khác nhau giữa hai phân
hoạch C và C*. Giá trị của VI(C, C*) càng nhỏ thì phân hoạch C càng giống
phân hoạch đúng C* nên chất lượng gom nhóm càng tốt. Giá trị của VI(C, C*)
bằng 0 khi phân hoạch C giống hoàn toàn phân hoạch đúng C*.
Đánh giá dựa vào mức độ tương ứng của các phân hoạch (r): đo mức độ
tương ứng giữa các nhóm được sinh ra bởi thuật toán gom nhóm cần đánh
giá và các lớp đã được gán trước trong tập dữ liệu kiểm thử.
Chương 2 – Dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian
2.1. Biểu diễn di chuyển trong mạng không dây
2.1.1. Biểu diễn vùng phủ sóng
Tương tự như các công trình trước đây, luận án biểu diễn vùng phủ sóng của
một hệ thống mạng không dây tế bào dưới dạng một mạng hình lục giác như trong
Hình 2.1. Mỗi lục giác là một tế bào được phục vụ bởi một AP. Để mô hình sự di
chuyển của MNs xung quanh vùng phủ sóng, luận án sử dụng một đồ thị có hướng
không trọng số (unweighted directed graph) G = (V, E). Trong đó, tập đỉnh V là tập
13
định danh của tất cả tế bào trong vùng phủ sóng và tập cạnh E biểu diễn sự lân cận
của hai tế bào tương ứng.
Hình 2.1. Vùng phủ sóng (a) và đồ thị di chuyển tương ứng (b)
2.1.2. Định nghĩa mẫu di chuyển và luật di chuyển
Vì mục tiêu của luận án là phân tích hành vi di chuyển hàng ngày của người
dùng di động nên luận án đề xuất chia chu kỳ thời gian một ngày (24 giờ) ra thành n
khoảng thời gian [ai, bi] bằng nhau, mỗi thời khoảng [ai, bi] được gán một nhãn thời
gian ti duy nhất. Khi đó, mỗi ngày đều có cùng một tập nhãn thời gian T = { t1, t2, …
ti, … tn} với tính chất ti < tj khi và chỉ khi i < j, 1 ≤ i, j ≤ n.
Ký hiệu c là định danh của tế bào trong vùng phủ sóng mà MN kết nối vào tại
thời điểm t, luận án định nghĩa một điểm (point) như sau:
Định nghĩa 2.1. Ký hiệu C và T tuần tự là tập định danh của tế bào và tập nhãn
thời gian. Cặp có thứ tự p = (c, t), trong đó c C và t T, được gọi là một điểm.
Ký hiệu P là tập tất cả điểm, P = C × T = {(c, t) | c C và t T}.
Hai điểm pi = (ci, ti) và pj = (cj, tj) được gọi là bằng nhau nếu và chỉ nếu ci = cj
và ti = tj. Điểm pi = (ci, ti) được gọi là điểm trước của điểm pj = (cj, tj) nếu và chỉ nếu
ti < tj, và ký hiệu là (ci, ti) < (cj, tj) hoặc pi < pj.
Ví dụ: điểm (8, t5) là điểm trước của điểm (2, t7) vì t5 < t7
Định nghĩa 2.2. Một đường đi (trajectory) của thiết bị di động được định nghĩa là
một chuỗi có thứ tự hữu hạn các điểm
trong không gian C × T, với
pj = (cj, tj) sao cho 1 ≤ j ≤ k và hai tế bào của hai điểm liền kề là lân cận nhau
trong vùng phủ sóng. Một đường đi gồm k điểm được gọi là một mẫu di chuyển tuần
tự (sequential mobility pattern) chiều dài k và được ký hiệu là k-pattern.
14
Chú ý rằng thứ tự tăng dần của các điểm trong đường đi được sắp xếp theo
nhãn thời gian ti của các điểm.
Định nghĩa 2.3. Một mẫu di chuyển tuần tự B = được gọi là một
mẫu di chuyển con (sub-pattern) của một mẫu di chuyển tuần tự A = , với ai và bj là những điểm, ký hiệu B A, nếu và chỉ nếu tồn tại những số
nguyên 1 ≤ i1 < … < im ≤ n sao cho bk = aik, cho tất cả k, với 1 ≤ k ≤ m. Và khi đó,
A được gọi là mẫu di chuyển cha (super-pattern) của B.
Định nghĩa 2.4. Cho một cơ sở dữ liệu giao tác D = {S1, S2, …, SN} chứa N mẫu di
chuyển. Độ phổ biến (support) của mẫu di chuyển S là tỷ lệ phần trăm giữa số giao
tác chứa S và tổng số giao tác trong cơ sở dữ liệu giao tác D, nghĩa là:
support( S )
Si | S Si , Si D
N
100
(2.1)
Định nghĩa 2.5. Cho một ngưỡng hỗ trợ tối thiểu (minimum support threshold),
suppmin, một mẫu di chuyển tuần tự S được định nghĩa là một mẫu di chuyển phổ
biến nếu và chỉ nếu S có độ phổ biến thỏa mãn:
support(S) ≥ suppmin
(2.2)
Định nghĩa 2.6. Một luật di chuyển có dạng R: A B, trong đó, A và B là hai mẫu
di chuyển phổ biến và A B =. Khi đó, A và B lần lượt được gọi là phần đầu và
phần đuôi của luật.
Vì luật di chuyển R: A B được sinh từ mẫu di chuyển phổ biến A B, độ
phổ biến của luật di chuyển là độ phổ biến của mẫu di chuyển A B.
Định nghĩa 2.7. Cho một cơ sở dữ liệu giao tác D = {S1, S2, …, SN} chứa N mẫu di
chuyển. Độ phổ biến của luật kết hợp R: A B là tỷ lệ phần trăm giữa số giao tác
chứa A B và tổng số giao tác trong cơ sở dữ liệu giao tác D, nghĩa là:
(2.3)
support( A B )
Si | A B Si , Si D
N
100 support( A B )
Định nghĩa 2.8. Cho một luật di chuyển R: A B, độ tin cậy của luật (confidence
value) được định nghĩa bởi công thức:
15
confidence ( R)
support(A B)
100
support( A)
(2.4)
2.2. Dự báo di chuyển dựa trên khai phá mẫu không gian – thời gian
2.2.1. Sinh cơ sở dữ liệu giao tác
Để có thể khai phá mẫu di chuyển phổ biến từ dữ liệu di chuyển, trước hết
luận án rút trích tất cả mẫu di chuyển có nghĩa từ tập tin nhật ký di chuyển (log file)
của cá nhân MN. Mẫu di chuyển có nghĩa là một chuỗi vị trí mà MN lần lượt kết
nối vào trong một phiên di chuyển, được gọi là một giao tác hợp lệ (valid
transaction). Tập tất cả giao tác hợp lệ theo thứ tự thời gian được gọi là cơ sở dữ
liệu giao tác (transactional database). Để khắc phục vấn đề mất kết nối hay thiếu dữ
liệu trong lịch sử di chuyển, luận án đề xuất sử dụng ràng buộc thời gian giữa các vị
trí kết nối của MN nhằm tạo ra các chuỗi di chuyển có nghĩa. Ràng buộc thời gian
giới hạn khoảng thời gian giữa hai vị trí trong một giao tác. Nghĩa là, khi khoảng
thời gian giữa hai vị trí kết nối liên tục của MN trong dữ liệu di chuyển của nó vượt
quá ngưỡng thời gian tối đa, ký hiệu là gapmax, thì một giao tác hợp lệ sẽ được sinh
ra. Ký hiệu tj và tj+1 lần lượt là thời điểm MN kết nối vào 2 vị trí liên tục thì tj+1 - tj ≤
gapmax.
2.2.2. Khai phá mẫu di chuyển không gian-thời gian
Luận án đã khảo sát, đánh giá ưu và nhược điểm của một số thuật toán khai
phá tập/mẫu tuần tự phổ biến điển hình như Apriori và các biến thể của nó, GSP,
SPADE, FP-Growth và PrefixSpan. Nhóm thuật toán dựa trên nguyên lý Apriori
duyệt lại CSDL nhiều lần nên thích hợp cho những hệ thống khai phá tương tác
(thường xuyên thay đổi độ phổ biến) hoặc khai phá CSDL tăng dần (thường xuyên
thêm các giao tác mới). Đồng thời, nhóm thuật toán này cũng được khuyến nghị chỉ
nên áp dụng khi các mẫu tuần tự trong CSDL có độ dài ngắn và CSDL có kích
thước nhỏ. Trong khi đó, nhóm thuật toán dựa trên phương pháp phát triển mẫu
thích hợp cho các CSDL lớn và chuỗi dữ liệu dài. Tuy nhiên, vì chi phí cho việc xây
dựng lại không gian tìm kiếm rất cao nên nhóm giải thuật này sẽ không hiệu quả khi
áp dụng cho những hệ thống khai phá tương tác hoặc khai phá CSDL tăng dần.
16
Luận án phân tích hành vi di chuyển hàng ngày của con người nên mỗi phiên
di chuyển của con người được thực hiện trong một ngày. Do đó, các mẫu di chuyển
tuần tự trong CSDL giao tác của luận án có độ dài thường là ngắn. Vì CSDL giao
tác trong luận án được xây dựng từ lịch sử di chuyển hàng ngày của tất cả người sử
dụng gia nhập vào hệ thống mạng nên CSDL thường xuyên được thêm các giao tác
mới.
Từ những phân tích trên, nhóm thuật toán dựa trên nguyên lý Apriori tỏ ra
thích hợp để khai phá tất cả mẫu di chuyển phổ biến không gian-thời gian từ CSDL
giao tác D trong luận án. Tuy nhiên, để có kết quả đánh giá thực nghiệm về hiệu
quả sử dụng của các nhóm thuật toán khai phá mẫu tuần tự phổ biến, luận án đề
xuất cài đặt cả hai nhóm thuật toán (1) dựa trên nguyên lý Apriori và (2) dựa trên
phương pháp phát triển mẫu. Cả hai thuật toán này đều được mở rộng trên cả hai
thuộc tính không gian và thời gian nhằm khai phá tất cả mẫu di chuyển phổ biến
không gian-thời gian từ cơ sở dữ liệu giao tác D.
2.2.3. Rút trích luật di chuyển theo trọng số thời gian
Giả sử S là một mẫu di chuyển phổ biến, tất cả luật di chuyển có thể được sinh
ra từ mẫu di chuyển phổ biến S là: A (S-A) với tất cả A S và A ≠ .
Mỗi luật di chuyển có một độ tin cậy (confidence) được tính theo Định nghĩa
2.7. Tất cả luật di chuyển có độ tin cậy lớn hơn ngưỡng tin cậy tối thiểu confmin sẽ
được chọn và được gọi là luật di chuyển phổ biến (frequent mobility rules). Luận án
đề xuất mỗi luật ri được gán một giá trị trọng số wi dựa trên thuộc tính thời gian.
Trọng số của mỗi luật được tính theo thủ tục sau. Ký hiệu MinDate và MaxDate lần
lượt là ngày đầu tiên (first date) và ngày cuối cùng (last date) trong tập tin nhật ký
di chuyển của MN. Ký hiệu RuleDate là ngày được xác định thông qua giá trị thuộc
tính thời gian của điểm cuối cùng trong phần đuôi của luật. Luận án đề xuất cách
tính giá trị trọng số của luật như Công thức (2.5).
weight ( R)
RuleDate MinDate
100
MaxDate MinDate
(2.5)
17
2.2.4. Dự báo di chuyển dựa trên luật di chuyển
Luật di chuyển phổ biến được rút trích từ dữ liệu di chuyển của người dùng di
động, mô tả hành vi di chuyển thường ngày của họ. Do đó, luật di chuyển phổ biến
có thể được sử dụng để tiên đoán sự di chuyển tương lai của người dùng di động.
Như phân tích ở trên, những luật di chuyển được rút trích từ tập dữ liệu di chuyển
trong quá khứ xa sẽ kém quan trọng hơn những luật di chuyển mới được rút trích từ
tập mẫu di chuyển hiện tại. Do đó, những luật di chuyển có thời gian tồn tại càng
lâu thì càng ít phản ánh hành vi di chuyển hiện tại của người dùng di động. Theo đó,
những luật di chuyển có thời gian tồn tại quá lâu thì cho dù chúng có độ phổ biến và
độ tin cậy cao nhưng cũng không được ưu tiên chọn để dự báo vì có khả năng hành
vi di chuyển hiện tại của con người đã thay đổi so với trước đây. Để giải quyết vấn
đề này, luận án đề xuất tính điểm so khớp luật di chuyển với đường đi hiện tại cần
dự báo dựa trên độ phổ biến, độ tin cậy và trọng số thời gian của luật.
Chương 3 – Dự báo dựa trên nhóm hành vi di chuyển
3.1. Độ đo tương tự cho mẫu di chuyển
Luận án đề xuất độ đo tương tự STPS (Spatial and Temporal Pattern
Similarity) dựa trên hai nhân tố sau đây:
Số tế bào chung của hai mẫu di chuyển: hai mẫu di chuyển có càng nhiều tế
bào chung thì chúng càng giống nhau về không gian.
Thời điểm kết nối vào các tế bào chung của hai mẫu di chuyển: Hai mẫu di
chuyển có thời điểm kết nối vào cùng tế bào càng gần nhau thì chúng càng
giống nhau về thời gian.
Định nghĩa 3.1. Cho P là một tập mẫu di chuyển, một hàm số f: P P [0,1], ánh
xạ từ một cặp mẫu di chuyển sang một số thực trong đoạn 0 và 1, được gọi là một
độ đo tương tự trên P nếu f thỏa các tính chất sau:
(i) Tính phản xạ: với mọi Pi P f(Pi, Pi) = 0;
(ii) Tính đối xứng: với mọi Pi,Pj P f(Pi, Pj) = f(Pj, Pi);
Dựa vào các khái niệm về độ đo tương tự được trình bày trong Phần 1.2.1, độ đo
tương tự này là một nửa mêtric hay bán mêtric (semi-metric)
18
Độ đo tương tự theo không gian
Định nghĩa 3.2. Ký hiệu g: P P R là một hàm số xác định số tế bào có trong
mẫu Pa nhưng không có trong mẫu Pb. Theo đó, g được biểu diễn bởi công thức sau
g ( Pa , Pb ) card ({cai | cai Pa , cai Pb })
(3.1)
Mệnh đề 3.1.
(i) 0 g(Pa, Pb) L(Pa), với L(Pa) là chiều dài của mẫu di chuyển Pa;
(ii) g(Pa, Pa) = 0, với mọi Pa P;
(iii) g(Pa, Pb) = L(Pa), nếu Pa và Pb không có chung bất kỳ một tế bào nào.
Định nghĩa 3.3. dspace(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được định nghĩa như
sau:
d space( Pa , Pb )
g ( Pa , Pb ) g ( Pb , Pa )
L( Pa ) L( Pb )
(3.2)
Mệnh đề 3.2. dspace(Pb, Pb) là một độ đo tương tự và được gọi là độ tương tự theo
không gian.
Độ đo tương tự theo thời gian
Định nghĩa 3.4. Giả sử Pa = <(ca1, ta1), …, (can, tan)> và Pb = <(cb1, tb1), …, (cbm,
tbm)> là hai mẫu di chuyển, với cai, cbj V và tai, tbj T với mọi i, j. Nếu hai mẫu Pa
và Pb có tế bào chung thì dtime(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được tính
bởi công thức sau:
d time ( Pa , Pb )
tai tbj
1 n ,m
với cai = cbj
k i 1, j 1 max( tai , tbj )
(3.3)
với k là số tế bào chung của Pa và Pb.
Mệnh đề 3.3. dtime(Pb, Pb) là một độ đo tương tự và được gọi là độ đo tương tự theo
thời gian.
Độ đo tương tự kết hợp không gian và thời gian
Định nghĩa 3.5. Một hàm u: [0,1] [0,1] [0,1] được gọi là một hàm kết hợp, ký
hiệu là com-function, nếu và chỉ nếu nó thỏa mãn những điều kiện sau:
(1) min(s, h) u(s, h) max(s, h);
(2) u(s1, h) u(s2, h) nếu s1 s2;
19
(3) u(s, h1) u(s, h2) nếu h1 h2.
Mệnh đề 3.4. Hàm u: [0,1] [0,1] [0,1] được định nghĩa bởi công thức:
u(x, y) = wspacex + wtimey với wspace + wtime = 1
(3.4)
là một hàm kết hợp.
Định nghĩa 3.6. d(Pa, Pb) giữa hai mẫu di chuyển Pa và Pb được định nghĩa bởi
công thức sau:
d(Pa, Pb) = wspace dspace(Pa, Pb) + wtime dtime(Pa, Pb) với wspace + wtime = 1
(3.5)
trong đó, dspace(Pa, Pb) và dtime(Pa, Pb) lần lượt là độ đo tương tự theo không gian và
theo thời gian giữa hai mẫu di chuyển Pa và Pb.
Mệnh đề 3.5. d(Pa, Pb) là một độ đo tương tự, là một hàm kết hợp và được gọi là độ
đo tương tự kết hợp.
3.2. Gom nhóm hành vi di chuyển của thiết bị di động
3.2.1. Thuật toán gom nhóm mẫu di chuyển không gian – thời gian
Mục đích của thuật toán gom nhóm là phân hoạch tập mẫu di chuyển thành k
nhóm sao cho những mẫu di chuyển trong cùng nhóm giống nhau hơn so với những
mẫu ở nhóm khác. Thuật toán gom nhóm mẫu di chuyển SMPC (Similarity
Mobility Pattern based Clustering) được đề xuất trong luận án là một sự mở rộng
của phương pháp k-means cho dữ liệu định tính (categorical data). Sự mở rộng tập
trung vào cải tiến thủ tục khởi tạo nhằm hạn chế tối ưu cục bộ và xây dựng thủ tục
cập nhật trung tâm nhóm nhằm tăng độ phân biệt giữa các nhóm thông qua việc gán
mẫu vào nhóm gần nhất.
Trong thuật toán gom nhóm SMPC, k trung tâm nhóm ban đầu được chọn bởi
thủ tục khởi tạo được trình bày trong Phần 3.2.2 thay cho việc khởi tạo một cách
ngẫu nhiên như k-means truyền thống. Sau khi chọn giá trị khởi tạo cho k trung tâm
nhóm, mỗi mẫu di chuyển trong tập dữ liệu được gán vào một nhóm gần nó nhất
theo nghĩa nó giống trung tâm của nhóm đó nhất trong k trung tâm nhóm như được
trình bày trong thủ tục ở Phần 3.2.3. Sau khi tất cả mẫu di chuyển trong tập dữ liệu
đều được gán vào nhóm tương ứng, trung tâm của mỗi nhóm sẽ phải được cập nhật
20
lại theo thủ tục được trình bày trong Phần 3.2.3. Dựa vào giá trị cập nhật của các
trung tâm nhóm, mỗi mẫu di chuyển trong tập dữ liệu cần được gán lại vào nhóm
gần nhất. Thủ tục cập nhật trung tâm nhóm và gán lại mẫu vào nhóm gần nhất sẽ
được lặp lại cho đến khi không còn mẫu di chuyển nào được gán lại nhóm sau một
chu kỳ kiểm tra toàn bộ tập dữ liệu.
3.2.2. Khởi tạo thuật toán gom nhóm mẫu di chuyển dựa trên độ đo tương tự
Ký hiệu P = { P1, P2, …, Pn} là tập mẫu di chuyển và k là một số nguyên
dương đặc tả số nhóm cần phân hoạch. Ký hiệu ci là trung tâm nhóm khởi tạo thứ i,
với 1 i k và C = {c1, c2, …, cl} là tập l trung tâm nhóm khởi tạo hiện tại, với 1
l k.
Định nghĩa 3.7. Trung tâm nhóm khởi tạo kế tiếp là một mẫu di chuyển Pi được
chọn từ tập dữ liệu sao cho giá trị của tổng sau đạt cực đại:
l
Di d ( Pi , c j )
(3.6)
j 1
trong đó d(Pi, cj) là độ đo tương tự kết hợp giữa mẫu di chuyển Pi và trung tâm
nhóm khởi tạo cj như trong Định nghĩa 3.6.
Thủ tục khởi tạo được phác họa như sau:
1. Trung tâm nhóm khởi tạo thứ nhất c1 được chọn một cách ngẫu nhiên từ tập
dữ liệu;
2. Với mỗi mẫu Pi trong tập dữ liệu, Pi c1, 1 i n, tính độ tương tự d(Pi,
c1) giữa mẫu Pi và trung tâm nhóm khởi tạo c1;
3. Trung tâm nhóm khởi tạo thứ hai c2 là một mẫu di chuyển Pi được chọn từ
tập dữ liệu sao cho d(Pi, c1) đạt giá trị lớn nhất.
4. Ký hiệu l là số trung tâm nhóm khởi tạo hiện tại. Với mỗi mẫu Pi trong tập
dữ liệu, Pi C, tính tổng độ tương tự Di giữa Pi và l trung tâm nhóm khởi
tạo hiện tại trong C theo công thức trong Định nghĩa 3.7. Trung tâm nhóm
khởi tạo kế tiếp cl+1 là mẫu Pi sao cho Di đạt giá trị lớn nhất.
5. Nếu l < k thì gán C = C cl+1, l = l+1 và lặp lại bước 4. Ngược lại thì dừng.