contributed articles

A P PLIED COMPU TE R S CI EN CE is concerned with the development of algorithms, applications, software, services, methods and measures, and hardware and devices. Excellent work continues to be done to make information technology accessible and usable for people with disabilities. For example, a number of familiar consumer technologies started out designed to provide access to people with disabilities, including the audiobook, speech recognition, captioning, and speech output (screen readers). Speech recognition enables hands-free computing, which is useful in situations like driving. Captioning of videos renders them available to text-based search algorithms but also makes video consumable when ambient sound levels are high, as in airports and gyms. Audiobooks, which began as a way for blind people to access reading material, are now everyday companions for travelers and commuters everywhere. [START_REF] Lazar | Ensuring Digital Accessibility Through Policy and Process[END_REF] In a 2012 Communications column, former ACM president Vinton G. Cerf highlighted the importance and difficulty of designing and developing accessible computing systems, making a public call for ideas and reports on success stories and experiences. [START_REF] Cerf | Why is accessibility so hard?[END_REF] Despite the long-term focus on making technology accessible for people with disabilities, the computing profession has not focused on making itself inclusive of people with disabilities; such people remain highly underrepresented at all levels and roles, including practitioner, researcher, student, and teacher. [START_REF] Burgstahler | Strategies for increasing the participation in computing of students with disabilities[END_REF] Although the percentage of undergraduate students with disabilities in technology-related majors is fairly representative of the worldwide population as a whole, it is estimated that less than 1% of students who earned Ph.D.'s in computer science (as of 2011) identify as students with disabilities. [START_REF] Taylor | Data trends on minorities and people with disabilities in computing[END_REF] People with disabilities bring diverse perspectives to the design of technology. Like Cerf, the authors of this article believe becoming more inclusive will be of great benefit to ACM and to technology in general. It is thus important to examine the barriers that exist and determine, as a professional organization, how we can overcome them. This makes strategic and tactical sense; for a professional organization that wants to increase membership, there are many potential community members with disabilities More accessible conferences, digital resources, and ACM SIGs will lead to greater participation by more people with disabilities.

Making

BY JONATHAN LAZAR, ELIZABETH F. CHURCHILL, TOVI GROSSMAN, GERRIT VAN DER VEER, PHILIPPE PALANQUE, JOHN "SCOOTER" MORRIS, AND JENNIFER MANKOFF key insights

People with disabilities are a potential source of ideas and additional membership for professional computing organizations.

Including people with disabilities in the decision-making processes of professional computing organizations ensures the most important barriers are addressed first.

Processes developed over years are needed to make physical conferences and their related digital content accessible to people with disabilities.

man Interaction (http://www.sigchi. org/), to be more inclusive for people with disabilities. We note that the term "inclusive" can have a broader meaning that involves economic, geographic, and other types of diversity. In this article, we use the meaning of inclusion found in the fields of education and law, where being inclusive means providing equal opportunity for participation by people with disabilities.

Addressing Accessibility SIGCHI is one of ACM's largest special interest groups, with approximately 3,500 members as of 2016. As with all SIGs, SIGCHI's core activities are to sponsor conferences, publish articles, and guide and support professional activities through mentoring and career development.

Over the past few years SIGCHI has sought to be more inclusive by decreasing barriers for participation encoun-who could join the community were it more accessible.

So how do professional organizations in computing start to make themselves more accessible? What needs to be done to enable better access for researchers, practitioners, teachers, and students with disabilities? This article provides an overview of the process and a case study of the steps taken by SIGCHI, the ACM Special Interest Group on Computer-Hu-

SIGCHI as Case Study

SIGCHI has been addressing accessibility across the areas identified for improvement through a number of experimental initiatives. For example, an accessibility chair was first appointed at SIGCHI's flagship conference CHI as early as 1996 with some success, but the position did not continue consistently in subsequent conferences. A broader effort was needed, so, in 2011, the SIGCHI Executive Committee began a program to raise awareness and rationalize processes around inclusiveness; see the sidebar "SIGCHI Accessibility Timeline."

Education of leadership. The SIG-CHI Executive Committee established a program of information gathering, reaching out to key professional groups and members of the SIGCHI community with disabilities, collaborating explicitly with two groups: ACM SIGACCESS. ACM SIGACCESS is in many ways a role model, with accessible conferences and publications and a large percentage of community members with disabilities. SIGACCESS has documentation and processes for how to make conferences and digital resources accessible for all who want to participate. A core challenge in applying SIGACCESS approaches to the SIGCHI context is the difference in the attendee population. SIGCHI members are not all as aware or committed to accessibility as SIGACCESS members, whose expertise and interest center on accessibility. SIGACCESS also has a longstanding tradition of inclusion, so people with disabilities know their needs will be met at a SIGACCESS conference. SIGCHI needs to build this awareness among its membership, devise inclusive practices, and build a reputation for accessibility. To create awareness, enthusiasm, and engagement within a less-invested membership requires a different set of strategies.

AccessComputing. Staff of the Access-Computing project at the University of Washington have been key to SIGCHI's progress in accessibility. AccessComputing is a National Science Foundation-funded Broadening Participation Alliance that focuses on increasing access to the field of computer science for people with disabilities. [START_REF]AccessComputing: The Alliance for Access to Computing Careers[END_REF] At the August 2013 SIGCHI Executive Committee meeting in Seattle, a subgroup tered by people with disabilities. In collaboration with other SIGs (such as SIGACCESS, http://www.sigaccess. org/), our work has included indirect activities (such as educating conference leadership about disabilities and advocating for inclusion of people with disabilities on committees). We have also improved accessibility at conferences and to digital resources and provided professional-development activities.

We began by recognizing that career development, in all areas of computing, is greatly enhanced through several activities: attendance at conferences on a regular basis; production and consumption of digital resources, from blogs to multimedia content to articles in the ACM Digital Library; and involvement in sponsored mentorship programs. We identified three disability-related concerns that had to be addressed: organization and involvement of stakeholders; considerations regarding physical accessibility; and considerations regarding digital accessibility. Here, we address each in turn. Moreover, we have three corresponding goals in telling the SIGCHI story: underscore the importance of stakeholder engagement; offer broad suggestions for how large SIGs can improve inclusiveness of physical events and digital content; and underscore that addressing physical and digital accessibility is an ongoing process that takes time, with involvement by many stakeholders. The main message is that inclusiveness starts with the creation of an environment of continuous improvement in inclusiveness.

Before discussing them, however, we acknowledge that accessibility is a continuum and SIGCHI (or any other SIG) will not become a highly accessible and inclusive organization overnight.

Organization of stakeholders. It is important for the SIGCHI community to have an ongoing process for and platform through which people with disabilities can participate actively. SIGCHI thus created an advocacy group-the SIGCHI Accessibility Community-to work from within SIGCHI to develop best practices for ensuring improved accessibility. It has worked over the past several years on disabilityrelated issues and produced a report [START_REF]edit?pref=2&pli=1#heading=h[END_REF] documenting accessibility concerns within the SIGCHI community. Jenni-fer Mankoff, one of the authors of this article, is chair of the SIGCHI Accessibility Community. The other authors are members of the community who have held leadership positions in the SIGCHI Executive Committee or in the conferences, in particular CHI 2014, where many of the practical initiatives were launched and trialed.

Physical accessibility. Many people with disabilities report that program committee meetings and conference facilities are often not accessible to people with motor impairments (such as those in wheelchairs). Moreover, elevators are sometimes not available, and few presentation stages have ramps. Processes should thus be planned in advance for requesting disability-related accommodations (such as sign-language interpretation for presentations and easy booking of accessible hotel rooms), and on-site accommodations need to be made available and communicated effectively in promotional materials or websites, as well as at event venues.

Digital accessibility. Many computing professionals use the resources available on the central ACM website (such as job banks, blogs, videos, and articles in the ACM Digital Library) that serve as the foundation for information sharing and knowledge growth. Within ACM, each SIG has its own website, with targeted digital resources for the needs of SIG members. Too often, however, the sites and information hosted are not in an accessible format, creating a discriminatory barrier. One approach has been to provide an "information on request" option for people unable to access certain content. But this is not an adequate solution; when digital resources are made accessible only upon request, the amount of material available to someone with a disability is limited and a time delay is introduced. This puts the person with a disability at a disadvantage compared to those without disabilities. Both the delay in time and the limitation in the amount of content available (due to "upon request" accommodations) can be considered forms of discrimination. [START_REF] Lazar | Ensuring Digital Accessibility Through Policy and Process[END_REF] An informal analysis we conducted at SIGCHI revealed many conference websites, paper-submission processes, and conference-registration processes are not accessible. committee chairs from CHI 2018 onward. One of the co-authors of this article, Jennifer Mankoff, was appointed to the steering committee to supervise implementation of a consistent level of accessibility throughout all SIGCHIsponsored conferences.

SIGCHI Accessibility Community

As more feedback and suggestions became available, it was necessary to prioritize requests in light of limited resources. Meeting in August 2013, the SIGCHI Executive Committee decided to crowdsource some of the feedback and priority setting. There is a mecha-nism on the SIGCHI website for the formation of SIGCHI "communities" in which members with a similar interest are able to use certain features on the website, including voting and resource sharing. [START_REF]SIGCHI Communities[END_REF] At the same meeting of the Executive Committee, several people who had been involved in the discussions about improving SIG-CHI accessibility were invited to form a SIGCHI community on the topic of accessibility. Unlike SIGACCESS, the SIGCHI Accessibility Community's primary functions are to provide feedback to SIGCHI on accessibility efforts, help set priorities, and provide the op-of the SIGCHI Executive Committee working on accessibility met with the AccessComputing leadership team.

Interaction with these groups made clear that a number of recommendations could be made. First, SIGCHI event organizers should be encouraged to appoint accessibility chairs or ensure that an advocate for accessibility would be part of the conference leadership committee. Second, discussions about stakeholder responsibilities should occur to, for example, clarify what aspects of accessibility are under the purview of ACM, vendors (such as website developers), and the conference committee. Such issues could perhaps be resolved or highlighted through appointment of accessibility chairs. Third, SIGCHI should recognize that reliance on volunteers represents a significant barrier to the scalability of accessibility throughout ACM and may be a major factor in limiting what leadership is able to accomplish.

As noted, SIGCHI leadership also discovered how advantageous it is to separate physical accessibility from digital accessibility. Although both are important, rarely in volunteer organizations like SIGCHI do the same people have responsibility for both for several reasons. First, the combination of expertise in physical and digital accessibility rarely resides in one person; for example, it is unlikely a single individual will have great experience in digital document markup languages for accessibility and the guidelines and recommendations for doorframe size and turnaround distance needed for wheelchair accessibility. Second, volunteer time is precious; it can be prohibitively time consuming for one person to take on all such responsibility. During the time period covered here, 2011-2016, within SIGCHI, the vice president (VP) of conferences and the general conference chairs for each sponsored and in-cooperation conference would have responsibility for physical accessibility. For digital accessibility, the VP of operations (for the website), the VP of publications (for the content being published), and the conference technical program chairs would have responsibility. The SIGCHI Executive Committee created a new structure-the CHI Steering Committee-in 2016 to oversee the activities of all conference

The following is a timeline of SIGCHI's actions related to accessibility:

2011. Focused discussions on accessibility and inclusiveness begin at SIGCHI Executive Committee meetings.

2012. The SIGCHI Conference Management Committee begins using the SIGACCESS conference checklist at on-site facility walkthroughs; note it affected only locations that, at the time, were not yet contracted though is now in place for all future conferences.

2013. The Executive Committee creates a formal plan for inclusiveness at its spring meeting.

Email alias. An email alias is created to invite SIGCHI members to share accessibility suggestions and provide a way for them to report problems;

Inclusiveness. The issue of inclusiveness is raised by the Executive Committee at the CHI 2013 Town Hall meeting in Paris;

Questions. Questions about accessibility and inclusiveness are added to the CHI 2013 post-conference survey and to all subsequent CHI post-conference surveys;

Accessibility chairs. The positions of "digital accessibility chair" and "physical accessibility chair" are added to the CHI 2014 committee;

AccessComputing. The SIGCHI Accessibility Community brought one major concern-accessibility of other SIGCHI-sponsored conferences-to the attention of the Executive Committee: Although the flagship CHI conference is steadily improving accessibility, most other SIG-CHI-sponsored or in-cooperation conferences have taken no steps toward improving accessibility. The Accessibility Community has also highlighted key factors affecting accessibility that need to be addressed, including lack of a clear process (from the member perspective) for handling accessibility problems and constraints; the burden of negotiating accessibility on a caseby-case basis; the problems of depending entirely on volunteers to assess and improve accessibility; and the lack of accessibility at venues (such as in program committee meetings).

Physical accessibility. SIGCHI efforts related to physical accessibility have been evolving for several years. The SIGCHI Conference Management Committee first adopted the SIGAC-CESS conference physical-accessibility checklist for meeting and conferencesite walkthroughs in 2012. a The first direct engagement with membership as a whole about physical accessibility was at the CHI 2013 conference in Paris, where SIGCHI leadership heard complaints about the venue's lack of physical accessibility. Discussion at the SIG Town Hall meeting at the conference led to adding a post-conference survey question regarding physical accessibility, resulting in 29 responses. Four issues were cited, the first two relating to hotel accommodations and the third and fourth to the convention venue itself:

Closest hotel. The closest recommended hotel was inaccessible for those using a wheelchair or scooter;

Connecting paths. Supposedly accessible connecting paths between the hotels and the convention center were poorly signed and not consistently open;

Ramps. At the convention center, presenters needing wheelchair or scooter access could not easily reach Digital accessibility. For the CHI 2014 digital accessibility chair, three topical areas were suggested by the conference chairs for improvement: conference website, conference mobile apps, and papers-publication process.

Among them, the most challenging was the papers review process. There is one clear international technical standard for webpages-the Web Content Accessibility Guidelines (WCAG) version 2.0-that has been adopted by many national governments, educational organizations, and corporations. [START_REF]World Wide Web Consortium (Web Accessibility Initiative)[END_REF] The guidelines were used in May 2013 in two preliminary evaluations of accessibility-one by a SIGCHI Executive Committee member and one by the AccessComputing Project at the University of Washington-and changes were made to the website (minor tagging of images) to improve accessibility. This was a good starting point but not optimal because there should be more evaluations involving people with disabilities. A similar process was used for the CHI 2015 and the CHI 2016 conferences, and it is hoped the SIGCHI Accessibility Community can be involved in the future to perform user-based accessibility evaluations.

The technical program chair and digital accessibility chair for CHI 2014 learned that the papers-publishing company SIGCHI works with, Sheridan, offers the option of evaluating accepted-paper .pdf files for accessibility and notifying authors of violations. However, this option was not possible stages, requiring portable ramps to be added; and

Distance. The vast size of the convention center meant considerable distance between events, affecting attendees with mobility limitations.

Based on the data collected, SIG-CHI leadership concluded that two categories of data or communication were missing between organizers and attendees for the organization's conferences:

Attendees. Attendees, especially presenters, need a mechanism for letting conference planners know in advance if they require any type of special accommodations; and

Conferences. Conferences need to let potential attendees know in advance which meeting locations and hotel accommodations are accessible and which are not and provide specific directions (and, where appropriate, signage) to guide attendees along accessible routes between hotels and convention centers.

To address the first, a box was added to the subsequent conference registration form for CHI 2014, as well as for 2015 and 2016. The online forms invite authors of accepted papers/notes to indicate if the presenters of the papers/ notes will need any type of disability-related accommodation and, if so, what type; for example, SIGCHI indicated it would fund as many sign-language interpreters as needed, but they must be requested in advance. To address information flow, a webpage was set up for the CHI 2014 conference website by the conference management team, the chairs, and the SIGCHI executive VP dedicated to physical accessibility, including detailed information regarding transportation and convention center and hotel contacts. The same information was provided for the CHI 2015 and CHI 2016 conferences. In addition, the committee in charge of venue selection began (as discussed in the sidebar's timeline) to assess site accessibility so a basic level of access can be ensured (such as wheelchairs and scooters being able to get to every part of the conference).

In 2014, SIGCHI leadership continued to ask about accessibility in the postconference survey; while such survey data is not public, summaries of the data are included in reports from the SIG-CHI Accessibility Community. [START_REF]edit?pref=2&pli=1#heading=h[END_REF] From CHI16 telepresence robots at recharging station.

thors. In addition, SIGCHI maintains an up-to-date wiki page describing current best practice for creating accessible .pdf documents. 2 Unfortunately, the CHI 2015 and CHI 2016 conferences did not use the same approach as was used for CHI 2014 of providing specific feedback to authors on the accessibility of their papers. However, the CHI 2015 digital accessibility chair offered to have his research group (from Carnegie-Mellon University) make papers accessible for authors, with 25 authors requesting the service. [START_REF] Brady | Creating accessible PDFs for conference proceedings[END_REF] Although the service was not continued in 2016, the instructions on accessibility and the information in the paper template were still included. While the goal should be year-to-year consistency, having different approaches tested each year does give some useful data for future conference chairs.

Based on data collected by the CHI 2014 Conference Committee, accessibility of papers at CHI 2014 improved compared with previous years. Figure 1 shows the percentage of published CHI papers from 2010 to 2016 that included each of the five recommended accessibility features. The data in the figure indicates the accessibility reports sent to authors in 2014 helped encourage accessibility of papers. The accompanying table lists the same data from the figure in tabular form, showing compliance in four of five (not tab order) categories rose from 16% to 26%, much higher than in previous years. In every category of accessibility feature, the papers submitted were more accessible in 2014 than in any previous year of the CHI conference, though they were not 100% accessible, which is indeed the goal. A separate analysis confirmed that the accessibility of CHI papers improved in 2014. [START_REF] Brady | Creating accessible PDFs for conference proceedings[END_REF] However, without giving the authors individual notification of their papers' accessibility between acceptance and camera-ready submission in 2015, the accessibility levels of papers dropped between 2014 and 2015. Averaged over the five measures of accessibility, the accessibility of papers between 2014 and 2015 dropped nearly 50%. Figures were generally consistent between 2015 and 2016, except for the alternative text, which dropped by more than 50%, with 8.26% compliant in 2015 compared to 3.67% compliant in 2016.

for the CHI 2014 conference because the timeline and contract with the company had already been fixed. It will thus be investigated for future conferences for which contracts have not been set; the CHI 2015 contracts had already been signed, and the CHI 2016 committee decided not to take the option.

Many guides to .pdf accessibility assume much knowledge about .pdf design and provide a high level of detail about every possible violation. Unlike the WCAG 2.0 for webpages, there is no one clear, agreed-upon standard for .pdf documents. From all the various guidelines, from SIGACCESS and the various international standards bodies, the CHI 2014 papers review committee eventually adopted five recommendations for implementation for the CHI 2014 papers, in consultation with the AccessComputing group. The information was provided to authors on the conference website, [START_REF]CHI 2014 Program Committee. CHI 2014 Guide to an Accessible Submission[END_REF] and the same guidelines were used for CHI 2015 and CHI 2016. The focus was on improving aspects of .pdf accessibility specifically related to CHI papers, including alternative text provided for images, table headers, generating a tagged .pdf, default language information in the .pdf, and having a correct tab order; readers are encouraged to visit the guide [START_REF]CHI 2014 Program Committee. CHI 2014 Guide to an Accessible Submission[END_REF] for more on these recommendations. A detailed guide was created to provide step-by-step instructions for the five main recommendations. The goal was to maximize accessibility while minimizing the workload of individual authors.

Information on .pdf accessibility, including a step-by-step guide for adding accessibility information and tool information on checking a .pdf, was added to the CHI 2014 website, and information about .pdf accessibility was added to the CHI 2014 paper tem-plates. This same information was used for CHI 2015 and CHI 2016.

The CHI 2014 conference received 2,043 submissions for papers and notes, with 465 accepted for publication. For all 465, the CHI 2014 team ran an automated check using Adobe Acrobat Action Wizard to create an accessibility report for each submission, creating a spreadsheet identifying which of the five recommendations each submission had addressed. The papers review committee sent a report to the primary authors on their submission's accessibility features, including links to the instructions for each of the recommendations. Authors received it before the camera-ready copy was to be submitted and were reminded to make their papers compliant with the five recommendations. The goal was to inform, educate, and improve digital accessibility. Making the .pdf file accessible was thus encouraged but not required. This action increased accessibility of accepted papers that were published in the ACM Digital Library but did not increase accessibility of the paper reviewing process. Furthermore, there are challenges with using some of the existing document production tools to create accessible .pdf files. Not all of the commonly used word processors and text editors support making accessible .pdf files; for example, MS-Word for Mac does not. In addition, although some previous attempts had sought to improve accessibility for La-TeX (such as Babett Schalitz's accessibility package 8 ), those packages were not robust enough for general use for CHI 2014 and CHI 2015. Nevertheless, SIGCHI volunteers have continued to improve the group's LaTeX templates (such as LaTeX Accessibility 8 ) and encourage participation by interested accessibility researchers and SIGCHI au- Figure 2 shows the difference in adherence between initial and final submissions for the 465 papers accepted for publication at CHI 2014, where authors were given specific details on the accessibility barriers of their respective papers. In four of five recommendations, accessibility of the papers increased 5% to 10% based on authors receiving feedback on accessibility. Unclear is why adherence to one recommendation (tab order) decreased slightly. There may be cases where authors had to update their final submission based on feedback from the publication vendor and forgot to reapply the accessibility changes.

Note that 30% accessibility of published papers or even 60% accessibil-ity is not ideal. The goal, as spelled out by the SIGCHI Accessibility Community, is 100% compliance. However, accessibility is a multi-pronged effort, and paper accessibility gets attention because it is an easy-to-measure metric; equally important are many other details we have discussed here (such as having accessibility chairs at each conference, proper information flows, and accessible physical locations). For instance, in choosing the site for the CHI 2019 conference-Glasgow, U.K.-accessibility criteria were specifically taken from the city's proposals, as well as from on-site walkthroughs, which led to one city with a fully accessible conference venue being chosen Giving authors individual notification of their papers' accessibility between acceptance and camera-ready submission in 2014 clearly increased the level of accessibility compliance. While accessibility of papers did increase, 16% to 26% is still not ideal, with a long way to go. As a comparison, we analyzed the accessibility of published papers from the ASSETS 2015 conference, though the sample size for ASSETS papers was 31, much smaller than the number of CHI papers in any given year. ASSETS generally uses two different approaches that have not yet been attempted by the CHI conference: The first is that authors are required (not just encouraged) to make their papers accessible and the second that SIGACCESS, sponsor of the ASSETS conference, specifically requires the company that is contracted for publishing, Sheridan, to manage the accessibility process and check for accessibility. We do not know the specifics of what is required in its contracts with Sheridan, and it is possible Sheridan is required to check for different accessibility features than in our evaluation. Given identical criteria, compliance for ASSETS 2015 papers was much higher than for CHI papers (in any given year) but still not at the 100% goal. In 2015, 74.1% of the AS-SETS papers had alternative text and table headers, 93.5% had generated a tagged .pdf file, and 90.3% had defaultlanguage information included in the .pdf, but only 51.6% of ASSETS 2015 papers had a correct tab order. And is there a hotel that may be farther away but that involves fewer barriers? Encourage feedback from the community at events and between events.

Include people with disabilities in organizational processes. One of the mottos of the disability rights movement is "nothing for us without us." Decisions about accessibility need to be made based on feedback from those with the most experience-people with disabilities. It is important early on to identify members of your community with disabilities who can provide specific feedback. Acknowledge that perspectives may be skewed; if your community includes many people with one type of disability, the feedback you receive may be biased. A core advisory group can provide feedback and advice and can help determine priorities.

Be clear about your priorities and communicate rationales. It is important to acknowledge that everything cannot be done at once. For instance, for an organization starting to become more inclusive, which of the following is a better first step: Making papers accessible or making videos on the website accessible? Making mentorship programs more inclusive or making journal editorial board software more accessible? Making the conference facility selections more accessible or setting up programs for remote attendance? All are important goals that should be achieved over time, but all cannot be achieved immediately. A dedicated advisory group, as with SIG-CHI's Accessibility Community, can be useful in setting priorities. Once priorities are set, they need to be communicated to the membership and to the broader community.

Recognize and explicitly address and communicate trade-offs. Be open about the fact that there are often trade-offs, as in the one between internationalization and consistent models of accessibility. Part of being an international organization means holding confer-over another equally attractive city but with a conference venue with multiple accessibility barriers.

In addition to event-specific efforts (such as those described here), other efforts to improve accessibility have been ongoing on multiple fronts within SIGCHI over the past few years. For instance, a SIGCHI email alias-sigchiaccessibility@listserv.acm.org-was set up for members to share their concerns with the Executive Committee, underscoring SIGCHI's commitment to being open and welcoming to academics, researchers, and practitioners with disabilities by inviting comments and concerns related to the organization's websites, publications, or physical accessibility at any SIGCHI-sponsored events, including conferences.

Another example of progress involves video captioning. SIGCHI captures the video and slides of a selection of the presentations at CHI and other SIGCHI-sponsored conferences. These presentations are included with the .pdf of the papers in the ACM Digital Library. Starting in 2016, SIGCHI volunteers began to work with ACM to create an ACM SIGCHI YouTube channel to host much of this content. As part of the effort, the SIGCHI Executive Committee authorized use of SIGCHI funds to create closed captions for all the videos on its YouTube channel. Once a video is uploaded to YouTube, SIGCHI works with a captioning company to develop professional (not automated) captioning. Because the captions are human generated, the time to caption all the videos in a conference can vary depending on the total number of videos uploaded.

Suggestions for All

Computing Organizations SIGCHI members surveyed as part of the SIGCHI Accessibility Community Report [START_REF]edit?pref=2&pli=1#heading=h[END_REF] were typically not aware of any SIG or ACM policy or procedure regarding inclusiveness for people with disabilities. This was the case for those with and those without disabilities. For example, respondents reported [START_REF]edit?pref=2&pli=1#heading=h[END_REF] being unable to answer the following questions: How can someone with a disability participate in a mentorship program sponsored by the organization? What happens when someone who is blind wants to vote in an election or run for office? Are the online tools utilized by journal editorial boards accessible? Do the procurement processes for these large contracts include accessibility? And what policies are used for remote participation?

Based on the SIGCHI experience, we can say that professional organization inclusiveness begins with explicit discussions on inclusiveness, and awareness and discussion represent an important first step. Executive committees of SIGs should start the discussion, which should expand to include conference chairs. Conference chairs should discuss accessibility with their technical program chairs. Executive committees should contact members of the professional community with known disabilities and email distribution messages asking for input and feedback. Conference chairs should also be aware that some disabilities are "invisible disabilities" that might not be apparent (such as learning disabilities and disabilities affecting energy level, as with Lupus and Lyme Disease). Starting the discussion produces information sharing, which should lead to a more formalized structure like a policy or specific committee position (such as accessibility chair for a conference). None of these changes will happen overnight. Becoming more inclusive is a process that takes place over a period of years. We thus recommend the following six actions for all ACM SIGs:

Reach out to SIGACCESS. No one within ACM has more experience with accessibility issues than SIGAC-CESS. At various points, SIGCHI used the SIGACCESS conference accessibility guidelines and portions of the SIGACCESS document accessibility guidelines and consulted with various members of the SIGACCESS Executive Committee who were always happy to help. It may be the SIGACCESS solutions cannot be implemented directly by another SIG due to scalability or lack of expertise, but SIGACCESS has the experience of creating solutions for most accessibility issues. SIGACCESS officers welcome inquiries and contacts from other SIGs.

Encourage proactive involvement and foster bidirectional communication. Make it easy for community members to notify the organization of potential accessibility needs before events like ences all over the world, including locations that have different accessibility requirements and accommodations. Such trade-offs should be acknowledged. When practices differ, it is critical that they be explicitly documented and communicated.

Allocate budget from SIG funds. Allocate budget from your SIG funds to support professional services (such as video captioning). Be clear about what work is done by volunteers and what is outsourced to professional services. SIGCHI and ACM function primarily through their volunteers, but SIGCHI has decided some aspects of accessibility are so important that we must contract with professionals who can provide dedicated and reliable focus to drive our inclusiveness agenda forward. This is not a criticism of the volunteers; all are committed to these initiatives, but for many, such plans are not their primary work focus, so a reliable, accountable effort is not a reasonable expectation.

Conclusion

We have three goals in telling the SIG-CHI story: underscore the importance of stakeholder engagement; offer broad suggestions for how large SIGs can improve the inclusiveness of physical events and digital content; and underscore that addressing physical and digital accessibility is an ongoing process that takes time, with involvement of many stakeholders. These stakeholders must work together to drive the creation of acceptable and accepted guidelines and resources, find individuals with expertise to work in an advisory capacity, and find volunteers to implement effective strategies and provide feedback regarding the policies and guidelines in action.

Improving the inclusiveness of any organization is a long-term process. It involves planning, structure, and information sharing. It involves checklists and inspections. It involves a commitment to programmatically raising awareness through communication and action. But where does inclusiveness start? One possibility is with members of the specific community raising awareness about barriers. But we advocate a more proactive stance. A professional community that has not been inclusive of people with disabili-ties is not likely to have members with disabilities who will raise awareness of what is needed. Inclusiveness must start with proactive outreach to increase inclusiveness so change can be driven from within the organization. A reactive stance through which accessibility issues are dealt with as (and only if) they occur is not programmatic and will not be as effective.

The impact of greater accessibility can be profound. The more accessible an organization becomes, the more people will feel comfortable giving feedback and working actively toward inclusive solutions that can lead to more members. As Kirkham [START_REF] Kirkham | Being reasonable: A manifesto for improving the inclusion of disabled people in SIGCHI conferences[END_REF] said about the current situation, "In practice significantly more research is being done about people with disabilities than by people with disabilities within SIGCHI." SIGCHI's hope is that SIG-CHI will be a community that is perceived as welcoming for all researchers and practitioners with disabilities.

In addition, actions on the part of any organization, including a SIG community, have the ability to influence outside actors. Large SIGs, when they educate others about digital and physical accessibility, can have significant influence on the conference locations they rent and the universities and companies that employ their members.

ACM has a leading role to play by ensuring all SIGs strive to be inclusive and by thus being a role model for other professional associations. The best way to handle such responsibility would ultimately be to ensure there are professional staff supporting and centralizing the most vital accessibility needs and accessibility is included in contractual relationships (such as with organizations that produce ACM's website and publications and contract conference venues).

  the survey, 623 CHI 2014 attendees answered the question about accessibility, with only 12 indicating their expressed needs were not met and the rest that their needs were met. Only one of those 12 responses actually indicated a specific disability-related need that was requested but not met. The other responses indicated an accommodation that should have been requested but was not ("I had an accessibility-related special need but did not request an accommodation"); most of the comments related to the cost of the conference or labeling of food ingredients. Although these topics relate to the inclusiveness of the conference, none specifically related to perceptual, motor, or cognitive disabilities. In addition, one change has been made though not based on the feedback from surveys; several related conferences (such as ASSETS and ubiComp) allow telepresence robots (such as Beam from Suitable Technologies, Inc. of Palo Alto, CA) to allow for participation of individuals with disabilities who are unable to travel. The CHI 2016 conference committee accepted applications from members who wanted to participate in the conference via a Beam robot due to "mobility impairments, chronic health issues, or temporary travel limitations." The experiment with robots at CHI 2016 was deemed a success, with a total of 35 individuals participating via 10 telepresence robots.

Figure 2 .Figure 1 .

 21 Figure 2. Difference in adherence among the 465 accepted papers for CHI 2014 between submitted and final versions (%). The bars here are likewise covered in patterned fill, rather than colors, to make the graphs more inclusive for colorblind readers.

The Executive Committee meets with AccessComputing directors at the Executive Committee's summer meeting; Papers. The webpage labeled "Information about making your CHI paper accessible" is added to the CHI 2014 conference website; Website and app. Two experts evaluate the CHI 2014 website and related mobile app for accessibility; Accommodations. Questions about disability-related accommodations are added to CHI 2014 registration forms and to all subsequent CHI registration forms; Automated reports. All authors of accepted papers for CHI 2014 receive an automated report evaluating the accessibility of their submissions; and Accessibility Community. The SIGCHI Accessibility Community is created. 10 2014. First face-to-face meeting of the SIGCHI Accessibility Community is held at the CHI 2014 conference in Toronto. Chairs appointed. Digital accessibility chairs and physical accessibility chairs are appointed to the CHI 2015 Technical Program Committee; Discussions. Inclusiveness is discussed at the CHI 2014 Town Hall meeting in Toronto; and Officers elected. For the first time, officers for the SIGCHI Accessibility Community are elected. 2015. The first report examining SIGCHI accessibility is produced, documenting failures and successes of CHI (and SIGCHI-sponsored) conferences to meet the accessibility needs of attendees. 2016. The SIGCHI Executive Committee authorizes use of SIGCHI funds to create closed captions for all videos on the SIGCHI YouTube channel (https://www.youtube. com/user/acmsigchi). Telepresence robots. Individuals with disabilities unable to travel were encouraged to apply for the use of telepresence robots (deemed a success) at CHI 2016. Appointed. Individual appointed to CHI Steering Committee to specifically work on accessibility.

	portunity for people with disabilities or
	those who are committed to improving accessibility to advance such efforts. The first face-to-face meeting of the SIGCHI Accessibility Community was held at the CHI 2014 conference in To-	SIGCHI Accessibility Timeline
	ronto and its first officers were elected
	in November 2014. Today, it lists 53 of-
	ficial members on the SIGCHI website
	and 134 members in the Facebook in-
	terest group.
	The mission of the SIGCHI Acces-
	sibility Community, as spelled out on
	the website, is to improve "… the ac-
	cessibility of SIGCHI conferences, and
	the digital accessibility of SIGCHI web
	site and publications. Our priorities
	include providing clear support and
	information to conferences and their
	leadership about accessibility, provid-
	ing support for SIGCHI members who
	are facing accessibility issues, advocat-
	ing for accessibility issues, and liais-
	ing with other communities such as
	SIGACCESS." One of the first acts of
	the SIGCHI Accessibility Community
	in 2014 was to assess the state of acces-
	sibility across SIGCHI from a member
	perspective, conducting a survey of
	SIGCHI members and analyzing post-
	conference survey responses given by
	CHI attendees about CHI accessibility.
	Other data analyzed included the num-
	ber of conferences in 2014 sponsored
	by SIGCHI with accessibility chairs
	(four of 17) and reports by commu-
	nity members on problems they had
	encountered. This led to the SIGCHI
	Accessibility Community's May 2016
	report, 11 including five recommenda-
	tions for future goals for SIGCHI:
	Recommendation 1. Ensure 100% of
	conferences are accessible, have an
	accessibility policy, and have a clear
	chain of command for addressing ac-
	cessibility issues;
	Recommendation 2. Ensure 100% of
	new content (such as videos and pa-
	pers) meets established standards for
	accessibility and develop a process for
	achieving this goal;
	Recommendation 3. Create a proc-
	ess for handling accessibility requests
	within SIGCHI;
	Recommendation 4. Increase repre-
	sentation of people with disabilities
	within SIGCHI; and
	Recommendation 5. Assess SIGCHI's
	success in meeting accessibility guide-
	lines at least once every two years.

Acknowledgments

The authors would like to acknowledge the advice provided by Sheryl Burgsthaler, Richard Ladner, Clayton Lewis, Jennifer Rode, Terry Thompson, Shari Trewin, and Jeff Bigham to the SIGCHI Executive Committee and CHI 2014 and CHI 2015 Program Committees.


Qi Wang
email: wangqi08@ict.ac.cn

Member, IEEE Katia Jaffr Ès-Runser

Member, IEEE Yongjun Xu

Jean-Luc Scharbarg
email: jean-luc.scharbarg@enseeiht.fr

Zhulin An
email: anzhulin@ict.ac.cn

Christian Fraboul
email: christian.fraboul@enseeiht.fr

J.-L Scharbarg

TDMA Versus CSMA/CA for Wireless Multihop Communications: A Stochastic Worst-Case Delay Analysis

Keywords: IEEE802.11 DCF, stochastic worst-case end-to-end delay, time division multiple access (TDMA), wireless multihop networks

Wireless networks have become a very attractive solution for soft real-time data transport in the industry. For such technologies to carry real-time traffic, reliable bounds on end-to-end communication delays have to be ascertained to warrant a proper system behavior. As for legacy wired embedded and real-time networks, two main wireless multiple access methods can be leveraged: one is time division multiple access (TDMA), which follows a time-triggered paradigm, and the other is carrier sense multiple access with collision avoidance (CSMA/CA), which follows an event-triggered paradigm. This paper proposes an analytical comparison of the time behavior of two representative TDMA and CSMA/CA protocols in terms of the worst-case end-to-end delay. This worst-case delay is expressed in a probabilistic manner because our analytical framework captures the versatility of the wireless medium. Analytical delay bounds are obtained from delay distributions, which are compared to fine-grained simulation results. Exhibited study cases show that TDMA can offer smaller or larger worst-case bounds than CSMA/CA depending on its settings. Index Terms-CSMA/CA,

bound. Guaranteeing hard real-time communications in wireless networks is difficult due to the unreliability of the wireless channel. However, it is possible to guarantee soft real-time requirements with a dedicated protocol stack design. Such networks can tolerate a really small probability for the end-to-end delay of flows to exceed a fixed time limit. In these networks, it is thus possible to derive a probabilistic worst-case delay bound d w with a given confidence level.

As for legacy wired embedded and real-time networks, two main types of multiple access methods can be leveraged: 1) time division multiple access (TDMA), which follows a time-triggered paradigm, and 2) carrier sense multiple access with collision avoidance (CSMA/CA), which follows an eventtriggered paradigm. So far, wireless real-time networking solutions rely on a mesh topology where TDMA is exploited for its high determinism [START_REF] Petersen | WirelessHART versus ISA100.11a: The format war hits the factory floor[END_REF]. CSMA/CA is the solution chosen for mainstream nontime-sensitive wireless networking for its scalability and elastic bandwidth management capability.

Several studies have looked at the benefits of CSMA/CA solutions for soft real-time networking and compared their performance to TDMA solutions. Most of these works have evaluated both approaches using simulations and experiments. In this paper, we propose to look at the problem from a theoretical point of view. There is still a need for a comprehensive analytical framework capable of calculating the worst-case delay bounds of flows carried on a given wireless network [START_REF] Suriyachai | A survey of MAC protocols for mission-critical applications in wireless sensor networks[END_REF]. The problem is not easy since wireless communications have to be modeled with a link transmission probability. Modeling the multihop, multiflow interactions requires advanced performance evaluation models (e.g., Markov chain, Z-transforms, etc.) whose assumptions are not always realistic.

This paper introduces a new method to calculate the delay distribution of a basic TDMA protocol. It relies on an analytical framework that we have previously defined to capture the performance (in average) of multihop multiflow wireless networks [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF]. From this delay distribution calculation, we can derive the stochastic worst-case delay bound of TDMA for any topology and flow pattern. This delay distribution and the worst-case bound are validated against extensive simulations. Next, we leverage this new TDMA bound calculation to compare the performance of TDMA to the one of CSMA/CA on two elementary network topologies. Therefore, the analytical model of [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF] we had validated for CSMA/CA is applied to the selected topologies. Several TDMA configurations are tested. As expected, TDMA can be made more or less efficient than CSMA/CA depending on its settings. It is interesting to note that our model clearly captures the longer tail of the delay distribution of CSMA/CA compared to TDMA.

This paper is organized as follows. Section II introduces network models and protocols related to both multiple access schemes. Section III pictures the main elements of the analytical models proposed herein for the end-to-end delay distribution computations of TDMA and CSMA/CA. Section IV validates our analytical models against simulations. Following, it compares the performance of TDMA and CSMA/CA on two topologies. Section V identifies main related works, and finally, Section VI concludes this paper.

II. SYSTEM MODEL AND PROTOCOLS

A. Multihop Topologies

In this paper, we investigate two different atomic topologies that are at the core of many deployment scenarios of wireless multihop communications. First, we will concentrate on a linear deployment scenario, as shown in Fig. 1(a). Such scenarios are typical where coverage needs to be extended in a specific direction. Linear topologies are for instance deployed to extend coverage on demand using swarms of drones over a stadium [START_REF] Pinto | Aerial multi-hop network characterization using cots multi-rotors[END_REF]. The second 2-relay/2-flow topology has been investigated to capture the contention effect of a set of nodes carrying multiple flows.

The linear topology is a basic multihop topology, where all packets are forwarded from one source node S to a destination node D using relay nodes. In our case, we choose a topology where x nodes relay the frames from S to D [cf., Fig. 1(a)]. In Section IV, we will provide results for x equal to 3, 4, or 5. The more relays are exploited, the higher the odds for the transmission to fail. Typically, end-to-end communications exceeding four to five hops get more difficult to implement in practice. The second topology investigated is the 2-relay/2-flow topology of Fig. 1(b). Here, the two relays have to forward packets that belong to two flows, simultaneously. The first flow is emitted by S 1 going to D 1 and the second flow is emitted by S 2 , going to D 2 . This situation is critical since the relays have to listen to both flows and to re-emit them concurrently.

Source nodes generate strictly periodic flows of frames. As we will explain later in Section IV, we set the frame generation period such as there is only one frame in the emission buffer of the source at all times. Thus, the only delay we are computing analytically or measuring by simulation is the MAC delay, i.e., the time for the frame to gain access to the channel. There is no delay related to queuing in this work.

B. CSMA/CA Network Model and Protocol

We assume in this work that all nodes of the network follow the state-of-the-art IEEE802.11 DCF MAC protocol. We refer the reader to the IEEE802.11-2012 norm for a detailed description of the IEEE802.11 DCF MAC protocol and to [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF] for a primer on the subject. The DCF mechanism can be extended by the RTS/CTS message exchange to avoid the hidden terminal problem. In this case, before initiating a communication, the emitter sends a Request To Send (RTS) frame. The destination node then emits a Clear To Send (CTS) frame to notify nodes that have not received the initial RTS of the imminent transmission start. The CSMA/CA protocol is completely distributed and thus can be very easily deployed.

C. TDMA Network Model and Protocol

A perfectly synchronized TDMA is considered. A superframe of |T | time slots is repeated indefinitely. For the 2-relay/2flow scenario, |T | = 4. The source S 1 emits its frames in time slot 1, source S 2 in slot 2, relay R 1 in slot 3, and relay R 2 in slot 4. Similarly, for the 3-relay scenario, |T | = 4 with the source emitting in time slot 1, and relays R i in time slot number i + 1. As shown in Fig. 1, there are bidirectional links between relays but not between sources and relays, nor between relays and destinations. It is a way to represent multiple paths, by allowing circular paths with different lengths.

In our TDMA network model [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF], each relay node is characterized by a set of uniform forwarding probabilities x uv ij that govern its forwarding decisions. Assuming node j receives a

x 1 3 S 1 R 1 x 1 4 S 1 R 2 x 2 3 S 2 R 1 x 2 4 S 2 R 2 x 3 4 R 1 R 2 x 4 3 R 2 R 1 τ 1 S 1 τ 2 S 2 τ 3 R 1 τ 4 R 2
Unique Solution 0.49 0 0.49 0 0.95 0.02 1 1 0.9986 0.9487 1-flow 3-relay scenario As such, a packet may travel one hop in the duration of at most one superframe. The forwarding probability x uv ij is the probability to forward the packet received from node i in slot u of super frame s in the time slot v of next superframe s + 1. Node j only re-emits at most once a packet received in slot u as v x uv ij ≤ 1. In case v x uv ij < 1, the packet may be dropped with probability 1v x uv ij . Each node of the network is represented by its emission rate in a slot. The emission rate τ u i represents the proportion of time a node i is active in a slot u, in average. For instance, a value of τ u i = 0.5 means that node i is emitting in slot u in every two superframes. Source nodes have an emission rate of 1 in time slot 1 for both topologies.

x 1 2 S R 1 x 1 3 S R 2 x 1 4 S R 3 x 2 3 R 1 R 2 x 2 4 R 1 R 3 x 3 2 R 2 R 1 x 3 4 R 2 R 3 x 4 2 R 3 R 1 x 4 3 R 3 R 2 τ 1 S τ 2 R 1 τ 3 R 2 τ 4 R 3 S mi
To ensure flow conservation and capture the cross-layer effect, the relay nodes have an emission rate that is proportional to the amount of packets they receive from other nodes and their respective forwarding probabilities. The amount of packets they receive is a function of the number of packets other nodes have sent, and the link quality over which they have been received. The link quality is quantified by a channel probability p u ij that represents the chances for a packet to be properly received in time slot u over link (i, j). This channel probability is derived from the average packet error rate on link (i, j) and from the emission rates of sending nodes. (cf., [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF] for details). Flow conservation is ensured if the following set of |E| equations is ensured:

(i,j )∈ --→ N u j u ∈T τ u i p u ij x uv ij = τ v j ∀(j, v) ∈ E (1)
where τ u i p u ij is the probability that a packet sent by i in time slot u arrives in j. |E| is given by the number of edges times the number of slots.

-→ N v j is the set of outgoing edges coming into node j from any node i in time slot u.

Based on this TDMA network model, we have shown in [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF] that it is possible to calculate, for a given matrix of forwarding probabilities X, various performance metrics using a steadystate computation reminiscent of a Markov chain. The two main performance metrics we have defined are the so-called capacityachieving average end-to-end delay f c D and capacity-achieving average energy f c E metrics. Both are to be minimized and are, respectively, equal to the average end-to-end delay f D and the average energy consumed f E normalized by the throughput f C I). P 1 , P 2 experience a direct path to the destination. P 1 0 uses the loop between R 3 and R 2 , while R 1 drops P 1 1 due to flow conservation constraint.

defined in [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF]. As such, we have the relations:

f c D = f D /f C and f c E = f E /f C . Since both f c
D and f c E metrics are normalized by the achieved capacity f C , each solution's performance is scaled to the actual throughput the whole system offers. As such, these metrics measure how much delay and how much energy it would cost to push all data through the system (they are capacity-achieving). In terms of units, f c D is expressed in number of hops as it gives the average number of hops required for a packet to arrive in D. For f c E , it represents the number of Joules required by all emissions and reception operations for one packet to arrive at its destination.

For the two topologies investigated in this work, we have calculated the Pareto-optimal forwarding probabilities given in Table I. These forwarding probabilities have been derived using a multiobjective optimization problem formulation where capacity-achieving delay (f c D ) and capacity-achieving energy (f c E ) are minimized concurrently (cf., [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF] for a detailed definition). The solutions provide the best tradeoffs between these two performance metrics. The multiobjective problem has been solved with the NSGA-2 algorithm. In our multiobjective problem, we have to add the constraint x R ( i ) R ( i -1 ) ≤ 1 -∆ and x R ( i -1 ) R i ≤ 1 -∆ (∆ = 0.05) to ensure convergence of the Markov model to steady state (cf., [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF]).

For the 2-relay scenario, only one solution is tested because the whole search has resumed to a single Pareto-optimal point, as represented in Fig. 3(a). For the 3-relay scenario, three forwarding solutions are investigated further in this work, all extracted from the Pareto-optimal set of Fig. 3(b). The first one, S m in , exhibits the smallest average end-to-end delay (but the highest average energy), the second one, S m ax , exhibits the largest average end-to-end delay (but the smallest average energy), and the last one, S m iddle , exhibits an average delay in between smallest and largest. Similar, for the 5-relay scenario, three forwarding solutions are investigated, as shown in Fig. 3(c), respectively.

D. Illustrative Example for TDMA

To clearly understand our TDMA protocol, we picture possible transmission sequences for the 1 flow 3-relay network configured with solution S m in (cf., Table I) in Fig. 2. In this solution, from the forwarding probabilities, a loop exists between R 2 and R 3 . In the first two superframes, packets emitted by S are forwarded without using the loop. For instance, P 1 is first re-emitted by relay R 1 in time slot 2, then by R 2 in slot 3, then by R 3 in slot 4 to finally arrive at D. This means that in slot 1, R 1 has received a packet from S and decided following probability x 12 S R 1 = 0.94 to store the packet into the buffer of slot 2. In slot 2, R 1 has a packet in its buffer and thus emits it. Still in slot 2, R 2 receives the packet and following probability x 23 R 1 R 2 = 0.95 chooses to store it in buffer of slot 3. Same steps are repeated in slots 3 and 4.

We also picture other possible (but less likely) sequences with packets P 10 and P 11 . Packet P 10 is received twice because it is overheard by R 2 and sent another time from R 2 to R 3 . More specifically, it is forwarded first by R 1 and then by R 2 in the same way than P 1 was. As R 3 receives P 10 , it decides following x 34 R 2 ,R 3 = 0.95 to emit it in slot 4. Both R 2 and D receive P 10 (as it happened as well for P 1 and P 2 ). But this time, R 2 decides to re-emit P 10 in slot 3 because of x 43 R 3 ,R 2 = 0.11. Thus, R 2 will store P 10 and emit it in next superframe 11, slot 3. Since flow conservation is enforced by constraint (1), packet p 11 is dropped by R 1 (this happens with probability 1x 23 R 1 R 2 = 0.05).

III. ANALYTICAL DELAY DISTRIBUTION AND WORST-CASE DELAY MODELS

This section introduces the analytical models to derive the delay distributions of both CSMA/CA and TDMA protocols.

The probabilistic worst-case end-to-end delay is derived from the delay distribution as defined next.

A. Worst-Case Delay Definition

The delay distribution for a flow ending at destination D j is given by the probability mass function (PMF) and denoted by the probability P [d j = d], with d ∈ R + being arbitrary positive end-to-end delay values. PMF can be computed for each flow in the network.

The stochastic worst-case delay for the flow ending at destination D j is defined as the delay d w for which the probability P [d j ≥ d] to find a delay larger than d w is arbitrarily small (for instance smaller than δ = 10 -9 ). Formally, for a flow ending at D j

d w = max d s.t. P [d j ≥ d] ≤ δ. (2)
If several flows exist, it is possible to calculate the worst-case delay for all the flows, which is given by the maximum of the d w values calculated for all possible destinations. Next, we concentrate on the PMF derivation for both CSMA/CA and TDMA schemes.

B. Delay Distribution for CSMA/CA

In our previous work [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF], we have analyzed and compared the two main delay distribution derivation methods for the IEEE802.11 DCF protocol proposed in [START_REF] Vardakas | Performance behaviour of IEEE 802.11 distributed coordination function[END_REF] and [START_REF] Zhai | Performance analysis of IEEE 802.11 MAC protocols in wireless LANs[END_REF]. Both works elaborate on the discrete time Markov chain model of Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. These Markov chains are derived for a one-hop communication interfered by n c -1 other nodes that constantly contend for channel access. We refer the reader to [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF] to retrieve all mathematical derivations related to our CSMA/CA model. Only main assumptions and necessary derivations are presented next.

As stated earlier, we assume the source generates packets periodically, with a period chosen such as there is one packet arriving in the source buffer when the previous packet has reached its destination. In other words, each packet has time to be flushed through the network before a new end-to-end transmission is attempted. Thus, no frames can build up in the source or relay queues, and there is no queuing delay.

To be able to apply the Markov model of [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF], where source and relay nodes compete continuously for the channel (we are at network saturation), we have to add supplementary interfering nodes. For each single-hop communication, we assume there is a total of n c = 3 nodes contending for channel access simultaneously, including the source of interest. From the derivations given by Vardakas et al. [START_REF] Vardakas | Performance behaviour of IEEE 802.11 distributed coordination function[END_REF], we calculate the Probability Generating Function (PGF) of the MAC delay for a one-hop communication. To retrieve the PMF of the single-hop communication, the PGF has to be inverted using the Lattice-Poisson formula given by Vu and Sakurai [START_REF] Vu | Accurate delay distribution for IEEE 802.11 DCF[END_REF].

To compute the PMF of end-to-end delay in a multihop communication, first, we calculate the PGF of the MAC delay for a one-hop communication. We assume that the delay experienced over one hop is independent of the delay of the other hops. This assumption is reasonable as we are in the saturated scenario, where all emitting nodes constantly contend for the medium. The PGF of the sum of independent random variables is equal to the product of the PGF of each variable. Thus, the analytical PGF of the multihop total delay d multihop (Z), calculated for any complex number Z ∈ C, can be derived as the product of the PGFs of MAC delays calculated for each hop, where C is the set of complex numbers:

d multihop (Z) = d 1 (Z) * d 2 (Z) * . . . * d h (Z)
, where d h (Z) is the PGF of the hth hop MAC delay. The value of the PGF d h (Z) for any complex Z ∈ C is given by the Z-transform of the h-th hop MAC delay d h [k] (a discrete time series where k is an integer):

d h (Z) = ∞ k =0 d h [k]Z k .
To retrieve the PMF, the numerical Lattice-Poisson inversion method given by Vu and Sakurai [START_REF] Vu | Accurate delay distribution for IEEE 802.11 DCF[END_REF] is applied with accuracy 10 -8 .

C. Delay Distribution for our TDMA Protocol

In our model, the delay is measured in hops. A packet may experience several paths, each one of different lengths in number of hops. It takes at most one superframe duration for the packet to travel one hop further. So all metrics of delay are expressed in hops, and can be easily converted in time units by multiplying them by M × ς slot , where M is the number of time slot and ς slot is the slot duration.

1) Relaying and Arrival Matrix: The relaying matrix Q gives the probabilities for any emission (i, u) in time epoch s (i.e., superframe) to be emitted as (j, v) at the following time epoch (s + 1) by the relays of the networks. The arrival matrix A is composed of the probabilities to go from any transient state to any absorbing state, i.e., the probabilities for any emission (i, u) at time epoch s to arrive at a destination D j in time slot v at time epoch (s + 1). N is the number of relays.

The relaying matrix Q is structured as follows:

Q =      0 Q 12 • • • Q 1N Q 21 0 • • • Q 2N . . . . . . Q N 1 • • • Q N -1N 0      0 is a |T |-
Q ij =    Q 11 ij • • • Q 1M ij . . . . . . Q M 1 ij • • • Q M M ij    (3)
where Q uv ij is the probability for a node j to retransmit in time slot v a packet that has been transmitted by node i in time slot u. From our network model, it equals to

Q u v = ij p u ij x uv ij . The arrival matrix A is given by A =    A 1D 1 • • • A 1D |D| . . . . . . A N D 1 • • • A N D |D|   
where A iD j is a |T |-by-|T | diagonal matrix whose diagonal elements A u iD j give the probabilities for a packet transmitted by a node i in time slot u to arrive at destination D j and A u iD j = p u iD j . Q S and A S are the relaying and arrival matrices for the packets sent by the sources and are given as

Q S =    Q S 1 1 • • • Q S 1 N . . . . . . Q S |O| 1 • • • Q S |O| N   
and

A S =    A S 1 D 1 • • • A S 1 D |D| . . . . . . A S |O| D 1 • • • A S |O| D |D|   
where Q S i j follows the pattern given by (3) and A S i D j is a |T |-by-|T | diagonal matrix whose diagonal elements are A u S i D j = p u S i D j . 2) Delay Distribution: We assume that one hop introduces a delay of one time unit. Consequently, an h-hop transmission introduces a delay of h units. The delay distribution P [d j = h] is the probability for a transmission toward D j to be done in h hops. After s time epochs, a packet can travel up to h = s + 1 hops. Thus, the PMF is given by

P [d j = h] =    A S • I D (D j ) f (D j ) h = 1 Q S • Q h -2 • A • I D (D j ) f (D j ) ∀h ≥ 2 (4)
where I D (D j ) is a selection vector of dimension |D||T | where the |T | elements relative to destination D j are equal to 1 and the others are equal to 0. I D (D j ) accumulates the packet arrival rate in each time slot at destination D j . And f (D j ) gives the total packet arrival rate obtained in D j . This total rate is the sum of the normalized rates obtained from each source sending to D j : f (D j ) = ∀S i ∈Q S f (S i , D j ). The normalized rate provided by source S i , f (S i , D j ), is defined in [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF] as f (S i , D j ) = ∀p∈P P (p) • τ S i , where P is the set of all possible paths from S i to D i , and P (p) is the probability for a packet emitted by S i to arrive in D i . This probability is directly obtained from Q and A matrices.

3) Computing Example for the Delay Distribution:

Following, we provide the main derivations that lead to the delay distribution of the 1-flow 3-relay TDMA delay distribution.

For the scenario of interest, there are |T | = 4 time slots. The source is transmitting in time slot 1, relay R 1 , R 2 , and R 3 are transmitting in time slot 2, 3, and 4, respectively. Thus, the relay matrix Q and arrival matrix A are given as follows (diagonal elements of Q are directly set to 0 since relays do not send data to themselves):

Q =     0 Q 23 R 1 R 2 Q 24 R 1 R 3 Q 32 R 2 R 1 0 Q 34 R 2 R 3 Q 42 R 3 R 1 Q 43 R 3 R 2 0     =    0 p 2 R 1 R 2 x 23 R 1 R 2 p 2 R 1 R 3 x 24 R 1 R 3 p 3 R 2 R 1 x 32 R 2 R 1 0 p 3 R 2 R 3 x 34 R 2 R 3 p 4 R 3 R 1 x 42 R 3 R 1 p 4 R 3 R 2 x 43 R 3 R 2 0    and A =   A 2 R 1 D 0 0 0 A 3 R 2 D 0 0 0 A 4 R 3 D   =   p 2 R 1 D 0 0 0 p 3 R 2 D 0 0 0 p 4 R 3 D   .
The relaying and arrival matrices Q S and A S for packets sent S are defined as

Q S = Q 12 S R 1 Q 13 S R 2 Q 14 S R
I T D (D) = 1 1 1 1 f (D)
gives the total packet arrival rate obtained in D. For the details of f (D) derivation, we refer the readers to our work in [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF]. It is computed as follows:

f (D) = 1 B [A 2 R 1 D • X + A 3 R 2 D • Y + A 4 R 3 D • Z] + A 1 SD where B = 1 -Q 23 R 1 R 2 Q 34 R 2 R 3 Q 42 R 3 R 1 -Q 32 R 2 R 1 Q 43 R 3 R 2 Q 24 R 1 R 3 -Q 34 R 2 R 3 Q 43 R 3 R 2 -Q 23 R 1 R 2 Q 32 R 2 R 1 -Q 24 R 1 R 3 Q 42 R 3 R 1 X = Q 12 S R 1 1 -Q 34 R 2 R 3 Q 43 R 3 R 2 + Q 13 S R 2 Q 32 R 2 R 1 + Q 34 R 2 R 3 Q 42 R 3 R 1 + Q 14 S R 3 Q 43 R 3 R 2 Q 32 R 2 R 1 + Q 42 R 3 R 1 Y = Q 12 S R 1 Q 23 R 1 R 2 + Q 43 R 3 R 2 Q 24 R 1 R 3 + Q 13 S R 2 1 -Q 24 R 1 R 3 Q 42 R 3 R 1 + Q 14 S R 3 Q 42 R 3 R 1 Q 23 R 1 R 2 + Q 43 R 3 R 2 Z = Q 12 S R 1 Q 23 R 1 R 2 Q 34 R 2 R 3 + Q 24 R 1 R 3 + Q 13 S R 2 Q 34 R 2 R 3 + Q 32 R 2 R 1 Q 24 R 1 R 3 + Q 14 S R 3 1 -Q 23 R 1 R 2 Q 32 R 2 R 1 .
The delay distribution P [d j = h] can be derived by substituting the above matrix in (4).

IV. RESULTS

First, this section confirms the accuracy of the delay distribution models derived for TDMA and CSMA/CA wireless multihop networks presented earlier by comparing them to finegrained protocol simulations. Second, the delay distribution and worst-case delay bounds for TDMA and CSMA/CA are compared for the 1-flow and 2-flow topologies illustrated in Fig. 1. Several settings are investigated, mostly related to the TDMA slot duration, the payload size, and the chosen delay-energy tradeoff solution.

A. Simulation Settings

Wireless topologies and protocols are simulated using the realistic discrete event-driven network simulator WSNet. 1 In all topologies, sources only generate frames and destinations only receive them. The sources emit a periodic flow of frames whose period is set differently according to the protocol in use. The end-to-end delay is the duration between the arrival of the frame in the source buffer and the arrival of the frame in destination buffer. Frames have a size of 127 bytes of payload (i.e., the standard maximum IEEE802.15.4 frame size). The data rate is 11 Mbits/s. Simulations are performed for the duration necessary to complete the transmission of 100 000 frames.

1) TDMA Settings: Results are given assuming an additive white Gaussian noise channel and a binary phase shift keying modulation without coding providing a bit error rate of BER(γ) = Q( √ 2γ) = 0.5 * erfc( √ γ), with γ the per bit signal to noise and interference ratio experienced on the link and erfc the complementary error function. In all topologies, only two nearby nodes communicate with each other (no other node is interfering), they experience a perfect link quality. Moreover, a perfect TDMA is considered, where all nodes are perfectly synchronized. The duration of each time slot is sufficient for emitting a complete frame. The time slot durations ς slot values are considered here: a) ς slot = 0.29 ms, the minimum slot duration for sending the frames with 127 bytes of payloads and 24 bytes of the PHY header using IEEE802.11 at 11 Mbits/s. b) ς slot = 10 ms, the regular slot duration chosen by Wire-lessHART or ISA100.11a TDMA protocols. Note that both slot durations are long enough to carry a frame with payload of 127 bytes, whether using IEEE802.11 at 11 Mbits/s or IEEE802.15.4 at 250 kbits/s. Relay nodes follow the protocol given in Algorithm 1.

2) CSMA/CA Settings: Presented results for the IEEE802.11 DCF MAC delay are given with the RTS/CTS mechanism. DSSS-PHY layer is assumed. Main DCF timing values are given in Table II. The period of flows emitted by the sources in simulations are derived from the analytical Markov chain model. The analytical Markov chain calculates the end-to-end delay distribution for each flow. From this distribution, it is straightforward to extract the worst-case endto-end delay. By setting the source periodicity to the worst-case end-to-end delay obtained by the Markov chain model, the simulation reaches the steady state assumed analytically. We have observed in the simulation traces that no packet is kept in his buffer for more than |T | -1 time slots. To be consistent with the Markov model assumptions and fair with TDMA, all nodes of the network have to be in the range of two nodes that are constantly competing for channel access in our simulations.

B. Delay Distribution for TDMA and CSMA/CA Networks

To assess the distance between both analytical and simulated delay distributions, we compute the root-mean-squared error:

RMSE = 1 n n i=1 (d(i)-d(i)) 2 f (i) 2
, with n being the total number of points on the graph, and d(i) and d(i) being the analytical and simulated delay values. 1) TDMA Delay Distributions: For the symmetric 2-flow 2-relay topology, the delay distribution for each sourcedestination pair S 1 -D 1 and S 2 -D 2 are the same. Delay distribution for TDMA has been computed in this section with the slot duration of 0.29 ms.

As shown in Fig. 4, the analytical delay distribution for one source-destination pair compared with the simulation results for 2-relay TDMA network matches well for most of the delay values that appear the most frequently. The tail of the distribution is very difficult to validate with simulations since such delays are very rare events, with very small probabilities (y-axis of plot is in logscale). However, looking at the overall fit, and the RMSE of 1.7069 * 10 -3 for the computed values, we can conclude that the model seems to be accurate enough (for soft real-time guarantees).

We have to stress that the distribution obtained with our TDMA model accounts for all packets received at the destination. As shown in our illustrative example of Fig. 2, packets can travel over the loop (cf., packet P 10 ). In this case, the destination can receive several copies that travelled for a different number of hops in the network. These copies provide redundancy and do explain the tail of the delay distribution calculated here.

For the 3-relay TDMA networks, there are several Pareto solutions, as shown in Fig. 3(b). We recall that we have picked three Pareto optimal solutions to show their delay distribution: S m in , S m iddle , and S m ax . Their respective distributions are plotted in Fig. 5(a)-(c). The RMSE between analytical and simulated delay PMF for the 2-relay, 3-relay, 4-relay, and 5-relay TDMA networks are given in Table III. Again, these values are really small.

Looking at the impact of the number of relays N on the linear topology, it is interesting to notice that the tail of the S m in delay distribution does not grow much with N . The impact of N is stronger on S m iddle and S m ax distributions. This can be explained by the fact that the loop is rarely used in S m in compared to the two other solutions.

2) CSMA/CA Distributions: We have also verified how good the fit for our CSMA/CA model is. From Fig. 6, we can conclude that analytical and simulated delay distributions match well, even for the distribution tail of 2-and 3-relays cases. The RMSE is 1.513 * 10 -2 for the 2-relay scenario, 3.213 * 10 -2 for the 3-relay scenario, 3.477 * 10 -2 for the 4-relay scenario, and 3.604 * 10 -2 for the 5-relay scenario.

C. Worst-Case Delay Bound Comparison

TDMA and CSMA/CA worst-case delay bounds have been compared assuming two different time slot duration values. The worst-case delay for 2-relay, 3-relay, 4-relay, and 5-relay topologies are given for different values of δ in Table IV. The comparison of the worst-case delay bounds for 2-relay and 3-relay topologies are illustrated in Figs. 7 and9.

As shown in Fig. 7, we can see that the worst-case delay bound of TDMA is larger than the one of CSMA for the 2-relay scenario. This plot has been derived for a time slot duration of 10 ms. For a time slot duration of 0.29 ms, however, TDMA is much faster than CSMA/CA, as shown in Table IV. Hence, TDMA can become way more efficient than CSMA/CA by adjusting its time slot duration to a smaller period. But, in practice, larger slots are chosen to mitigate the impact of synchronization errors, at the cost of overall performance degradation, as shown here. However, the tail of the TDMA distribution is much shorter than the one of CSMA. Thus, TDMA systems exhibit a slower increase in d w as accuracy increases (and δ reduces).

For the 3-relay CSMA/CA network, the worst-case delay bound with δ = 10 -5 is of 66 ms. As shown in Fig. 9(a),d w of TDMA obtained with S m in and a 10 ms slot is still larger than the worst-case delay of CSMA/CA. But for the time slot duration of 0.29 ms, TDMA is faster than CSMA/CA. Note that we have not accounted for the synchronization overhead in our TDMA derivations.

D. Worst-Case Delay Bound for Different Payloads

In this section, we compare the worst-case delay bound for different payload sizes. Fig. 8(a) and (b) illustrate the results for the 2-flow 2-relay topology and the 1-flow 3-relay topology, respectively. All previous results were given for a payload size of 127 bytes. Here, we investigate the impact of payload by comparing the distributions obtained for TDMA and CSMA/CA with a 127 bytes payload to a 2560 bytes payload (i.e., the maximum frame size of IEEE802.11). This extended payload is modeled in TDMA by setting ς slot to 2.1 ms. Not surprisingly, the smaller the payload, the smaller the worst-case delay bound. Even for of 2560 bytes (which is unusual for wireless sensor networks), TDMA performs better than CSMA/CA. This clearly calls for 1) implementing microsecond or submicro-second level synchronization algorithms to reduce the TDMA slot size from 10 ms slots to 3 ms slots, and 2) introducing the overhead introduced by such an algorithm in the delay distribution derivations.

V. RELATED WORKS AND DISCUSSION

Currently, only few works have addressed the problem of worst-case delay bound calculation for wireless multihop networks. They have focused on deriving either a deterministic or a probabilistic bound. Deterministic bound calculation methods encompass two pieces of works. The first piece is based on network calculus and has been proposed by Schmitt and Roedig [START_REF] Schmitt | Sensor network calculus-A framework for worst case analysis[END_REF] and extended in their later works to include the processing resources on the sensors. The analytical model is named Sensor Network Calculus. In [START_REF] Koubaa | Modeling and worst-case dimensioning of cluster-tree wireless sensor networks[END_REF] and [START_REF] Lenzini | Tight end-to-end per-flow delay bounds in fifo multiplexing sink-tree networks[END_REF], it has been applied to analyze the IEEE802.15.4 cluster-tree WSNs. In the aforementioned works, it has been assumed that transmissions follow a perfect TDMA. Thus, the service curve can be approximated by a rate-latency curve. Assuming that the channel is perfect during the specified time window may be too optimistic in some cases. Localized interference may lead to a sudden drop in signal to noise ratio, triggering additional delay before perfect reception. Moreover, additional to such an analysis, it is necessary to measure the quality of the synchronization protocol used to ensure this perfect TDMA. There is a risk with such an approach to underestimate the worst-case delay bound. In other words, network calculus provides a purely deterministic analytical framework, which may be too rigid to capture the probabilistic nature of wireless transmissions. Moreover, it is not straightforward to capture the delay performance of contention-based medium access protocols such as CSMA with network calculus.

The later works for deterministic bound calculation rely on model checking [START_REF] Fehnker | Modelling and verification of the LMAC protocol for wireless sensor networks[END_REF], [START_REF] Mouradian | Formal verification of real-time wireless sensor networks protocols: Scaling up[END_REF]. These papers can only address small scale networks since for a simple five-node sensor network cluster, enumerating all possible topologies needs more than 8000 model checking runs. Despite the small number of nodes, this approach gave valuable insight into the protocol and the scenarios that lead to collisions not being detected by the protocol. To better capture the link error probabilities, it is proposed in [START_REF] Mouradian | Formal verification of real-time wireless sensor networks protocols: Scaling up[END_REF] to calculate in parallel the probability for the considered property to be verified knowing the probability that a given topology exists due to possible link packet error rates. But still, the well-known combinatorial explosion pitfall of model checking seems to be the main obstacle for a successful validation for real-time networks. Such networks carry more than a thousand real-time multicast flows, thus, deriving a scalable method is essential. Models of this paper are way more scalable as their complexity grows only with the number of nodes, and not with the number of flows carried in the network. Indeed, the matrix representation we leverage in our TDMA model and the Markov chain calculations for CSMA/CA can handle several source flows with the same complexity, provided that the number of nodes is not changed.

More recent works look at the problem from a probabilistic point of view, defining the worst-case end-to-end delay d w , as in this paper. In this vein, probabilistic network calculus has been applied in [START_REF] Fidler | Wlc15-2: A network calculus approach to probabilistic quality of service analysis of fading channels[END_REF] to provide a quality of service aware method that captures wireless fading channels. Probabilistic network calculus leverages moment generating functions. The study exploits a service curve for a Gilbert-Elliott channel with memory representative of a realistic fading channel. Results show clearly that the fading speed of the wireless medium impacts the service guaranties significantly.

A closely related work is the one of Despaux et al. [START_REF] Despaux | Modelling and performance analysis of wireless sensor networks using process mining techniques: Contikimac use case[END_REF], which leverages the probabilistic framework of reliability calculus proposed in [START_REF] He | Reliability calculus: A theoretical framework to analyze communication reliability[END_REF]. Reliability calculus relies on a stochastic model of the network where links are modeled using a packet error rate, and nodes with a probabilistic decision to forward a received message on a given link. Using the Laplace transform, He et al. [START_REF] He | Reliability calculus: A theoretical framework to analyze communication reliability[END_REF] manage to calculate the delay distribution of flows in a multihop network. Despaux et al. [START_REF] Despaux | Modelling and performance analysis of wireless sensor networks using process mining techniques: Contikimac use case[END_REF] have leveraged this stochastic model to calculate the delay performance of the ContikiMAC protocol. Therefore, they use processmining techniques to abstract the protocol process into a Markov chain to feed the model mentioned in [START_REF] He | Reliability calculus: A theoretical framework to analyze communication reliability[END_REF]. This abstraction is essential to capture the behavior of the protocol from very long execution traces. These execution traces encompass the behavior of the MAC protocol, but also the impact of the wireless channel at the time of recording. The network model of reliability calculus is close to the one proposed in our work, but our approach is more general: It can be leveraged to calculate a wide variety of network metrics that can be used to optimize networking decision (i.e., forwarding probabilities).

VI. CONCLUSION

Fig. 1 .

 1 Fig. 1. Investigated topologies: (a) linear topology composed of one flow and x relay nodes; and (b) cross flow topology where two flows share a specific path composed of two relay nodes.

Fig. 2 .

 2 Fig. 2. Example of our TDMA protocol (1-flow 3-relay networks with solution S m in given in TableI). P 1 , P 2 experience a direct path to the destination. P 1 0 uses the loop between R 3 and R 2 , while R 1 drops P 1 1 due to flow conservation constraint.

Fig. 3 .

 3 Fig.3. Capacity-achieving Pareto optimal bounds for TDMA network. x-axis (respectively y-axis) represents the average duration in milliseconds (respectively in Joules) for one packet received at the destination. (a) Pareto optimal bound for 2-relay wireless networks, (b) Pareto optimal bound for 3-relay wireless networks, and (c) Pareto optimal bound for 5-relay wireless networks.

3 andA S = A 1 SD

 31 D j ) is a dimension selection vector. Since there is only one destination in this example, I D (D j ) can be denoted by I D (D). The transpose of I D (D) is as follows:

Fig. 5 .

 5 Fig. 5. Analytical and simulated delay PMFs for 3-relay TDMA networks. (a) Delay distribution for S m in , (b) delay distribution for S m id d le , and (c) Delay distribution for S m a x .

Fig. 6 .

 6 Fig. 6. Analytical and simulated delay PMFs for CSMA/CA networks. (a) Analytical and simulated delay PMFs for 2-relay CSMA/CA network, (b) analytical and simulated delay PMFs for 3-relay CSMA/CA network, and (c) analytical and simulated delay PMFs for 5-relay CSMA/CA network.

Fig. 7 .

 7 Fig. 7. Worst-case delay bound comparison (δ = 10 -5 ) for 2-relay TDMA and CSMA/CA networks-time slot duration of 10 ms.

Fig. 8 .

 8 Fig. 8. Worst-case delay bound comparison for different payload sizes for 2-flow 2-relay and 1-flow 3-relay TDMA and CSMA/CA networks. δ = 10 -5 . (a) 2-flow 2-relay; and (b) 1-flow 3-relay (S m in solution).

Fig. 9 .

 9 Fig. 9. Worst-case delay bound comparison (δ = 10 -5 ) for 3-relay TDMA and CSMA/CA networks-time slot duration of 10 ms. (a) 3-relay with Pareto optimal solution S m in , (b) 3-relay with Pareto optimal solution S m id d le , and (c) 3-relay with Pareto optimal solution S m a x .

Algorithm 1 :

 1 TDMA Scheduling of Node j in Time Slot u.

	else if x u (v -1) ij Store the packet p into memory of slot v; ij then ≤ x ≤ x uv
	end if
	end if
	end for
	end if
	end if

if memory of slot u not empty then Send the packet; else if node j receives a packet p from i in slot u then Generate a random value x ∈ [0, 1]; for each time slot v ∈ T , v = u do if v==1 and x ≤ x u 1 ij then Store the packet p into memory of slot 1;

TABLE I FORWARDING

 I PROBABILITIES AND EMISSION RATES FOR 2-RELAY AND 3-RELAY SCENARIO SETTING IN TDMA

	2-flow 2-relay scenario

TABLE IV

 IV

			D W FOR ALL TOPOLOGIES
		δ	D W for TDMA	D W for TDMA	D W for CSMA/CA
			(ς s l o t = 0.29 ms)	(ς s l o t = 10 ms)	(IEEE802.11 DCF)
	2-flow	10 -5	10.44 (9 hops)	360	82
	2-relay	10 -6	12.76 (11 hops)	440	86
		10 -7	15.08 (13 hops)	520	88
		10 -8	17.4 (15 hops)	600	-
		10 -9	19.72 (17 hops)	680	-
	1-flow	10 -5	20.88 (18 hops )	720	66
	3-relay	10 -6	23.2 (20 hops )	800	74
		10 -7	25.52 (22 hops )	880	78
		10 -8	27.84 (24 hops)	960	-
		10 -9	30.16 (26 hops)	1040	-
	1-flow	10 -5	27.55 (19 hops)	950	132
	4-relay	10 -6	33.35 (23 hops)	1150	188
		10 -7	36.25 (25 hops)	1250	316
		10 -8	42.05 (29 hops)	1450	428
		10 -9	44.95 (31 hops)	1550	1442
	1-flow	10 -5	34.8 (20 hops)	1200	152
	5-relay	10 -6	41.76 (24 hops)	1440	314
		10 -7	45.24 (26 hops)	1560	676
		10 -8	52.2 (30 hops)	1800	1206
		10 -9	55.68 (32 hops)	1920	2174
	All results are given for S mi n solution (Unit: ms).

http://wsnet.gforge.inria.fr/

This paper provides an overview of two models whose aim is to calculate the worst-case delay bounds d w for TDMA and CSMA/CA-based wireless multihop networks. An original contribution of this work is the analytical delay distribution model for TDMA. After calculating the d w bounds for TDMA and CSMA/CA for both topologies, we have investigated the impact of the TDMA slot duration and payload on d w . We can show that this choice clearly impacts the worst-case bound performance of TDMA, as expected. In future works, we plan to validate our model against real experiments. It will be interesting as well to be able to control the load pushed into the network to capture its impact on both multiple access methods.

This work was supported in part by the National Natural Science Foundation of China under Grant 61602447 and Grant 61303245. Paper no. TII-16-0461.R1.