Luận văn thạc sĩ khoa học máy tính bloom filters cho bài toán về quản lý black list và white list thẻ từ trong giao thông công cộng

Chuyên đề nghiên cứu Ứng dụng Bloom Filters trong quản lý danh sách đen và danh sách trắng thẻ từ giao, cập nhật xu hướng mới, giá trị tham khảo cao

• Tác giả: Nguyễn Hoàng Phúc
• Người hướng dẫn: PGS.TS Thoại Nam
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bloom Filters Cho Bài Toán Về Quản Lý Black List Và White List Thẻ Từ Trong Giao Thông Công Cộng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2024
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu về Bloom Filters

Trong bối cảnh phát triển công nghệ hiện đại, Bloom Filters đã trở thành một công cụ hữu ích trong việc quản lý và xác thực thông tin. Được giới thiệu lần đầu bởi Burton Howard Bloom vào năm 1970, cấu trúc dữ liệu này cho phép kiểm tra xem một phần tử có thuộc về một tập hợp hay không với hiệu suất cao và yêu cầu không gian lưu trữ tối thiểu. Bloom Filters hoạt động dựa trên nguyên lý ánh xạ các phần tử vào một chuỗi bit, từ đó xác định tính thành viên của một phần tử thông qua các hàm băm. Đặc điểm nổi bật của Bloom Filters là khả năng phát sinh kết quả dương tính giả (False Positive) nhưng không có âm tính giả (False Negative). Điều này có nghĩa là nếu Bloom Filter xác nhận một phần tử không thuộc tập hợp, thì chắc chắn rằng nó không có trong tập hợp, trong khi nếu nó xác nhận một phần tử thuộc về tập hợp, có thể đó chỉ là một kết quả dương tính giả.

II. Quản lý danh sách đen và danh sách trắng trong giao thông công cộng

Trong hệ thống giao thông công cộng, việc quản lý danh sách đen và danh sách trắng là rất quan trọng để đảm bảo an toàn và hiệu quả. Danh sách trắng chứa các thẻ từ hợp lệ, trong khi danh sách đen bao gồm các thẻ từ không hợp lệ hoặc đã bị từ chối. Sử dụng Bloom Filters cho phép các thiết bị xác thực kiểm tra nhanh chóng tính hợp lệ của thẻ từ mà không cần phải truy cập vào cơ sở dữ liệu lớn. Điều này không chỉ giúp giảm thiểu thời gian xác thực mà còn tiết kiệm băng thông mạng. Khi số lượng người dùng gia tăng, việc sử dụng Bloom Filters giúp hệ thống duy trì hiệu suất cao, đặc biệt trong các giờ cao điểm khi lưu lượng truy cập tăng cao.

III. Thuật toán Bloom và các biến thể

Thuật toán Bloom có thể được mở rộng thành nhiều biến thể khác nhau như Counting Bloom Filter và Scalable Bloom Filter. Counting Bloom Filter cho phép xóa các phần tử khỏi tập hợp, điều này rất hữu ích trong các ứng dụng mà dữ liệu có thể thay đổi thường xuyên. Scalable Bloom Filter cung cấp khả năng mở rộng, cho phép thêm các phần tử mới mà không cần phải khởi tạo lại bộ lọc. Các biến thể này giúp tăng tính linh hoạt và khả năng ứng dụng của Bloom Filters trong quản lý danh sách đen và danh sách trắng trong giao thông công cộng, nơi mà dữ liệu liên tục thay đổi.

IV. Phân tích hiệu suất và ứng dụng thực tiễn

Việc áp dụng Bloom Filters trong quản lý thẻ từ giao thông công cộng không chỉ cải thiện hiệu suất mà còn đảm bảo tính bảo mật. Hệ thống có thể xử lý hàng triệu yêu cầu xác thực mà không làm giảm tốc độ dịch vụ. Theo nghiên cứu, việc sử dụng Bloom Filters giúp giảm thời gian xác thực xuống còn vài mili giây, cho phép người dùng trải nghiệm dịch vụ mượt mà hơn. Thêm vào đó, việc giảm thiểu băng thông sử dụng cũng giúp tiết kiệm chi phí cho các nhà cung cấp dịch vụ giao thông công cộng. Mô hình này không chỉ có giá trị lý thuyết mà còn mang lại lợi ích thực tiễn rõ rệt cho ngành giao thông, góp phần vào việc hiện đại hóa hệ thống giao thông công cộng tại Việt Nam.

V. Kết luận và hướng phát triển

Tổng kết lại, việc ứng dụng Bloom Filters trong quản lý danh sách đen và danh sách trắng thẻ từ giao thông công cộng là một giải pháp hiệu quả cho các thách thức hiện tại trong lĩnh vực này. Hướng phát triển tiếp theo có thể tập trung vào việc tối ưu hóa thuật toán để nâng cao độ chính xác và giảm thiểu tỷ lệ dương tính giả, cũng như tích hợp các công nghệ mới như trí tuệ nhân tạo để cải thiện khả năng phân tích và dự đoán. Sự phát triển này không chỉ nâng cao trải nghiệm người dùng mà còn thúc đẩy sự phát triển bền vững của hệ thống giao thông công cộng tại Việt Nam.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh chuyển đổi số quốc gia và chiến lược phát triển đô thị thông minh, việc hiện đại hóa mạng lưới giao thông công cộng là một mục tiêu chiến lược tại Việt Nam. Theo thống kê của Bộ Giao thông Vận tải, hiện có 60/63 tỉnh thành trên cả nước đã đưa hệ thống xe buýt vào khai thác với gần 10.000 phương tiện vận hành bởi 280 doanh nghiệp và hợp tác xã. Riêng tại Thủ đô Hà Nội với quy mô dân số đạt 8,4 triệu người, tỷ lệ người dân lựa chọn giao thông công cộng đã chạm mức 21,5% đến 23%, tương đương khoảng 2 triệu lượt đi lại mỗi ngày. Việc khai trương thí điểm hệ thống vé điện tử liên thông đa phương thức trên hơn 25 tuyến buýt đã mở ra bước ngoặt lớn nhằm thay thế hoàn toàn vé giấy truyền thống.

Tuy nhiên, sự gia tăng nhanh chóng của lượng người tham gia giao thông đã tạo ra thách thức lớn về mặt hạ tầng công nghệ thông tin. Bài toán đặt ra là làm thế nào để quản lý hàng triệu bản ghi trong danh sách hợp lệ (whitelist) và danh sách thẻ bị khóa (blacklist) giữa các nhà xe khác nhau mà vẫn đảm bảo tốc độ xác thực tức thì tại các điểm bán vé hoặc thiết bị di động. Các thiết bị điểm bán hàng (POS) gắn trên xe buýt thường xuyên di chuyển, phụ thuộc vào kết nối mạng không dây và phải đối mặt với áp lực xử lý lượng khách lớn trong các khung giờ cao điểm.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Nguyễn Hoàng Phúc, thực hiện dưới sự hướng dẫn khoa học của Phó Giáo sư, Tiến sĩ Thoại Nam tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh, đã giải quyết bài toán này bằng việc đề xuất mô hình ứng dụng cấu trúc dữ liệu xác suất Counting Scalable Bloom Filter (CSBF) kết hợp với kiến trúc quản lý tập trung và cơ chế đồng bộ dòng thời gian (Timeline). Nghiên cứu không chỉ tối ưu hóa dung lượng truyền tải dữ liệu mà còn nâng cao hiệu năng vận hành của toàn bộ hệ thống thu phí tự động.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng các lý thuyết cấu trúc dữ liệu tiên tiến kết hợp với mô hình hệ thống thu phí tự động (Automated Fare Collection - AFC) đã được triển khai thành công tại nhiều đô thị lớn trên thế giới từ năm 1997. Khung lý thuyết trọng tâm của đề tài bao gồm bốn trụ cột chính:

Thứ nhất, cấu trúc Bloom Filter nguyên bản do Burton Howard Bloom phát triển năm 1970. Đây là một mảng bit kết hợp với các hàm băm độc lập nhằm kiểm tra tính thành viên của một phần tử trong một tập hợp với ưu điểm vượt trội về không gian lưu trữ và thời gian xử lý. Điểm đặc trưng của bộ lọc này là hoàn toàn không xuất hiện hiện tượng âm tính giả (False Negative), mặc dù chấp nhận một tỷ lệ dương tính giả (False Positive) rất nhỏ có thể tính toán và kiểm soát được theo công thức toán học xác suất.

Thứ hai, cấu trúc Counting Bloom Filter (CBF) được Li Fan giới thiệu năm 2000. Cải tiến này thay thế các ô bit đơn lẻ bằng các chuỗi bộ đếm kích thước 4-bit hoặc 8-bit, cho phép hệ thống thực hiện các thao tác xóa phần tử ra khỏi bộ lọc mà không cần phải khởi tạo lại toàn bộ cấu trúc dữ liệu từ đầu.

Thứ ba, biến thể Scalable Bloom Filter (SBF) do Almeida và các cộng sự đề xuất năm 2007. SBF giải quyết giới hạn kích thước cố định của Bloom Filter truyền thống bằng cách ghép nối nhiều bộ lọc phân vùng (Partitioned Bloom Filter - PBF). Hệ thống tự động mở rộng theo hệ số tăng trưởng s = 2 và tỷ số thắt chặt r = 0,8, đảm bảo xác suất dương tính giả gộp trên toàn bộ hệ thống luôn hội tụ và nhỏ hơn 5 lần sai số ban đầu ngay cả khi kích thước dữ liệu tăng đến vô hạn.

Thứ tư, kỹ thuật tối ưu hóa hàm băm kép của Adam Kirsch và Michael Mitzenmacher năm 2008. Thay vì phải tính toán hàng loạt hàm băm phức tạp gây tiêu tốn tài nguyên vi xử lý, giải pháp chỉ sử dụng kết quả của hai giá trị băm cơ sở trích xuất từ 8 byte đầu tiên của chuỗi băm SHA-256 (32 byte) để sinh ra k hàm băm thông qua công thức toán học tuyến tính, giữ xác suất trùng lặp ở ngưỡng an toàn tuyệt đối là 1 trên 2 mũ 64.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng kết hợp với phân tích định lượng hiệu năng hệ thống phần mềm. Dữ liệu thử nghiệm được thiết kế với quy mô mẫu là 1.000.000 bản ghi mã định danh thẻ từ, phản ánh chính xác cấu trúc nghiệp vụ phát hành thẻ của hệ thống giao thông công cộng đô thị. Phương pháp chọn mẫu ngẫu nhiên phân tầng được áp dụng để tạo ra các tập dữ liệu có quy mô tăng dần từ 200.000, 400.000, 600.000, 800.000 đến 1.000.000 phần tử.

Phương pháp phân tích được thực hiện trên môi trường giả lập chuẩn hóa gồm hệ điều hành Windows 11 Pro 64-bit, vi xử lý Intel Core i7-12700K, bộ nhớ RAM 32GB, hệ quản trị cơ sở dữ liệu SQL Server Developer 64-bit và nền tảng lập trình .NET 6 cùng C# 10 trên Visual Studio 2022. Lý do lựa chọn phương pháp thực nghiệm này là nhằm đối chiếu trực tiếp, khách quan giữa giải pháp Counting Scalable Bloom Filter với các phương thức truyền thống như truy vấn cơ sở dữ liệu quan hệ, tìm kiếm trong tập hợp mảng bộ nhớ và quét chuỗi tuần tự về hai chỉ số then chốt: dung lượng bộ nhớ tiêu thụ và thời gian xử lý phản hồi. Quá trình nghiên cứu và thu thập dữ liệu được thực hiện liên tục từ tháng 09/2023 đến tháng 12/2023.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình kiểm thử và đánh giá mô hình thực nghiệm đã mang lại những phát hiện quan trọng có giá trị thực tiễn cao:

Thứ nhất, giải pháp Counting Scalable Bloom Filter giúp tiết giảm dung lượng lưu trữ một cách ấn tượng. Khi kiểm thử trên tập dữ liệu 1.000.000 bản ghi thẻ từ, kích thước dữ liệu thô ban đầu là 5,56 MB. Sau khi được tính toán và nén qua cấu trúc CSBF với tham số mở rộng s = 2, kích thước bộ lọc chỉ còn chiếm 1,89 MB trong bộ nhớ, tương đương mức tiết kiệm hơn 66% dung lượng bộ nhớ lưu trữ và băng thông truyền dẫn mạng.

Thứ hai, tốc độ kiểm tra tính thành viên của thẻ từ đạt hiệu năng vượt bậc. Thời gian phản hồi của bộ lọc Bloom Filter nhanh hơn gấp khoảng 1.000 lần so với phương thức truy vấn trực tiếp trong cơ sở dữ liệu SQL Server hoặc duyệt tìm tuần tự trên chuỗi. Độ trễ xác thực luôn ổn định ở mức dưới 1 mili-giây cho mỗi thao tác quét thẻ, giải quyết triệt để tình trạng nghẽn hàng đợi tại cửa soát vé.

Thứ ba, cấu trúc dữ liệu thể hiện khả năng thích ứng linh hoạt với sự mở rộng quy mô. Với bộ lọc ban đầu có dung lượng tối đa 200.000 phần tử, khi lượng dữ liệu tăng lên mức 1.000.000 bản ghi, hệ thống chỉ cần kích hoạt thêm 3 bộ lọc thành phần với ngưỡng sức chứa tối đa tự động nâng lên mức 1.400.000 phần tử mà vẫn kiểm soát sai số dương tính giả ở mức tiệm cận lý thuyết cực nhỏ (khoảng 0,0001%).

Thứ tư, mô hình đồng bộ Timeline theo vector thời gian giúp giảm thiểu lưu lượng truyền dữ liệu giữa máy chủ trung tâm, các nhà xe và thiết bị POS di động. Các thiết bị ngoại vi chỉ cần tải về các gói tin thay đổi chênh lệch (delta) phát sinh từ mốc thời gian đồng bộ gần nhất, giúp giảm hơn 80% lưu lượng mạng so với cơ chế đồng bộ toàn phần truyền thống.

Thảo luận kết quả

Hiệu quả vượt trội của giải pháp xuất phát từ bản chất toán học của Bloom Filter: cấu trúc này không lưu trữ trực tiếp chuỗi ký tự hay dữ liệu định danh của thẻ cùng các con trỏ bộ nhớ phức tạp, mà chỉ biểu diễn sự tồn tại của phần tử thông qua các mảng bit và bộ đếm chỉ mục. Nhờ đó, độ phức tạp thuật toán khi tra cứu luôn là O(k) với k là số lượng hàm băm cố định, thay vì phụ thuộc tuyến tính O(N) vào quy mô của tập dữ liệu như các hệ thống cơ sở dữ liệu quan hệ.

Khi so sánh với các nghiên cứu trước đây về việc ứng dụng bộ đệm (cache) trong mạng diện rộng của Li Fan hay nghiên cứu của Almeida về bộ lọc mở rộng, việc tích hợp Counting Bloom Filter vào Scalable Bloom Filter đã khắc phục triệt để điểm yếu không thể xóa phần tử của bộ lọc mở rộng truyền thống. Bảng số liệu thực nghiệm cho thấy việc lựa chọn hệ số tăng trưởng s = 2 mang lại hiệu quả nén không gian vượt trội hơn hẳn so với hệ số s = 1 khi số lượng bản ghi vượt qua mốc 400.000 phần tử. Dữ liệu này có thể được trực quan hóa rõ nét qua biểu đồ tương quan giữa dung lượng RAM và số lượng phần tử, trong đó đường biểu diễn của phương pháp CSBF duy trì độ dốc logarithmic ổn định trong khi phương pháp quét mảng truyền thống tăng trưởng theo đường thẳng tuyến tính dốc đứng.

Hơn nữa, mô hình quản lý tập trung kết hợp lưu trữ Timeline đã giải quyết triệt để bài toán đồng bộ dữ liệu phân tán giữa các nhà xe buýt độc lập. Thời gian để một thay đổi về thẻ từ nhà xe này có hiệu lực trên máy POS của nhà xe khác được xác định chính xác theo công thức độ trễ mạng, triệt tiêu hoàn toàn sự phụ thuộc vào các thao tác đối soát thủ công của con người.

Đề xuất và khuyến nghị

Dựa trên các kết quả nghiên cứu khoa học và thực nghiệm thu được, luận văn đưa ra bốn nhóm giải pháp và khuyến nghị hành động cụ thể:

Thứ nhất, nâng cấp cấu trúc lưu trữ và tối ưu hóa phần mềm trên thiết bị POS. Các doanh nghiệp vận tải hành khách công cộng như VinBus, HanoiBus và các đơn vị vận hành xe buýt tại Thành phố Hồ Chí Minh cần tích hợp thuật toán CSBF trực tiếp vào bộ nhớ RAM cục bộ của các thiết bị POS di động trong giai đoạn quý 1 và quý 2 năm 2024. Mục tiêu là duy trì thời gian xác thực thẻ dưới 1 mili-giây và giảm 66% dung lượng bộ nhớ cần cấp phát, giúp kéo dài tuổi thọ phần cứng của thiết bị đầu cuối.

Thứ hai, thiết lập cổng dịch vụ đồng bộ dữ liệu Timeline tập trung. Trung tâm Quản lý và Điều hành Giao thông công cộng tại các đô thị cần triển khai hệ thống giao diện lập trình ứng dụng (API) đồng bộ dòng thời gian trong thời hạn 6 tháng. Giải pháp này giúp các nhà xe chỉ truyền nhận dữ liệu chênh lệch, cắt giảm ít nhất 75% chi phí cước viễn thông 3G và 4G hàng tháng cho toàn bộ đội xe gần 10.000 phương tiện.

Thứ ba, chuẩn hóa quy trình quản lý danh sách trắng và danh sách đen liên thông. Sở Giao thông Vận tải các địa phương cần ban hành quy chuẩn kỹ thuật đồng nhất về định dạng mã thẻ 64-bit hoặc 128-bit trong năm 2024. Quy trình này bảo đảm việc cập nhật thẻ hợp lệ hoặc khóa thẻ vi phạm được thực thi nhất quán trên toàn bộ mạng lưới liên tuyến, kiểm soát tỷ lệ dương tính giả dưới ngưỡng 0,0001%.

Thứ tư, mở rộng nghiên cứu sang biến thể bộ lọc hợp nhất phân tán. Đội ngũ kỹ sư công nghệ thông tin và các nhà nghiên cứu cần tiếp tục hoàn thiện biến thể Mergeable Counting Scalable Bloom Filter (MCSBF) trong giai đoạn 2024 đến 2025. Giải pháp nâng cao này sẽ hỗ trợ kiến trúc đa trung tâm dữ liệu, đáp ứng nhu cầu tích hợp liên vùng cho các đại đô thị có quy mô trên 10 triệu dân.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị tham khảo chuyên môn sâu sắc cho bốn nhóm đối tượng:

Thứ nhất, các kỹ sư phần mềm và kiến trúc sư hệ thống công nghệ thông tin. Tài liệu cung cấp hướng dẫn chi tiết về cách thức hiện thực cấu trúc dữ liệu xác suất nâng cao, phương pháp băm kép tối ưu với thuật toán SHA-256 và kỹ thuật quản lý bộ nhớ đệm (caching) cho các bài toán xử lý dữ liệu lớn trong thời gian thực.

Thứ tư, các doanh nghiệp vận tải và đơn vị vận hành giao thông công cộng. Luận văn đem đến giải pháp thực tiễn giúp cắt giảm hơn 66% chi phí hạ tầng máy chủ và băng thông truyền dữ liệu, đồng thời nâng cao độ ổn định cho các thiết bị thanh toán POS hoạt động tại những khu vực có sóng di động chập chờn.

Thứ ba, các nhà quản lý đô thị và cơ quan hoạch định chính sách giao thông thông minh. Nghiên cứu phác thảo mô hình kiến trúc chuẩn mực để xây dựng hệ thống vé điện tử liên thông đa phương thức cho hơn 60 tỉnh thành, phục vụ chuyển đổi số hệ thống xe buýt, đường sắt đô thị và các phương tiện công cộng trong tương lai.

Thứ tư, học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính hoặc Hệ thống thông tin. Đây là nguồn tư liệu học thuật phong phú về cấu trúc dữ liệu xác suất, thuật toán phân tán và phương pháp thiết kế kịch bản kiểm thử hiệu năng trên tập mẫu 1.000.000 bản ghi.

Câu hỏi thường gặp

Cấu trúc dữ liệu Bloom Filter có nhược điểm gì và được khắc phục thế nào trong nghiên cứu? Điểm yếu của Bloom Filter truyền thống là kích thước chuỗi bit cố định và không thể xóa phần tử. Luận văn khắc phục triệt để bằng cách tích hợp Counting Bloom Filter (sử dụng bộ đếm thay cho bit đơn để hỗ trợ xóa phần tử) với Scalable Bloom Filter (tự động mở rộng theo cấp số nhân với hệ số s = 2 và r = 0,8 khi lượng thẻ vượt ngưỡng ban đầu).

Tại sao thiết bị POS không gửi truy vấn trực tiếp về máy chủ trung tâm mỗi khi quẹt thẻ? Nếu toàn bộ gần 10.000 xe buýt đồng loạt gửi yêu cầu về máy chủ trong giờ cao điểm, lưu lượng mạng sẽ quá tải dẫn đến nghẽn hệ thống. Việc kiểm tra cục bộ qua bộ lọc CSBF trên máy POS giúp thiết bị hoạt động độc lập không cần internet liên tục, tiết kiệm chi phí băng thông 3G/4G và tăng tốc độ xử lý gấp 1.000 lần.

Biến thể Counting Scalable Bloom Filter đạt hiệu năng tối ưu nhất với những tham số nào? Qua thực nghiệm trên 1.000.000 bản ghi, hệ thống đạt hiệu năng cao nhất khi thiết lập tỷ số thắt chặt r = 0,8, hệ số tăng trưởng s = 2 và kích thước bộ lọc cơ sở ban đầu là 200.000 phần tử. Cấu hình này giúp không gian bộ nhớ tăng theo quy luật tối ưu mà vẫn giữ xác suất dương tính giả gộp ở mức cực thấp xấp xỉ 0,0001%.

Cơ chế Timeline đóng vai trò gì trong việc đồng bộ danh sách thẻ giữa các nhà xe? Dữ liệu Timeline đóng vai trò như một trục vector thời gian chuẩn mực. Thay vì gửi toàn bộ cơ sở dữ liệu, trung tâm chỉ truyền các thông tin thẻ thay đổi từ mốc thời gian đồng bộ gần nhất của từng nhà xe. Cơ chế này bảo đảm tính toàn vẹn dữ liệu trên toàn mạng lưới và cho phép tính toán chính xác thời gian thay đổi có hiệu lực.

Kỹ thuật băm kép SHA-256 được triển khai thế nào để tối ưu tốc độ tính toán? Hệ thống trích xuất 8 byte đầu tiên từ chuỗi băm 32 byte của thuật toán SHA-256 để gán cho hai số nguyên 32-bit không dấu. Công thức băm tuyến tính kết hợp hai giá trị này giúp sinh ra k hàm băm tối ưu cho bộ lọc mà không cần gọi lại thuật toán SHA-256 nhiều lần, đồng thời duy trì xác suất va chạm ở mức an toàn tuyệt đối là 1 trên 2 mũ 64.

Kết luận

Luận văn thạc sĩ của tác giả Nguyễn Hoàng Phúc đã giải quyết trọn vẹn bài toán quản lý và xác thực danh sách thẻ từ trong giao thông công cộng thông qua những đóng góp nổi bật:

• Đề xuất thành công mô hình kết hợp sáng tạo giữa bộ lọc đếm và bộ lọc mở rộng thành biến thể Counting Scalable Bloom Filter (CSBF) đáp ứng linh hoạt các nghiệp vụ thêm, xóa và tăng trưởng dữ liệu thẻ.
• Giảm hơn 66% dung lượng bộ nhớ lưu trữ và truyền dẫn, đồng thời tăng tốc độ kiểm tra tính thành viên của thẻ lên gấp 1.000 lần so với các phương pháp truy vấn cơ sở dữ liệu truyền thống.
• Xây dựng hoàn chỉnh kiến trúc quản lý tập trung và cơ chế đồng bộ dòng thời gian Timeline, bảo đảm dữ liệu thẻ luôn nhất quán và độc lập giữa các nhà xe.
• Chứng minh tính khả thi và độ ổn định cao của giải pháp thông qua kịch bản thực nghiệm mô phỏng trên tập dữ liệu chuẩn 1.000.000 phần tử tương đương quy mô đô thị lớn.
• Mở ra định hướng phát triển biến thể bộ lọc hợp nhất phân tán Mergeable CSBF phục vụ hệ thống giao thông thông minh đa vùng trong giai đoạn 2024 đến 2025.

Các cơ quan quản lý đô thị, doanh nghiệp vận tải hành khách và đội ngũ kỹ sư phần mềm quan tâm đến giải pháp tối ưu hóa hiệu năng thu phí tự động có thể tham khảo toàn văn luận văn và mã nguồn thực nghiệm để áp dụng trực tiếp vào các dự án chuyển đổi số giao thông công cộng hiện nay.

Trích đoạn nội dung tài liệu

Mở đầu 1. Giới thiệu đề tài Theo xu thế phát triển chung của thế giới, Việt Nam đang phải đối mặt với những vấn đề về giao thông đô thị như sự gia tăng của phương tiện cá nhân, áp lực về cơ sở hạ tầng và nhu cầu đi lại của người dân ngày càng cao. Nhận thức rõ áp lực của phát triển dịch vụ vận tải đối với phát triển đô thị, Chính phủ và Bộ Giao thông Vận tải cũng như các địa phương từ nhiều năm trước đây và hiện nay đã xác định phát triển giao thông công cộng là giải pháp tối ưu và được ưu tiên phát triển để giải quyết tình trạng trên. Theo Bộ Giao thông Vận tải, việc phát triển hệ thống vận tải hành khách công cộng đã đạt được những kết quả bước đầu.

Đến thời điểm này đã có 60/63 tỉnh, thành phố trên cả nước (trừ Yên Bái, Lai Châu, Hà Giang) có vận tải hành khách công cộng bằng xe buýt hoạt động với gần 10.000 phương tiện và 280 doanh nghiệp, hợp tác xã vận tải thực hiện. Từ năm 2019 đến nay, với cuộc cách mạng công nghiệp 4.0 hiện nay thì ngành giao thông công cộng cũng đang dần chuyển mình để thay thế vé giấy truyền thống với sử dụng vé điện tử và thẻ điện tử nhằm bảo vệ môi trường và tiết kiệm nhiều chi phí trong việc in vé giấy hàng ngày cũng như việc thay đổi đường lối quản lý thông qua các báo cáo tự động từ các phần mềm thay vì sử dụng sức người truyền thống.1: Trạm bán vé tháng xe buýt của HanoiBus Trong thời gian vừa qua có các nhà vận hành xe buýt ứng dụng công nghệ này có thể kể đến như Zalo với UNIPASS [1] đi đầu trong việc đầu tư thiết bị đọc thẻ từ trên các tuyến xe buýt tại TP. Hồ Chí Minh. VINBUS với hệ thống xe buýt điện và thanh toán bằng thẻ ATM kết hợp thẻ tháng do VINBUS phát hành [2] cho hệ thống xe buýt tại TP.2: Cổng thu vé tự động của UNIPASS trên xe buýt 2 Hình 1.3: Thiết bị thu vé cầm tay trên xe VINBUS Trong quá trình chuyển đổi như vậy thì giải pháp sử dụng thẻ từ được tập trung hơn cả vì khi sử dụng thẻ từ thì mỗi người dân chỉ cần dùng một thẻ từ để có thể thanh toán cho toàn bộ các phương tiện công cộng mà người đó đã mua.

Điều đó giúp các nhà cung cấp dịch vụ tiết kiệm được một chi phí rất lớn trong việc in vé giấy hàng ngày và giúp bảo vệ môi trường. Và mới gần đây theo báo điện tử VnExpress ngày 28/11/2023 [15], Hà nội đã tổ chức khai trương thí điểm hệ thống vé điện tử liên thông đa phương thức cho giao thông công cộng. Bằng việc triển khai vé điện tử đã giải quyết được nhiều bất cập, trong đó có tiết giảm kinh phí ngân sách nhà nước thông qua việc không còn cần nhân viên phục vụ. Hiện tại số lượng tuyến được sử dụng vé điện tử liên thông đã lên đến > 25 tuyến mặc dù chỉ trong thời gian thí điểm.

Không chỉ vậy theo bài báo Nhà nước đang có kế hoạch trợ giá thêm cho xe buýt theo từng năm cho thấy vấn đề cấp thiết trong công cuộc thúc đẩy người dân sử dụng giao thông công cộng nhiều hơn. Với các hình thức trên thì hình thức sử dụng thiết bị xác thực trên phương tiện yêu cầu các giải pháp về công nghệ nhiều hơn hẳn các hình thức khác, điều đó xảy ra do các 3 thiết bị xác thực giờ đây sẽ luôn di chuyển chung với phương tiện. Thiết bị xác thực hoạt động bằng việc kiểm tra xem thẻ của bạn có hợp lệ hay không dựa vào danh sách trắng và đen. Hiện nay thì mỗi thiết bị cần phải đồng bộ về trung tâm vận hành để cập nhật lại danh sách mới nhất, sau đó mỗi khi cần xác thực thì máy sẽ quét toàn bộ dữ liệu đó để kiểm tra liệu thông tin thẻ có trong danh sách hay không.

Chúng ta sẽ cần giải quyết các bài toán về lưu lượng truyền dữ liệu từ các thiết bị về trung tâm vận hành, làm sao để thiết bị xác thực thực thi nhanh hơn để đáp ứng được các giờ cao điểm khách vào liên tục? Chúng ta có thể áp dụng được công nghệ Bloom Filter vào ứng dụng này thì ta có thể giải đáp cùng một lúc cả hai bài toán trên. Bloom Filter cung cấp chức năng kiểm xem dữ kiện 𝑥 có thuộc một tập 𝑆 không và ta có thể tối giản được không gian sử dụng thay vì kiểm tra trong tập dữ liệu truyền thống. Vì vậy trong luận văn này ta phát triển một mô hình ứng dụng công nghệ Bloom Filter để quản lý thẻ từ whitelist và blacklist trong giao thông công cộng. Cấu trúc luận văn Cấu trúc các phần còn lại của luận văn như sau: Chương 2 trình bày các công trình nghiên cứu liên quan, các cơ sở lý thuyết về Bloom Filter, các biến thể của Bloom Filter cũng như các nghiên cứu về hệ thống AFC.

Chương 3 trình bày mô hình đề xuất. Chương 4 trình bày về cách hiện thực, kịch bản đánh giá giải pháp. Chương 5 tổng kết và phương hướng phát triển tiếp theo của đề tài. 4 Chương 2: Cơ sở lý thuyết 2.

Các nghiên cứu liên quan về hệ thống AFC Hệ thống Automated Fare Collection (AFC) được giới thiệu lần đầu vào năm 1997 với hệ thống Octopus card ở Hồng Kong[3], Octopus card là loại thẻ từ thông minh không tiếp xúc được phát triển để thực hiện các giao dịch thanh toán trực tuyến hoặc không trực tuyến trên AFC của với hệ thống giao thông công cộng ở Hong Kong[3]. Từ đó việc sử dụng thẻ từ thông minh contactless đã trở thành một tiêu chuẩn thanh toán của hệ thống AFC, mặc dù có nhiều hệ thống sử dụng nhiều phương thức thanh toán khác nhau. Một hệ thống AFC thường bao gồm các thành phần cơ bản: - Phương tiện thanh toán (thẻ từ, tiền mặt, QR, …) - Thiết bị đọc/ghi giao dịch (máy POS, cổng thanh toán cố định,…) - Các máy trạm kết nối với các thiết bị đọc/ghi - Trung tâm văn phòng vận hành - Hệ thống xử lý vận hành trung tâm Gần đây khi các ngân hàng đang tiến hành phát hành các loại thẻ từ thông minh không tiếp xúc thì các hệ thống AFC cũng kết hợp với ngân hàng tích hợp sử dụng thẻ ngân hàng song song với các loại thẻ từ mà hệ thống đang cung cấp để mang lại sự tiện nghi cho người dùng. Ở Việt Nam ta, từ năm 2019 trên địa phận thành phố Hồ Chí Minh Zalo đã phối hợp với một số nhà vận hành xe buýt phát triển hệ thống AFC ứng dụng thẻ UNIPASS trên một số tuyến xe[1].

Về phương thức thanh toán của hệ thống của UNIPASS thì mỗi khi khách hàng chạm thẻ vào thiết bị đọc sẽ gọi về các máy trạm để tiến hành xác thực và thanh toán. Tuy nhiên Zalo vẫn chưa giải quyết được việc nhà vận hành xe buýt vẫn phải 5 bán vé giấy đối với các trường hợp sử dụng tiền mặt và các dạng thanh toán khác. Tuy nhiên vào năm 2021 thì công ty VINBUS – một công ty con của tập đoàn VINGROUP đã phát triển một hệ thống AFC mới với độ tích hợp cao cho các nhà phân phối khác nhau kể cả các ngân hàng khi sử dụng máy Point of Sale (POS) xác thực tại chỗ cho khách hàng khiến trải nghiệm khách hàng được nâng cao và tiện lợi hơn. Tuy nhiên khi tìm hiểu hơn về hệ thống thì chúng ta đã thấy cách máy POS mà VINBUS hiện đang vận hành đang gặp một vài vấn đề về tốc độ xử lý, dung lượng đường truyền lớn cần có phường án để giải quyết khi hệ thống càng lúc càng phát triển.

Bước đến năm 2022, Đảng và nhà đã ra chỉ thị bắt đâu công cuộc số hóa cho giao thông công cộng với bài toán phát hành thẻ từ, thẻ điện tử cho khách hàng. Khi này với sự gia tăng nhanh chóng của tập khách hàng sử dụng giao thông công cộng, bài toán lại phát sinh về tập dữ liệu lớn của khách hàng. Khi khách hàng sử dụng thẻ từ, thẻ điện tử thì cần nhanh chóng xác định tính hợp lệ để cho phép khách hàng sử dụng dịch vụ. Với lượng dữ liệu lớn việc xác minh danh tính hợp lệ cần các hệ thống tốn thêm nhiều thời gian hơn và việc đó làm giảm trải nghiệm của khách hàng.

Và với tập khách hàng khó tính như Việt Nam thì việc trải nghiệm chậm trễ luôn là một điểm trừ rất lớn. Vì vậy cần có một giải pháp có thể đáp ứng được các nhu cầu về giảm dung lượng đường truyền, giảm thời gian xác thực, đảm bảo được tính hiệu quả. Bloom Filter Bloom Filter lần đầu được trình bày bởi Burton Howard Bloom vào năm 1970. Bloom Filter là một cấu trúc dữ liệu xác suất được tối ưu cho không gian nhằm mục đích kiểm tra một phần tử nào đó có phải thuộc trong một nhóm không? Những kết quả dương tính giả (False Positive) có thể xảy ra nhưng tuyệt đối không xuất hiện trường hợp âm tính giả (False Negative) – nói cách khác thì khi chúng ta tiến hành kiểm tra một phần tử liệu có thuộc trong một tập hợp thì ta sẽ có câu trả lời là “Có thể thuộc” hoặc “Chắc chắn 6 không thuộc”.

Số lượng dữ liệu trong tập hợp càng nhiều thì tỉ lệ False Positive sẽ càng lớn. Ý tưởng của Bloom là ánh xạ một phần tử 𝑥 ∈ 𝑆 vào một giá trị 𝑦 = ℎ(𝑥) ∈ 𝑌 sử dụng một hàm băm h(), và kiểm tra tính thành viên của một phần tử 𝑥′ ∈ 𝑆 bằng việc kiểm tra 𝑦′ = ℎ(𝑥′) ∈ 𝑌 và thực hiện điều đó với nhiều hàm băm h. Với nghiên cứu của Bloom, bằng việc đánh đổi tỉ lệ false positive, Bloom Filter có lợi thế về không thời gian (Probability of false positives) đáng kể so với các cấu trúc dữ liệu khác để biểu diễn các tập hợp, chẳng hạn như cây tìm kiếm nhị phân tự cân bằng (self-balancing binary search trees), cây tiền tố (digital tree – prefix tree), bảng băm(hash table), mảng đơn(simple arays) hoặc danh sách liên kết(linked list) của các mục. Hầu hết trong các cấu trúc dữ liệu trên đều yêu cầu lưu dữ một số dữ liệu cần thiết, có thể là bất kỳ dữ liệu gì từ một số lượng nhỏ bit đối với số nguyên nhỏ, cho đến số lượng bit tùy ý đối với chuỗi (còn cây tiền tố là một ngoại lệ vì chúng có thể chia sẻ bộ nhớ giữa các phần tử với tiền tố giống nhau).

Bộ lọc Bloom hoàn toàn không lưu trữ các mục dữ liệu, có giải pháp riêng cho việc lưu trữ thực tế.